Abstract
We show that the upper bound (n − k)·2n + k·2n − 1 on the state complexity of the square of a regular language recognized by an n-state deterministic finite automaton with k final states is tight in the ternary case for every k with 1 ≤ k ≤ n − 2. Using this result, we are able to define a language that is hard for the square operation on languages accepted by alternating finite automata. In the unary case, the known upper bound for square is 2n − 1, and we prove that each value in the range from 1 to 2n − 1 may be attained by the state complexity of the square of a unary language with state complexity n whenever n ≥ 5.
Research supported by grant APVV-0035-10.
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.
References
Brzozowski, J., Leiss, E.: On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10, 19–35 (1980)
Čevorová, K.: Kleene star on unary regular languages. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 277–288. Springer, Heidelberg (2013)
Fellah, A., Jürgensen, H., Yu, S.: Constructions for alternating finite automata. Int. J. Comput. Math. 35, 117–132 (1990)
Jirásek, J., Jirásková, G., Szabari, A.: State complexity of concatenation and complementation. Internat. J. Found. Comput. Sci. 16, 511–529 (2005)
Jirásková, G.: State complexity of some operations on binary regular languages. Theoret. Comput. Sci. 330, 287–298 (2005)
Jirásková, G.: Descriptional complexity of operations on alternating and boolean automata. In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 196–204. Springer, Heidelberg (2012)
Leiss, E.: Succinct representation of regular languages by boolean automata. Theoret. Comput. Sci. 13, 323–330 (1981)
Leiss, E.: On generalized language equations. Theoret. Comput. Sci. 14, 63–77 (1981)
Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Math. Doklady 11, 1373–1375 (1970)
Nicaud, C.: Average state complexity of operations on unary automata. In: Kutyłowski, M., Wierzbicki, T., Pacholski, L. (eds.) MFCS 1999. LNCS, vol. 1672, pp. 231–240. Springer, Heidelberg (1999)
Rampersad, N.: The state complexity of L 2 and L k. Inform. Process. Lett. 98, 231–234 (2006)
Sipser, M.: Introduction to the theory of computation. PWS Publishing Company, Boston (1997)
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 41–110. Springer, Heidelberg (1997)
Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315–328 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Čevorová, K., Jirásková, G., Krajňáková, I. (2014). On the Square of Regular Languages. In: Holzer, M., Kutrib, M. (eds) Implementation and Application of Automata. CIAA 2014. Lecture Notes in Computer Science, vol 8587. Springer, Cham. https://doi.org/10.1007/978-3-319-08846-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-08846-4_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08845-7
Online ISBN: 978-3-319-08846-4
eBook Packages: Computer ScienceComputer Science (R0)