A Contraction Method to Decide Monadic Second-order Theories of Trees

Gabriele Puppis - Dipartimento di Matematica e Informatica, Udine

Data e ora
martedì 20 novembre 2007 alle ore 17.00 - Inizio alle 17:30, Caffe' e biscotti alle 17:00.

Ca' Vignal 3 - Piramide, Piano 0, Sala Verde

Tiziano Villa

Referente esterno

Data pubblicazione
6 novembre 2007



We generalize the contraction method, originally proposed by Elgot
and Rabin and later extended by Carton and Thomas, from labeled
linear orderings to deterministic colored trees. We introduce a suitable
notion of indistinguishability of trees with respect to tree automata
and we take advantage of compositional properties of trees to reduce a
number of instances of the acceptance problem for tree auotomata to
simple instances involving regular trees. We prove that such a method
works effectively for a large class of trees, which is closed under
noticeable operations and includes all deterministic trees in the
Caucal hierarchy as well as several trees outside it.
Inizio pagina