Tree Automata Make Ordinal Theory Easy
classification
💻 cs.GT
keywords
omegatheoryautomataordertreealgorithmcasescomplexity
read the original abstract
We give a new simple proof of the decidability of the First Order Theory of (omega^omega^i,+) and the Monadic Second Order Theory of (omega^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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.