OFFSET
1,2
COMMENTS
For a word w, cyc(w) refers to the set of all cyclic shifts of w. Thus cyc(ate) = {ate, tea, eat}.
For a language (that is, a set of words), cyc(L) is the union of cyc(w) over all w in L.
The deterministic state complexity of a regular language L is the smallest number of states needed by a deterministic finite automaton to accept L.
LINKS
G. Jirásková and A. Okhotin, State complexity of cyclic shift, RAIRO-Theor. Inf. Appl. 42 (2008), 335-360. See table on page 357.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Mar 18 2019
STATUS
approved