License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07441.6
URN: urn:nbn:de:0030-drops-14082
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1408/
Go to the corresponding Portal |
Cachat, Thierry
Tree Automata Make Ordinal Theory Easy
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.
BibTeX - Entry
@InProceedings{cachat:DagSemProc.07441.6,
author = {Cachat, Thierry},
title = {{Tree Automata Make Ordinal Theory Easy}},
booktitle = {Algorithmic-Logical Theory of Infinite Structures},
pages = {1--11},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2008},
volume = {7441},
editor = {Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2008/1408},
URN = {urn:nbn:de:0030-drops-14082},
doi = {10.4230/DagSemProc.07441.6},
annote = {Keywords: Ordinals, First Order theory, Monadic Second Order Theory, tree automata}
}
Keywords: |
|
Ordinals, First Order theory, Monadic Second Order Theory, tree automata |
Collection: |
|
07441 - Algorithmic-Logical Theory of Infinite Structures |
Issue Date: |
|
2008 |
Date of publication: |
|
09.04.2008 |