Tree Automata Make Ordinal Theory Easy
Thierry Cachat
Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, 2006, Proceedings. FSTTCS 2006 (2006) 286-297 · 2006
We email you when a new notice or a question about this paper appears.
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.
Abstract licence: CC0
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.