%I #8 Mar 19 2019 00:11:55

%S 1,5,108,20237,56817428

%N Worst-case of deterministic state complexity for cyclic shift of binary language with state complexity n.

%C For a word w, cyc(w) refers to the set of all cyclic shifts of w. Thus cyc(ate) = {ate, tea, eat}.

%C For a language (that is, a set of words), cyc(L) is the union of cyc(w) over all w in L.

%C The deterministic state complexity of a regular language L is the smallest number of states needed by a deterministic finite automaton to accept L.

%H G. Jirásková and A. Okhotin, <a href="http://www.numdam.org/article/ITA_2008__42_2_335_0.pdf">State complexity of cyclic shift</a>, RAIRO-Theor. Inf. Appl. 42 (2008), 335-360. See table on page 357.

%K nonn,more

%O 1,2

%A _Jeffrey Shallit_, Mar 18 2019