DagSemProc.07441.6.pdf
- Filesize: 135 kB
- 11 pages
Document
Tree Automata Make Ordinal Theory Easy
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 7441
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2008-04-09
Cite As Get BibTex
Thierry Cachat. Tree Automata Make Ordinal Theory Easy. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/DagSemProc.07441.6
Abstract
We give a new simple proof of the decidability of the First Order Theory of
$(w^{w^i},+)$ and the Monadic Second Order Theory of $(w^i,<)$, improving the
complexity in both cases. Our algorithm is based on tree automata and a new
representation of (sets of) ordinals by (infinite) trees.
Subject Classification
Keywords
- Ordinals
- First Order theory
- Monadic Second Order Theory
- tree automata
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads