Issue |
RAIRO-Theor. Inf. Appl.
Volume 42, Number 2, April-June 2008
|
|
---|---|---|
Page(s) | 335 - 360 | |
DOI | https://doi.org/10.1051/ita:2007038 | |
Published online | 13 December 2007 |
State complexity of cyclic shift
1
Mathematical Institute, Slovak Academy of Sciences,
Grešákova 6, 040 01 Košice, Slovakia;
jiraskov@saske.sk
2
Academy of Finland
Department of Mathematics, University of Turku, Turku 20014, Finland;
alexander.okhotin@utu.fi
Received:
6
December
2006
Accepted:
17
August
2007
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 state complexity.
We also establish a tight 2n2+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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.