Séminaire du LIF
Jeudi 16 Novembre - CMI, Salle du Conseil
Thierry Cachat
LIAFA, Paris 7
Tree automata make ordinal theory easy
We give a new simple proof of the decidability of the First Order Theory of (ωωi,+) and the Monadic Second Order Theory of (ω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.
Home-page de l'orateur : http://www.liafa.jussieu.fr/~txc