Residual Finite Tree Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2003

Residual Finite Tree Automata

Résumé

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.
Fichier principal
Vignette du fichier
dlt03.pdf (222.1 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00091272 , version 1 (05-09-2006)
inria-00091272 , version 2 (05-09-2006)

Identifiants

Citer

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. pp.171 -- 182. ⟨inria-00091272v2⟩
495 Consultations
245 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More