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

Speaker:  Gabriele Puppis - Dipartimento di Matematica e Informatica, Udine
  Tuesday, November 20, 2007 at 5:00 PM Inizio alle 17:30, Caffe' e biscotti alle 17:00.
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.

Ca' Vignal - Piramide, Floor 0, Hall Verde

Programme Director
Tiziano Villa

Publication date
November 6, 2007