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.
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}, publisher = {EDP-Sciences}, volume = {45}, number = {3}, year = {2011}, doi = {10.1051/ita/2011107}, mrnumber = {2836494}, zbl = {1236.68173}, language = {en}, url = {http://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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, Volume 45 (2011) no. 3, pp. 347-370. doi : 10.1051/ita/2011107. http://www.numdam.org/articles/10.1051/ita/2011107/
[1] Data Structures and Algorithms. Addison-Wesley, Reading, MA (1983). | MR | Zbl
, and ,[2] Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155 (1996) 291-319. | MR | Zbl
,[3] From regular expressions to deterministic automata. Theoret. Comput. Sci. 48 (1986) 117-126. | MR | Zbl
and ,[4] Derivatives of regular expressions. J. Assoc. Comput. Mach. 11 (1964) 481-494. | MR | Zbl
,[5] From c-continuations to new quadratic algorithms for automaton synthesis. Int. J. Algebra Comput. 11 (2001) 707-735. | MR | Zbl
and ,[6] Canonical derivatives, partial derivatives and finite automaton constructions. Theoret. Comput. Sci. 289 (2002) 137-163. | MR | Zbl
and ,[7] Computing the follow automaton of an expression, in Proc. of CIAA 2004. Lect. Notes Comput. Sci. 3317 (2004) 90-101. | MR | Zbl
, and ,[8] Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, release October, 12th (2007).
, , , , , , and ,[9] Tree languages, in Handbook of Formal Languages 3. Springer (1997) Chap. 1, 1-68. | MR
and ,[10] The abstract theory of automata. Russian Mathematical Surveys 16 (1961) 1-53. | Zbl
,[11] Regular expression pattern matching for XML. SIGPLAN Not. 36 (2001) 67-80. | Zbl
and ,[12] Translating regular expressions into small -free nondeterministic finite automata. J. Comput. System Sci. 62 (2001) 565-588. | MR | Zbl
, and ,[13] Constructing NFAs by optimal use of positions in regular expressions, in Proc. of CPM 2002. Lect. Notes Comput. Sci. 2373 (2002) 279-288. | MR | Zbl
and ,[14] 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
,[15] Construction of tree automata from regular expressions, in Proc. of DLT 2008. Lect. Notes Comput. Sci. 5257 (2008) 491-503. | MR | Zbl
and ,[16] Derivatives of rational expressions with multiplicity. Theoret. Comput. Sci. 332 (2005) 141-177. | MR | Zbl
and ,[17] Regular expressions and state graphs for automata. IEEE Trans. Electron. Comput. 9 (1960) 39-57. | Zbl
and ,[18] Three partition refinement algorithms. SIAM J. Comput. 16 (1987) 973-989. | MR | Zbl
and ,[19] Éléments de théorie des automates. Vuibert (2003). | Zbl
,[20] 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 | Zbl
,[21] Hedge pattern partial derivative, in Proc. of CIAA 2009. Lect. Notes Comput. Sci. 5642 (2009) 125-134. | MR | Zbl
and ,[22] Generalized finite automata theory with application to a decision problem of second-order logic. Math. Syst. Theor. 2 57-81 (1968). | MR | Zbl
and ,[23] Machine models and simulations, in Handbook of Theoretical Computer Science A. Elsevier & The MIT Press (1990) Chap. 1, 1-66. | MR | Zbl
,[24] Passage d'une expression rationnelle à un automate fini non-déterministe. Bull. Belg. Math. Soc. 4 (1997) 177-203. | Zbl
, and ,Cited by Sources: