|
%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
| 