Geodesic
Construction of tree automata from regular expressions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 3, pp. 347-370 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov's partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud and Ziadi from words to trees.

DOI : 10.1051/ita/2011107
Classification : 68Q45
Keywords: trees, automata, regular expressions, partial derivatives 
@article{ITA_2011__45_3_347_0,
     author = {Kuske, Dietrich and Meinecke, Ingmar},
     title = {Construction of tree automata from regular expressions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {347--370},
     year = {2011},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {3},
     doi = {10.1051/ita/2011107},
     mrnumber = {2836494},
     zbl = {1236.68173},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011107/}
}
TY  - JOUR
AU  - Kuske, Dietrich
AU  - Meinecke, Ingmar
TI  - Construction of tree automata from regular expressions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 347
EP  - 370
VL  - 45
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011107/
DO  - 10.1051/ita/2011107
LA  - en
ID  - ITA_2011__45_3_347_0
ER  - 
%0 Journal Article
%A Kuske, Dietrich
%A Meinecke, Ingmar
%T Construction of tree automata from regular expressions
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 347-370
%V 45
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011107/
%R 10.1051/ita/2011107
%G en
%F ITA_2011__45_3_347_0
Kuske, Dietrich; Meinecke, Ingmar. Construction of tree automata from regular expressions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 3, pp. 347-370. doi: 10.1051/ita/2011107

Cité par Sources :