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

Gabriele Puppis - Dipartimento di Matematica e Informatica, Udine
Date and time
Tuesday, November 20, 2007 at 5:00 PM - Inizio alle 17:30, Caffe' e biscotti alle 17:00.
Ca' Vignal - Piramide, Floor 0, Hall Verde
Programme Director
Tiziano Villa
External reference
Publication date
November 6, 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  Verona University
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234