login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306990 Worst-case of deterministic state complexity for cyclic shift of binary language with state complexity n. 0
1, 5, 108, 20237, 56817428 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 6 05:39 EDT 2022. Contains 355108 sequences. (Running on oeis4.)