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

1, 5, 108, 20237, 56817428

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

Table of n, a(n) for n=1..5.

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

Sequence in context: A318986 A220549 A210904 * A048564 A139971 A305095

Adjacent sequences: A306987 A306988 A306989 * A306991 A306992 A306993

Keyword

nonn,more

Author

Jeffrey Shallit, Mar 18 2019

Status

approved