Evènement pour le groupe Graphes et Logique
|Date|| 2011-03-15 11:00-12: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 semi-structured documents where they proved the NP-completeness 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 |
|Url||LSV, ENS Cachan |
Aucun document lié à cet événement.RetourRetour à l'index