Abstract
The word position automaton was introduced by Glushkov and McNaughton in the early 1960. This automaton is homogeneous and has (||E|| + 1) states for an expression of alphabetic width ||E||. In this paper this type of automata is extended to regular tree expressions and it is shown that the conversion of a regular tree expression of size |E| and alphabetic width ||E|| into its reduced tree automaton can be done in O(|E|·||E||) time. The time complexity of the algorithm proposed by Dietrich Kuske and Ingmar Meinecke is also proved in order to reach an O(||E||·|E|) time complexity for the problem of the construction of the equation automaton from a regular tree expression.
D. Ziadi was supported by the MESRS - Algeria under Project 8/U03/7015.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science 155, 291–319 (1996)
Bruggemann-Klein, A.: Regular expressions into finite automata. Theoretical Computer Science 120, 197–213 (1993)
Chang, C.H., Paige, R.: From regular expressions to DFAs using compressed NFAs. Theoretical Computer Science 178, 136 (1997)
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Loding, C., Tison, S., Tommasi, M.: Tree automata techniques and applications (October 2007), http://www.grappa.univ-lille3.fr/tata
Cortes, C., Haffner, P., Mohri, M.: Rational kernels: Theory and algorithms. Journal of Machine Learning Research 5, 1035–1062 (2004)
Glushkov, V.M.: The abstract theory of automata. Russian Mathematical Surveys 16, 1–53 (1961)
Kuske, D., Meinecke, I.: Construction of tree automata from regular expressions. RAIRO - Theoretical Informatics and Applications 45, 347–370 (2011)
Ouardi, F., Ziadi, D.: Efficient weighted expressions conversion. Informatique Théorique et Application 42(2), 285–307 (2008)
Trakhtenbrot, B.: Origins and metamorphoses of the trinity: Logic, nets, automata. In: Proceedings of the Tenth Annual IEEE Symposium on Logic in Computer Science, pp. 26–29. IEEE Computer Society Press (June 1995)
Ziadi, D., Ponty, J.L., Champarnaud, J.M.: Passage d’une expression rationnelle a un automate fini non deterministe. Bulletin of the Belgian Mathematical Society - Simon Stevin 4, 177–203 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Laugerotte, É., Sebti, N.O., Ziadi, D. (2013). From Regular Tree Expression to Position Tree Automaton. In: Dediu, AH., Martín-Vide, C., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2013. Lecture Notes in Computer Science, vol 7810. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37064-9_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-37064-9_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37063-2
Online ISBN: 978-3-642-37064-9
eBook Packages: Computer ScienceComputer Science (R0)