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

Abstract

top
The cyclic shift of a language L , defined as s h i f t ( L ) = { v u | u v ∈ L } , 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)! · 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 Θ ( 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.

How to cite

top

Jirá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. [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. [2] J.-C. Birget, Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43 (1992) 185–190. Zbl0763.68048MR1187185
  3. [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. [4] J.-C. Birget, The state complexity of Σ * L ¯ ¯ and its connection with temporal logic. Inform. Process. Lett. 58 (1996) 185–188. MR1413639
  5. [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. [6] M. Domaratzki, State complexity and proportional removals. J. Autom. Lang. Comb. 7 (2002) 455–468. Zbl1095.68605MR1990451
  7. [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. [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. [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. [10] M. Holzer and M. Kutrib, Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14 (2003) 1087–1102. Zbl1101.68657MR2031104
  11. [11] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979). Zbl0426.68001MR645539
  12. [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. [13] J. Hromkovič, Communication Complexity and Parallel Computing. Springer-Verlag, Berlin, Heidelberg (1997). Zbl0873.68098MR1442518
  14. [14] J. Hromkovič, Descriptional complexity of finite automata: concepts and open problems. J. Autom. Lang. Comb. 7 (2002) 519–531. Zbl1094.68576MR1990455
  15. [15] K. Iwama, A. Matsuura and M. Paterson, A family of NFAs which need 2 n - α deterministic states. Theor. Comput. Sci. 301 (2003), 451–462. Zbl1022.68067MR1975240
  16. [16] G. Jirásková, State complexity of some operations on binary regular languages. Theor. Comput. Sci. 330 (2005) 287–298. Zbl1078.68088MR2114874
  17. [17] A.N. Maslov, Estimates of the number of states of finite automata. Soviet Mathematics Doklady 11 (1970) 1373–1375. Zbl0222.94064MR274221
  18. [18] A.N. Maslov, Cyclic shift operation for languages. Probl. Inf. Transm. 9 (1973) 333–338. MR334597
  19. [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. [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. [21] A. Salomaa, K. Salomaa and S. Yu, State complexity of combined operations. Theor. Comput. Sci. 383 (2007) 140–152. Zbl1124.68056MR2350788
  22. [22] S. Yu, State complexity: recent results and open problems. Fund. Inform. 64 (2005) 471–480. Zbl1102.68076MR2347575
  23. [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. [24] L. van Zijl, Magic numbers for symmetric difference NFAs. Int. J. Found. Comput. Sci. 16 (2005) 1027–1038. Zbl1090.68065MR2174338

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.