State complexity of cyclic shift

Galina Jirásková; Alexander Okhotin

RAIRO - Theoretical Informatics and Applications (2007)

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

Abstract

top
The cyclic shift of a language L, defined as SHIFT(L) = {vu | uv ∈ 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 2n2+ nlogn - 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 2n2+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 42.2 (2007): 335-360. <http://eudml.org/doc/92875>.

@article{Jirásková2007,
abstract = { The cyclic shift of a language L, defined as SHIFT(L) = \{vu | uv ∈ 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 2n2+ nlogn - 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 2n2+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},
keywords = {Finite automata; descriptional complexity; cyclic shift},
language = {eng},
month = {12},
number = {2},
pages = {335-360},
publisher = {EDP Sciences},
title = {State complexity of cyclic shift},
url = {http://eudml.org/doc/92875},
volume = {42},
year = {2007},
}

TY - JOUR
AU - Jirásková, Galina
AU - Okhotin, Alexander
TI - State complexity of cyclic shift
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/12//
PB - EDP Sciences
VL - 42
IS - 2
SP - 335
EP - 360
AB - The cyclic shift of a language L, defined as SHIFT(L) = {vu | uv ∈ 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 2n2+ nlogn - 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 2n2+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/92875
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.  
  3. J.-C. Birget, Partial orders on words, minimal elements of regular languages, and state complexity. Theor. Comput. Sci.119 (1993) 267–291.  
  4. J.-C. Birget, The state complexity of Σ * L ¯ ¯ and its connection with temporal logic. Inform. Process. Lett.58 (1996) 185–188.  
  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.  
  6. M. Domaratzki, State complexity and proportional removals. J. Autom. Lang. Comb.7 (2002) 455–468.  
  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.  
  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.  
  9. I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett.59 (1996) 75–77.  
  10. M. Holzer and M. Kutrib, Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci.14 (2003) 1087–1102.  
  11. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979).  
  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).  
  14. J. Hromkovič, Descriptional complexity of finite automata: concepts and open problems. J. Autom. Lang. Comb.7 (2002) 519–531.  
  15. K. Iwama, A. Matsuura and M. Paterson, A family of NFAs which need 2n - α deterministic states. Theor. Comput. Sci.301 (2003), 451–462.  
  16. G. Jirásková, State complexity of some operations on binary regular languages. Theor. Comput. Sci.330 (2005) 287–298.  
  17. A.N. Maslov, Estimates of the number of states of finite automata. Soviet Mathematics Doklady11 (1970) 1373–1375.  
  18. A.N. Maslov, Cyclic shift operation for languages. Probl. Inf. Transm.9 (1973) 333–338.  
  19. T. Oshiba, Closure property of the family of context-free languages under the cyclic shift operation. T. IECE55D (1972) 119–122.  
  20. A. Salomaa, D. Wood and S. Yu, On the state complexity of reversals of regular languages. Theor. Comput. Sci.320 (2004) 315–329.  
  21. A. Salomaa, K. Salomaa and S. Yu, State complexity of combined operations. Theor. Comput. Sci.383 (2007) 140–152.  
  22. S. Yu, State complexity: recent results and open problems. Fund. Inform.64 (2005) 471–480.  
  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.  
  24. L. van Zijl, Magic numbers for symmetric difference NFAs. Int. J. Found. Comput. Sci.16 (2005) 1027–1038.  

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.