Residual Finite Tree Automata

Abstract : Tree automata based algorithms are essential in many fields in computer science such as verification, specification, program analysis. They become also essential for databases with the development of standards such as XML. In this paper, we define new classes of non deterministic tree automata, namely residual finite tree automata (RFTA). In the bottom-up case, we obtain a new characterization of regular tree languages. In the top-down case, we obtain a subclass of regular tree languages which contains the class of languages recognized by deterministic top-down tree automata. RFTA also come with the property of existence of canonical non deterministic tree automata.
Type de document :
Communication dans un congrès
7th International Conference on Developments in Language Theory, Jul 2003, Szeged, Hungary, Hungary. Springer Verlag, 2710 (2710), pp.171 -- 182, 2003
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00091272
Contributeur : Marc Tommasi <>
Soumis le : mardi 5 septembre 2006 - 17:48:22
Dernière modification le : mardi 24 avril 2018 - 13:32:54
Document(s) archivé(s) le : lundi 20 septembre 2010 - 16:53:06

Fichiers

Identifiants

Collections

Citation

Julien Carme, Rémi Gilleron, Marc Tommasi, Alain Terlutte, Aurélien Lemay. Residual Finite Tree Automata. 7th International Conference on Developments in Language Theory, Jul 2003, Szeged, Hungary, Hungary. Springer Verlag, 2710 (2710), pp.171 -- 182, 2003. 〈inria-00091272v2〉

Partager

Métriques

Consultations de la notice

604

Téléchargements de fichiers

219