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 - 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.

© 2002 - 2021  Universit√† degli studi di Verona
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234