2026-08-17T19:42:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1408 2024-03-06T11:07:45Z ddc:004 open_access

Tree Automata Make Ordinal Theory Easy Cachat, Thierry Ordinals First Order theory Monadic Second Order Theory tree automata 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thierry Cachat 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07441.6 urn:nbn:de:0030-drops-14082 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.6 eng https://creativecommons.org/licenses/by/4.0/legalcode