Tree Automata with Constraints: a brief survey

Emmanuel Filiot 1 Florent Jacquemard 2, 3 Sophie Tison 4, 5
3 MuTant - Synchronous Realtime Processing and Programming of Music Signals
Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, IRCAM, CNRS - Centre National de la Recherche Scientifique
5 LINKS - Linking Dynamic Data
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : It is well-known that tree automata define exactly regular languages of trees. However for some problems one sometimes needs to test for equalities and disequalities of subtrees. For instance, ranges of non-linear tree transducers cannot be represented by tree automata. To overcome this problem some extensions of tree automata with tree (dis)equality constraints have been proposed. This talk surveys some of the most important models and their applications. Two families of automata are presented. First, we consider automata with local constraints. They have been used to solve problems related to pattern-matching, tree rewriting and more recently the tree homomorphism problem. Then, motivated by applications to XML processing and security protocols verification, we present a more recent model of tree automata with global constraints.
Type de document :
Document associé à des manifestations scientifiques
Tree Transducers and Formal Methods (Dagstuhl Seminar 13192), May 2013, Wadern, Germany. pp.1-18, 2013
Liste complète des métadonnées
Contributeur : Florent Jacquemard <>
Soumis le : mercredi 3 juillet 2013 - 15:42:33
Dernière modification le : jeudi 21 mars 2019 - 13:07:49
Document(s) archivé(s) le : vendredi 4 octobre 2013 - 04:11:31


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00840959, version 1


Emmanuel Filiot, Florent Jacquemard, Sophie Tison. Tree Automata with Constraints: a brief survey. Tree Transducers and Formal Methods (Dagstuhl Seminar 13192), May 2013, Wadern, Germany. pp.1-18, 2013. 〈hal-00840959〉



Consultations de la notice


Téléchargements de fichiers