Tree Automata Make Ordinal Theory Easy
<|reference_start|>Tree Automata Make Ordinal Theory Easy: 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.<|reference_end|>
@article{cachat2006tree,
    title={Tree Automata Make Ordinal Theory Easy},
    author={Thierry Cachat (LIAFA)},
    journal={Foundations of Software Technology and Theoretical Computer
  Science, 26th International Conference, 2006, Proceedings. FSTTCS 2006 (2006)
  286-297},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0610166},
    primaryClass={cs.GT}
}