Abstract
We prove that the cyclic shift of a prefix-free language represented by a minimal complete n-state deterministic finite automaton is recognized by a deterministic automaton of at most (2n − 3)n − 2 states. We also show that this bound is tight in the quaternary case, and that it cannot be met by using any smaller alphabet. In the ternary and binary cases, we still get exponential lower bounds.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Birget, J.-C.: Intersection and union of regular languages and state complexity. Inform. Process. Letters 43, 185–190 (1992)
Gruber, H., Holzer, M.: Language operations with regular expressions of polynomial size. Theoret. Comput. Sci. 410, 3281–3289 (2009)
Han, Y.-S., Salomaa, K., Wood, D.: Operational state complexity of prefix-free regular languages. In: Automata, Formal Languages, and Related Topics, pp. 99–115. University of Szeged, Hungary (2009)
Han, Y.-S., Salomaa, K., Wood, D.: Nondeterministic state complexity of basic operations for prefix-free regular languages. Fund. Inform. 90, 93–106 (2009)
Han, Y.-S., Salomaa, K., Yu, S.: State complexity of combined operations for prefix-free regular languages. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 398–409. Springer, Heidelberg (2009)
Jirásková, G., Krausová, M.: Complexity in prefix-free regular languages. In: McQuillan, I., Pighizzini, G., Trost, B. (eds.) Proc. 12th DCFS, pp. 236–244. University of Saskatchewan, Saskatoon (2010)
Jirásková, G., Okhotin, A.: State complexity of cyclic shift. Theor. Inform. Appl. 42, 335–360 (2008)
Krausová, M.: Prefix-free regular languages: Closure properties, difference, and left quotient. In: Kotásek, Z., Bouda, J., Černá, I., Sekanina, L., Vojnar, T., Antoš, D. (eds.) MEMICS 2011. LNCS, vol. 7119, pp. 114–122. Springer, Heidelberg (2012)
Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Math. Dokl. 11, 1373–1375 (1970)
Maslov, A.N.: The cyclic shift of languages. Problemy Peredači Informacii 9, 81–87 (1973) (Russian)
Oshiba, T.: Closure property of the family of context-free languages under the cyclic shift operation. Electron. Commun. Japan 55, 119–122 (1972)
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, ch. 2, 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
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jirásek, J., Jirásková, G. (2013). Cyclic Shift on Prefix-Free Languages. In: Bulatov, A.A., Shur, A.M. (eds) Computer Science – Theory and Applications. CSR 2013. Lecture Notes in Computer Science, vol 7913. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38536-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-38536-0_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38535-3
Online ISBN: 978-3-642-38536-0
eBook Packages: Computer ScienceComputer Science (R0)