Tree Automata with Global Constraints

Abstract : 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.
Type de document :
Communication dans un congrès
12th International Conference on Developments in Language Theory (DLT), Sep 2008, Kyoto, Japan. pp.314-326, 2008
Liste complète des métadonnées


https://hal.inria.fr/inria-00292027
Contributeur : Emmanuel Filiot <>
Soumis le : lundi 8 juin 2009 - 13:43:07
Dernière modification le : lundi 13 février 2017 - 18:00:08
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 13:01:04

Fichiers

dlt-full.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00292027, version 2

Collections

Citation

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, 2008. <inria-00292027v2>

Partager

Métriques

Consultations de
la notice

291

Téléchargements du document

267