RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

| Abstract | PDF (691.4 KB) | References |

RAIRO-Theor. Inf. Appl. 42, 335-360 (2008)
DOI: 10.1051/ita:2007038

State complexity of cyclic shift

Galina Jirásková¹ and Alexander Okhotin²

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

(Received December 6, 2006. Accepted August 17, 2007 Published online 13 December 2007.)

Abstract
The cyclic shift of a language L, defined as $\textsc{shift}(L)$ = $\ensuremath{ \{ vu \: \vert \: uv \in 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)! $\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²+1 lower bound for the nondeterministic state complexity of this operation using a binary alphabet.

Mathematics Subject Classification. 68Q45, 68Q19

Key words: Finite automata -- descriptional complexity -- cyclic shift

© EDP Sciences 2007