|
| |
|
|
A370821
|
|
Number of minimal deterministic Mealy automata with n states outputting ternary strings
|
|
1
|
|
|
|
3, 12, 54, 210, 798, 2850, 10038, 34410, 116406, 388362, 1283430, 4203786, 13675038, 44211570, 142202574, 455299242, 1451997726, 4614253122, 14617620726, 46177325994, 145505603694, 457437342546, 1435074324006, 4493508791754, 14045385985902
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
a(n) counts the minimal number of ternary words w = uv, with |w| = n, such that u is an irreducible prefix and v a primitive word. This defines a minimal "pattern", written as "u(v)", describing the behavior of a minimal n-state deterministic Mealy automaton outputting a string from a ternary alphabet, where u is the transient output, and v the cyclic output, possibly truncated. Used in the definition of the Deterministic Complexity (DC) of strings (Vieira and Budroni, 2022).
|
|
|
REFERENCES
|
M. Domaratzki, D. Kisman, and J. Shallit, On the number of distinct languages accepted by finite automata with n states, J. Autom. Lang. Combinat. 7 (2002) 4-18, Section 6, f_1(n).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = psi(3, n) + Sum_{i=1..n-1} (3-1)*3^(i-1)*psi(3, n-i), where psi(k,n) is the number of primitive words of length n on a k-letter alphabet (Cf. A143324).
|
|
|
EXAMPLE
|
a(1) = 3 as there are only 3 deterministic Mealy automata with 1 state producing ternary words, corresponding to the 3 patterns (0), (1) and (2), generating the strings w=0^L, w=1^L, and w=2^L for L >= 1.
a(2) = 12, since there are 12 minimal ternary patterns: (01), 0(1), (02), 0(2), (10), 1(0), (12), 1(2), (20), 2(0), (21), 2(1).
E.g.: The ternary string w = 000120120 can be described by the pattern 00(012), where the parentheses indicate the repeating part, up to truncation. This pattern is minimal, with 5 symbols (ignoring the parentheses). It describes the behavior of a minimal deterministic Mealy automaton producing the string w, leading to its Deterministic Complexity (DC) to be DC(w) = 5.
|
|
|
MATHEMATICA
|
NumPrimitiveWords[k_, n_] := Sum[MoebiusMu[d] k^(n/d), {d, Divisors[n]}];
a[n_] := NumPrimitiveWords[3, n] + Sum[(3 - 1) 3^(i - 1) NumPrimitiveWords[3, n - i], {i, 1, n - 1}]
|
|
|
CROSSREFS
|
Cf. A059412 for the case of binary strings.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
