Tree Automata Make Ordinal Theory Easy

Simple item page
dc.creatorCachat, Thierry
dc.date2006-10-30
dc.date.accessioned2026-07-07T07:39:02Z
dc.date.available2026-07-07T07:39:02Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/cs/0610166
dc.identifierhttp://arxiv.org/abs/cs/0610166
dc.identifierFoundations of Software Technology and Theoretical Computer Science, 26th International Conference, 2006, Proceedings. FSTTCS 2006 (2006) 286-297
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/121306
dc.subjectComputer Science and Game Theory
dc.titleTree Automata Make Ordinal Theory Easy
dc.typetext

Files

Collections

arXiv