inria-00292027, version 2
Tree Automata with Global Constraints
Emmanuel Filiot
1, 2Jean-Marc Talbot
a, 3Sophie Tison 1, 2
12th International Conference on Developments in Language Theory (DLT) (2008) 314-326
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.
- a – Université de Provence - Aix-Marseille I
- 1 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
- CNRS : UMR8022 – INRIA – IRCICA – Université Lille 1 - Sciences et Technologies
- 2 : MOSTRARE (INRIA Lille - Nord Europe)
- INRIA – CNRS : UMR8022 – Université Lille 1 - Sciences et Technologies : EA3588 – Université Charles de Gaulle - Lille III
- 3 : Laboratoire d'informatique Fondamentale de Marseille (LIF)
- CNRS : UMR6166 – Université de la Méditerranée - Aix-Marseille II – Université de Provence - Aix-Marseille I
- Domaine : Informatique/Informatique et langage
Informatique/Logique en informatique - Versions disponibles : v1 (04-11-2008) v2 (08-06-2009)
- inria-00292027, version 2
- http://hal.inria.fr/inria-00292027
- oai:hal.inria.fr:inria-00292027
- Contributeur : Emmanuel Filiot
- Soumis le : Lundi 8 Juin 2009, 13:43:07
- Dernière modification le : Lundi 8 Juin 2009, 13:55:43
Documents associés
Exporter