login
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
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
Lucas B. Vieira and Costantino Budroni, Temporal correlations in the simplest measurement sequences, Quantum 6 p. 623 (2022).
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.
Cf. A143324 for psi(k,n).
Sequence in context: A293131 A120983 A124810 * A329056 A191577 A282901
KEYWORD
nonn
AUTHOR
Lucas B. Vieira, Mar 02 2024
STATUS
approved