Tree Automata With Global Constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Journal of Foundations of Computer Science Année : 2010

Tree Automata With Global Constraints

Résumé

We define tree automata with global equality and disequality constraints (TAGED). TAGEDs can test (dis)equalities between subtrees which may be arbitrarily faraway. In particular, they are equipped with an equality relation and a disequality relation on states, so that whenever two subtrees t and t′ evaluate (in an accepting run) to two states which are in the (dis)equality relation, they must be (dis)equal. We study several properties of TAGEDs, and prove emptiness decidability of for several expressive subclasses of TAGEDs.

Dates et versions

hal-00526987 , version 1 (17-10-2010)

Identifiants

Citer

Emmanuel Filiot, Jean-Marc Talbot, Sophie Tison. Tree Automata With Global Constraints. International Journal of Foundations of Computer Science, 2010, 21 (4), pp.571-596. ⟨10.1142/S012905411000743X⟩. ⟨hal-00526987⟩
114 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More