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

Relatore:  Gabriele Puppis - Dipartimento di Matematica e Informatica, Udine
  martedì 20 novembre 2007 alle ore 17.00 - 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 3 - Piramide, Piano 0, Sala Verde

Tiziano Villa

Data pubblicazione
6 novembre 2007

Offerta formativa