
Evènement pour le groupe Graphes et Logique
Date  20110315 11:0012:00 
Titre  Deciding emptiness for tree automata with global constraints. 
Résumé  We study several classes of finite state automata running on ranked terms, extended with constraints that allow to test for equalities or disequalities between subterms. We focus on tree automata with global constraints where the tests are done depending on the states reached by the automaton on its runs. Such automata were introduced by Filiot, Talbot and Tison, 2008, in studies on semistructured documents where they proved the NPcompleteness of the membership problem and the undecidability of the universality problem. Moreover, they showed the decidability of the emptiness problem for several subclasses whith restrictions on the type or the number of (dis)equality constraints. We answer positively the full emptiness decision problem by showing that tree automata with global disequality constraints are equivalent to automata on direceted acyclic graph representations of terms (DAG). Global equality constraints may then be easily added by restrictions on the runs of the DAG automata. Then, we study the emptiness decision problem for automata with global constraints where we authorize "key constraints", that intuitively allow that all subtrees of a given type in an input tree are distincts. We give an emptiness decision procedure that allows to extend the automata with additionnal constraints, like counting constraints or local tests, while preserving decidability.

Lieu  salle 76 
Orateur  Camille Vacher 
Email  vacher@lsv.enscachan.fr 
Url  LSV, ENS Cachan 
Aucun document lié à cet événement. RetourRetour à l'index
 