Construction of tree automata from regular expressions

Dietrich Kuske; Ingmar Meinecke

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2011)

  • Volume: 45, Issue: 3, page 347-370
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Kuske, Dietrich, and Meinecke, Ingmar. "Construction of tree automata from regular expressions." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 45.3 (2011): 347-370. <http://eudml.org/doc/273037>.

@article{Kuske2011,
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.},
author = {Kuske, Dietrich, Meinecke, Ingmar},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {trees; automata; regular expressions; partial derivatives; tree automata; tree languages; synthesis of automata},
language = {eng},
number = {3},
pages = {347-370},
publisher = {EDP-Sciences},
title = {Construction of tree automata from regular expressions},
url = {http://eudml.org/doc/273037},
volume = {45},
year = {2011},
}

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
PB - EDP-Sciences
VL - 45
IS - 3
SP - 347
EP - 370
AB - 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.
LA - eng
KW - trees; automata; regular expressions; partial derivatives; tree automata; tree languages; synthesis of automata
UR - http://eudml.org/doc/273037
ER -

References

top
  1. [1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data Structures and Algorithms. Addison-Wesley, Reading, MA (1983). Zbl0487.68005MR666695
  2. [2] V. Antimirov, Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci.155 (1996) 291–319. Zbl0872.68120MR1379579
  3. [3] G. Berry and R. Sethi, From regular expressions to deterministic automata. Theoret. Comput. Sci.48 (1986) 117–126. Zbl0626.68043MR889664
  4. [4] J.A. Brzozowski, Derivatives of regular expressions. J. Assoc. Comput. Mach.11 (1964) 481–494. Zbl0225.94044MR174434
  5. [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. Zbl1024.68065MR1880374
  6. [6] J.-M. Champarnaud and D. Ziadi, Canonical derivatives, partial derivatives and finite automaton constructions. Theoret. Comput. Sci.289 (2002) 137–163. Zbl1061.68109MR1932893
  7. [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. Zbl1115.68424MR2143396
  8. [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. [9] F. Gécseg and M. Steinby, Tree languages, in Handbook of Formal Languages 3. Springer (1997) Chap. 1, 1–68. MR1470018
  10. [10] V.M. Glushkov, The abstract theory of automata. Russian Mathematical Surveys16 (1961) 1–53. Zbl0104.35404
  11. [11] H. Hosoya and B. Pierce, Regular expression pattern matching for XML. SIGPLAN Not.36 (2001) 67–80. Zbl1093.68556
  12. [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. Zbl1014.68093MR1837505
  13. [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. Zbl1077.68669MR2072611
  14. [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. MR77478
  15. [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. Zbl1159.68018MR2490980
  16. [16] S. Lombardy and J. Sakarovitch, Derivatives of rational expressions with multiplicity. Theoret. Comput. Sci.332 (2005) 141–177. Zbl1070.68074MR2122501
  17. [17] R.F. McNaughton and H. Yamada, Regular expressions and state graphs for automata. IEEE Trans. Electron. Comput.9 (1960) 39–57. Zbl0156.25501
  18. [18] R. Paige and R.E. Tarjan, Three partition refinement algorithms. SIAM J. Comput.16 (1987) 973–989. Zbl0654.68072MR917035
  19. [19] J. Sakarovitch, Éléments de théorie des automates. Vuibert (2003). Zbl1178.68002
  20. [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. Zbl1172.68526MR2214022
  21. [21] T. Suzuki and S. Okui, Hedge pattern partial derivative, in Proc. of CIAA 2009. Lect. Notes Comput. Sci. 5642 (2009) 125–134. Zbl1248.68317MR2550017
  22. [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.257–81 (1968). Zbl0157.02201MR224476
  23. [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. Zbl0900.68265MR1127167
  24. [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. Zbl0915.68123

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.