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 :
Documents associés à des manifestations scientifiques -- Hal-inria+
Tree Transducers and Formal Methods (Dagstuhl Seminar 13192), May 2013, Wadern, Germany. pp.1-18, 2013
Liste complète des métadonnées

https://hal.inria.fr/hal-00840959
Contributeur : Florent Jacquemard <>
Soumis le : mercredi 3 juillet 2013 - 15:42:33
Dernière modification le : mercredi 29 novembre 2017 - 16:32:44
Document(s) archivé(s) le : vendredi 4 octobre 2013 - 04:11:31

Fichier

TAC-survey.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00840959, version 1

Citation

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〉

Partager

Métriques

Consultations de la notice

628

Téléchargements de fichiers

99