Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-22T17:16:15.969Z Has data issue: false hasContentIssue false
  • English
  • Français

Construction of tree automata from regular expressions

Published online by Cambridge University Press:  22 August 2011

Dietrich Kuske  and
Ingmar Meinecke
Dietrich Kuske
Affiliation:
Fachgebiet Theoretische Informatik, Technische Universität Ilmenau, Postfach 100565, 98684 Ilmenau, Germany. [email protected]
Ingmar Meinecke
Affiliation:
Institut für Informatik, Universität Leipzig, PF 100920, 04009 Leipzig, Germany. [email protected]
Get access

Abstract

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

Treesautomataregular expressionspartial derivatives
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 45 , Issue 3 , July 2011 , pp. 347 - 370
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data Structures and Algorithms. Addison-Wesley, Reading, MA (1983).
Antimirov, V., Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155 (1996) 291–319. CrossRef
Berry, G. and Sethi, R., From regular expressions to deterministic automata. Theoret. Comput. Sci. 48 (1986) 117–126. CrossRef
Brzozowski, J.A., Derivatives of regular expressions. J. Assoc. Comput. Mach. 11 (1964) 481–494. CrossRef
Champarnaud, J.-M. and Ziadi, D., From c-continuations to new quadratic algorithms for automaton synthesis. Int. J. Algebra Comput. 11 (2001) 707–735. CrossRef
Champarnaud, J.-M. and Ziadi, D., Canonical derivatives, partial derivatives and finite automaton constructions. Theoret. Comput. Sci. 289 (2002) 137–163. CrossRef
Champarnaud, J.-M., Nicart, F. and Ziadi, D., Computing the follow automaton of an expression, in Proc. of CIAA 2004. Lect. Notes Comput. Sci. 3317 (2004) 90–101. CrossRef
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).
F. Gécseg and M. Steinby, Tree languages, in Handbook of Formal Languages 3. Springer (1997) Chap. 1, 1–68.
Glushkov, V.M., The abstract theory of automata. Russian Mathematical Surveys 16 (1961) 1–53. CrossRef
Hosoya, H. and Pierce, B., Regular expression pattern matching for XML. SIGPLAN Not. 36 (2001) 67–80. CrossRef
Hromkovic, J., Seibert, S. and Wilke, T., Translating regular expressions into small $\varepsilon$-free nondeterministic finite automata. J. Comput. System Sci. 62 (2001) 565–588. CrossRef
Ilie, L. and Constructing NFAs, S. Yu by optimal use of positions in regular expressions, in Proc. of CPM 2002. Lect. Notes Comput. Sci. 2373 (2002) 279–288. CrossRef
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.
Kuske, D. and Meinecke, I., Construction of tree automata from regular expressions, in Proc. of DLT 2008. Lect. Notes Comput. Sci. 5257 (2008) 491–503. CrossRef
Lombardy, S. and Sakarovitch, J., Derivatives of rational expressions with multiplicity. Theoret. Comput. Sci. 332 (2005) 141–177. CrossRef
McNaughton, R.F. and Yamada, H., Regular expressions and state graphs for automata. IEEE Trans. Electron. Comput. 9 (1960) 39–57. CrossRef
Paige, R. and Tarjan, R.E., Three partition refinement algorithms. SIAM J. Comput. 16 (1987) 973–989. CrossRef
J. Sakarovitch, Éléments de théorie des automates. Vuibert (2003).
Sakarovitch, J., 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. CrossRef
Suzuki, T. and Okui, S., Hedge pattern partial derivative, in Proc. of CIAA 2009. Lect. Notes Comput. Sci. 5642 (2009) 125–134. CrossRef
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).
P. Van Emde Boas, Machine models and simulations, in Handbook of Theoretical Computer Science A. Elsevier & The MIT Press (1990) Chap. 1, 1–66.
Ziadi, D., Ponty, J.-P. and Champarnaud, J.-M., Passage d'une expression rationnelle à un automate fini non-déterministe. Bull. Belg. Math. Soc. 4 (1997) 177–203.