# State complexity of cyclic shift

Galina Jirásková; Alexander Okhotin

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

- Volume: 42, Issue: 2, page 335-360
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topJirásková, Galina, and Okhotin, Alexander. "State complexity of cyclic shift." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 42.2 (2008): 335-360. <http://eudml.org/doc/246037>.

@article{Jirásková2008,

abstract = {The cyclic shift of a language $L$, defined as $\textsc \{shift\}(L)$=$ \lbrace vu \: | \: uv \in L \rbrace $, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov’s pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! $\cdot $ 2$^\{(n-1)(n-2)\}$, which shows that the state complexity of cyclic shift is $2^\{n^2 + n \log n - O(n)\}$ for alphabets with at least 4 letters. For 2- and 3-letter alphabets, we prove $2^\{\Theta (n^2)\}$ state complexity. We also establish a tight 2n$^2+1$ lower bound for the nondeterministic state complexity of this operation using a binary alphabet.},

author = {Jirásková, Galina, Okhotin, Alexander},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {finite automata; descriptional complexity; cyclic shift},

language = {eng},

number = {2},

pages = {335-360},

publisher = {EDP-Sciences},

title = {State complexity of cyclic shift},

url = {http://eudml.org/doc/246037},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Jirásková, Galina

AU - Okhotin, Alexander

TI - State complexity of cyclic shift

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2008

PB - EDP-Sciences

VL - 42

IS - 2

SP - 335

EP - 360

AB - The cyclic shift of a language $L$, defined as $\textsc {shift}(L)$=$ \lbrace vu \: | \: uv \in L \rbrace $, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov’s pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! $\cdot $ 2$^{(n-1)(n-2)}$, which shows that the state complexity of cyclic shift is $2^{n^2 + n \log n - O(n)}$ for alphabets with at least 4 letters. For 2- and 3-letter alphabets, we prove $2^{\Theta (n^2)}$ state complexity. We also establish a tight 2n$^2+1$ lower bound for the nondeterministic state complexity of this operation using a binary alphabet.

LA - eng

KW - finite automata; descriptional complexity; cyclic shift

UR - http://eudml.org/doc/246037

ER -

## References

top- [1] A.V. Aho, J.D. Ullman and M. Yannakakis, On notions of information transfer in VLSI circuits, in Proceedings of 15th ACM STOC, ACM (1983) 133–139.
- [2] J.-C. Birget, Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43 (1992) 185–190. Zbl0763.68048MR1187185
- [3] J.-C. Birget, Partial orders on words, minimal elements of regular languages, and state complexity. Theor. Comput. Sci. 119 (1993) 267–291. Zbl0786.68071MR1244294
- [4] J.-C. Birget, The state complexity of $\overline{{\Sigma}^{*}\overline{L}}$ and its connection with temporal logic. Inform. Process. Lett. 58 (1996) 185–188. MR1413639
- [5] C. Câmpeanu, K. Salomaa and S. Yu, Tight lower bound for the state complexity of shuffle of regular languages. J. Autom. Lang. Comb. 7 (2002) 303–310. Zbl1033.68057MR1957693
- [6] M. Domaratzki, State complexity and proportional removals. J. Autom. Lang. Comb. 7 (2002) 455–468. Zbl1095.68605MR1990451
- [7] M. Domaratzki, D. Kisman and J. Shallit, On the number of distinct languages accepted by finite automata with $n$ states. J. Autom. Lang. Comb. 7 (2002) 469–486. Zbl1137.68421MR1990452
- [8] V. Geffert, Magic numbers in the state hierarchy of finite automata, Mathematical Foundations of Computer Science, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006, Springer, Berlin. Lect. Notes Comput. Sci. 4162 (2006) 312–423. Zbl1132.68444MR2298196
- [9] I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett. 59 (1996) 75–77. Zbl0900.68313MR1409955
- [10] M. Holzer and M. Kutrib, Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14 (2003) 1087–1102. Zbl1101.68657MR2031104
- [11] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979). Zbl0426.68001MR645539
- [12] M. Hricko, G. Jirásková and A. Szabari, Union and intersection of regular languages and descriptional complexity, in Proceedings of DCFS 2005, Como, Italy, June 30–July 2, 2005, 170–181.
- [13] J. Hromkovič, Communication Complexity and Parallel Computing. Springer-Verlag, Berlin, Heidelberg (1997). Zbl0873.68098MR1442518
- [14] J. Hromkovič, Descriptional complexity of finite automata: concepts and open problems. J. Autom. Lang. Comb. 7 (2002) 519–531. Zbl1094.68576MR1990455
- [15] K. Iwama, A. Matsuura and M. Paterson, A family of NFAs which need ${2}^{n}-\alpha $ deterministic states. Theor. Comput. Sci. 301 (2003), 451–462. Zbl1022.68067MR1975240
- [16] G. Jirásková, State complexity of some operations on binary regular languages. Theor. Comput. Sci. 330 (2005) 287–298. Zbl1078.68088MR2114874
- [17] A.N. Maslov, Estimates of the number of states of finite automata. Soviet Mathematics Doklady 11 (1970) 1373–1375. Zbl0222.94064MR274221
- [18] A.N. Maslov, Cyclic shift operation for languages. Probl. Inf. Transm. 9 (1973) 333–338. MR334597
- [19] T. Oshiba, Closure property of the family of context-free languages under the cyclic shift operation. T. IECE 55D (1972) 119–122. MR478788
- [20] A. Salomaa, D. Wood and S. Yu, On the state complexity of reversals of regular languages. Theor. Comput. Sci. 320 (2004) 315–329. Zbl1068.68078MR2064305
- [21] A. Salomaa, K. Salomaa and S. Yu, State complexity of combined operations. Theor. Comput. Sci. 383 (2007) 140–152. Zbl1124.68056MR2350788
- [22] S. Yu, State complexity: recent results and open problems. Fund. Inform. 64 (2005) 471–480. Zbl1102.68076MR2347575
- [23] S. Yu, Q. Zhuang and K. Salomaa, The state complexity of some basic operations on regular languages. Theor. Comput. Sci. 125 (1994) 315–328. Zbl0795.68112MR1264137
- [24] L. van Zijl, Magic numbers for symmetric difference NFAs. Int. J. Found. Comput. Sci. 16 (2005) 1027–1038. Zbl1090.68065MR2174338

## NotesEmbed ?

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