Tree Automata with Global Constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Tree Automata with Global Constraints

Résumé

A tree automaton with global equality and disequality constraints, TAGED for short, is an automaton on trees which allows to test (dis)equalities between subtrees which may be arbitrarily faraway. In particular, it is equipped with an (dis)equality 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 decidability of emptiness of several classes. We give two applications of TAGEDs: decidability of an extension of Monadic Second Order Logic with tree isomorphism tests and of unification with membership constraints.
Fichier principal
Vignette du fichier
dlt-full.pdf (523.26 Ko) Télécharger le fichier
dlt-short.pdf (195.21 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00292027 , version 1 (04-11-2008)
inria-00292027 , version 2 (08-06-2009)

Identifiants

  • HAL Id : inria-00292027 , version 2

Citer

Emmanuel Filiot, Jean-Marc Talbot, Sophie Tison. Tree Automata with Global Constraints. 12th International Conference on Developments in Language Theory (DLT), Sep 2008, Kyoto, Japan. pp.314-326. ⟨inria-00292027v2⟩
296 Consultations
785 Téléchargements

Partager

Gmail Facebook X LinkedIn More