Evènement pour le groupe Graphes et Logique

Date 2011-03-15  11:00-12:00
TitreDeciding 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.  
Lieusalle 76 
OrateurCamille Vacher 
UrlLSV, ENS Cachan 

Aucun document lié à cet événement.

Retour à l'index