State complexity of cyclic shift

¹ Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia; jiraskov@saske.sk
² Academy of Finland Department of Mathematics, University of Turku, Turku 20014, Finland; alexander.okhotin@utu.fi

Received: 6 December 2006
Accepted: 17 August 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 2^{n2+ nlogn - O(n)} for alphabets with at least 4 letters. For 2- and 3-letter alphabets, we prove state complexity. We also establish a tight 2n²+1 lower bound for the nondeterministic state complexity of this operation using a binary alphabet.