|
| |
|
|
A370489
|
|
Deterministic complexity of binary strings, in shortlex order.
|
|
1
|
|
|
|
1, 1, 1, 2, 2, 1, 1, 3, 2, 2, 2, 2, 3, 1, 1, 4, 3, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 3, 4, 1, 1, 5, 4, 4, 3, 3, 4, 3, 3, 3, 2, 4, 4, 3, 4, 2, 2, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 1, 1, 6, 5, 5, 4, 4, 5, 4, 4, 3, 3, 5, 4, 4, 5, 3, 3, 4, 3, 5, 5, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
a(n) = DC(w[n]), where w[n] is the n-th binary string in shortlex order: 0, 1, 00, 01, 10, 11, 000, 001, .... (row n-1 of A076478).
The Deterministic Complexity (DC) of a string w is the minimum number of states in a deterministic Mealy automaton outputting the string w. Alternatively, DC(w) = |u|+|v| for the smallest (possibly empty) u and primitive word v, such that w = trunc(uv^k,|w|) for some k >= 1, where trunc(x,L) truncates the word x to length L.
1..L each appear at least twice in row L since DC(0^i 1^(L-i)) = DC(1^i 0^(L-i)) = i+1 for i = 0..L-1. - Michael S. Branicky, Mar 03 2024
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
For n = 1, w[1] = 0, and DC(w[1]) = 1. The minimal deterministic Mealy automaton outputting w[1] has a single state, transitioning to itself and outputting 0.
For n = 36, w[36] = 00101, and DC(w[36]) = 3. The minimal deterministic Mealy automaton has 3 states: transitions 1->2 and 2->3 output 0, and 3->2 outputs 1.
|
|
|
MATHEMATICA
|
(* e.g. DC[{0, 0, 1, 0, 1}] = 3 *)
DC[seq_] := With[{L = Length[seq]}, Do[If[With[{c = dc - t}, Take[Flatten[{Take[seq, t], ConstantArray[Take[Drop[seq, t], c], Ceiling[(L - t)/c]]}], L]] == seq, Return[dc]], {dc, 0, L}, {t, 0, dc - 1}]];
a[n_] := DC[Rest[IntegerDigits[n + 1, 2]]];
(* Table for all sequences up to length 10 *)
With[{L = 10}, Table[a[n], {n, 2*(2^L-1)}]]
|
|
|
PROG
|
(Python)
def DC(w): return next(dc for dc in range(1, len(w)+1) for i in range(dc) if w == (w[:i]+w[i:dc]*(1+(len(w)-i)//(dc-i)))[:len(w)])
def a(n): return DC(bin(n+1)[3:])
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
