Construction of tree automata from regular expressions
Kuske, Dietrich ; Meinecke, Ingmar
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011), p. 347-370 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2011-01-01
DOI : https://doi.org/10.1051/ita/2011107
Classification:  68Q45 
@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},
     volume = {45},
     year = {2011},
     pages = {347-370},
     doi = {10.1051/ita/2011107},
     mrnumber = {2836494},
     zbl = {1236.68173},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 347-370. doi : 10.1051/ita/2011107. http://gdmltest.u-ga.fr/item/ITA_2011__45_3_347_0/

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data Structures and Algorithms. Addison-Wesley, Reading, MA (1983). | MR 666695 | Zbl 0487.68005

[2] V. Antimirov, Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155 (1996) 291-319. | MR 1379579 | Zbl 0872.68120

[3] G. Berry and R. Sethi, From regular expressions to deterministic automata. Theoret. Comput. Sci. 48 (1986) 117-126. | MR 889664 | Zbl 0626.68043

[4] J.A. Brzozowski, Derivatives of regular expressions. J. Assoc. Comput. Mach. 11 (1964) 481-494. | MR 174434 | Zbl 0225.94044

[5] J.-M. Champarnaud and D. Ziadi, From c-continuations to new quadratic algorithms for automaton synthesis. Int. J. Algebra Comput. 11 (2001) 707-735. | MR 1880374 | Zbl 1024.68065

[6] J.-M. Champarnaud and D. Ziadi, Canonical derivatives, partial derivatives and finite automaton constructions. Theoret. Comput. Sci. 289 (2002) 137-163. | MR 1932893 | Zbl 1061.68109

[7] J.-M. Champarnaud, F. Nicart and D. Ziadi, Computing the follow automaton of an expression, in Proc. of CIAA 2004. Lect. Notes Comput. Sci. 3317 (2004) 90-101. | MR 2143396 | Zbl 1115.68424

[8] H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, release October, 12th (2007).

[9] F. Gécseg and M. Steinby, Tree languages, in Handbook of Formal Languages 3. Springer (1997) Chap. 1, 1-68. | MR 1470018

[10] V.M. Glushkov, The abstract theory of automata. Russian Mathematical Surveys 16 (1961) 1-53. | Zbl 0104.35404

[11] H. Hosoya and B. Pierce, Regular expression pattern matching for XML. SIGPLAN Not. 36 (2001) 67-80. | Zbl 1093.68556

[12] J. Hromkovic, S. Seibert and T. Wilke, Translating regular expressions into small ε-free nondeterministic finite automata. J. Comput. System Sci. 62 (2001) 565-588. | MR 1837505 | Zbl 1014.68093

[13] L. Ilie and S. Yu, Constructing NFAs by optimal use of positions in regular expressions, in Proc. of CPM 2002. Lect. Notes Comput. Sci. 2373 (2002) 279-288. | MR 2072611 | Zbl 1077.68669

[14] S.E. Kleene, Representations of events in nerve nets and finite automata, in Automata Studies. C.E. Shannon and J. McCarthy, Eds. Princeton University Press (1956) 3-42. | MR 77478

[15] D. Kuske and I. Meinecke, Construction of tree automata from regular expressions, in Proc. of DLT 2008. Lect. Notes Comput. Sci. 5257 (2008) 491-503. | MR 2490980 | Zbl 1159.68018

[16] S. Lombardy and J. Sakarovitch, Derivatives of rational expressions with multiplicity. Theoret. Comput. Sci. 332 (2005) 141-177. | MR 2122501 | Zbl 1070.68074

[17] R.F. Mcnaughton and H. Yamada, Regular expressions and state graphs for automata. IEEE Trans. Electron. Comput. 9 (1960) 39-57. | Zbl 0156.25501

[18] R. Paige and R.E. Tarjan, Three partition refinement algorithms. SIAM J. Comput. 16 (1987) 973-989. | MR 917035 | Zbl 0654.68072

[19] J. Sakarovitch, Éléments de théorie des automates. Vuibert (2003). | Zbl 1178.68002

[20] J. Sakarovitch, The language, the expression, and the (small) automaton, in Implementation and Application of Automata, 10th International Conference, CIAA 2005. Lect. Notes Comput. Sci. 3845 (2005) 15-30. | MR 2214022 | Zbl 1172.68526

[21] T. Suzuki and S. Okui, Hedge pattern partial derivative, in Proc. of CIAA 2009. Lect. Notes Comput. Sci. 5642 (2009) 125-134. | MR 2550017 | Zbl 1248.68317

[22] J.W. Thatcher and J.B. Wright, Generalized finite automata theory with application to a decision problem of second-order logic. Math. Syst. Theor. 2 57-81 (1968). | MR 224476 | Zbl 0157.02201

[23] P. Van Emde Boas, Machine models and simulations, in Handbook of Theoretical Computer Science A. Elsevier & The MIT Press (1990) Chap. 1, 1-66. | MR 1127167 | Zbl 0900.68265

[24] D. Ziadi, J.-P. Ponty and J.-M. Champarnaud, Passage d'une expression rationnelle à un automate fini non-déterministe. Bull. Belg. Math. Soc. 4 (1997) 177-203. | Zbl 0915.68123