Standard

State complexity of cyclic shift. / Jirásková, Galina; Okhotin, Alexander.

In: RAIRO - Theoretical Informatics and Applications, Vol. 42, No. 2, 01.04.2008, p. 335-360.

Research output: Contribution to journal › Article › peer-review

Harvard

Jirásková, G & Okhotin, A 2008, 'State complexity of cyclic shift', RAIRO - Theoretical Informatics and Applications, vol. 42, no. 2, pp. 335-360. https://doi.org/10.1051/ita:2007038

APA

Jirásková, G., & Okhotin, A. (2008). State complexity of cyclic shift. RAIRO - Theoretical Informatics and Applications, 42(2), 335-360. https://doi.org/10.1051/ita:2007038

Vancouver

Jirásková G, Okhotin A. State complexity of cyclic shift. RAIRO - Theoretical Informatics and Applications. 2008 Apr 1;42(2):335-360. https://doi.org/10.1051/ita:2007038

Author

Jirásková, Galina ; Okhotin, Alexander. / State complexity of cyclic shift. In: RAIRO - Theoretical Informatics and Applications. 2008 ; Vol. 42, No. 2. pp. 335-360.

BibTeX

@article{b89c08aac6b44893a2db6e84d8307778,
title = "State complexity of cyclic shift",
abstract = "The cyclic shift of a language , defined as =, 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, which shows that the state complexity of cyclic shift is for alphabets with at least 4 letters. For 2- and 3-letter alphabets, we prove state complexity. We also establish a tight 2n lower bound for the nondeterministic state complexity of this operation using a binary alphabet.",
keywords = "Cyclic shift, Descriptional complexity, Finite automata",
author = "Galina Jir{\'a}skov{\'a} and Alexander Okhotin",
year = "2008",
month = apr,
day = "1",
doi = "10.1051/ita:2007038",
language = "English",
volume = "42",
pages = "335--360",
journal = "RAIRO - Theoretical Informatics and Applications",
issn = "0988-3754",
publisher = "EDP Sciences",
number = "2",

}

RIS

TY - JOUR

T1 - State complexity of cyclic shift

AU - Jirásková, Galina

AU - Okhotin, Alexander

PY - 2008/4/1

Y1 - 2008/4/1

N2 - The cyclic shift of a language , defined as =, 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, which shows that the state complexity of cyclic shift is for alphabets with at least 4 letters. For 2- and 3-letter alphabets, we prove state complexity. We also establish a tight 2n lower bound for the nondeterministic state complexity of this operation using a binary alphabet.

AB - The cyclic shift of a language , defined as =, 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, which shows that the state complexity of cyclic shift is for alphabets with at least 4 letters. For 2- and 3-letter alphabets, we prove state complexity. We also establish a tight 2n lower bound for the nondeterministic state complexity of this operation using a binary alphabet.

KW - Cyclic shift

KW - Descriptional complexity

KW - Finite automata

UR - http://www.scopus.com/inward/record.url?scp=41549087893&partnerID=8YFLogxK

U2 - 10.1051/ita:2007038

DO - 10.1051/ita:2007038

M3 - Article

AN - SCOPUS:41549087893

VL - 42

SP - 335

EP - 360

JO - RAIRO - Theoretical Informatics and Applications

JF - RAIRO - Theoretical Informatics and Applications

SN - 0988-3754

IS - 2

ER -

ID: 41141610