Skip to Main content Skip to Navigation
Documents associated with scientific events

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
IRCAM - Institut de Recherche et Coordination Acoustique/Musique, Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, 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.
Document type :
Documents associated with scientific events
Complete list of metadata
Contributor : Florent Jacquemard Connect in order to contact the contributor
Submitted on : Wednesday, July 3, 2013 - 3:42:33 PM
Last modification on : Tuesday, March 15, 2022 - 3:21:05 AM
Long-term archiving on: : Friday, October 4, 2013 - 4:11:31 AM


Files produced by the author(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⟩



Record views


Files downloads