login
Number of minimal deterministic Mealy automata with n states outputting ternary strings
1

%I #12 Mar 25 2024 21:37:17

%S 3,12,54,210,798,2850,10038,34410,116406,388362,1283430,4203786,

%T 13675038,44211570,142202574,455299242,1451997726,4614253122,

%U 14617620726,46177325994,145505603694,457437342546,1435074324006,4493508791754,14045385985902

%N Number of minimal deterministic Mealy automata with n states outputting ternary strings

%C 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).

%D 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).

%H Lucas B. Vieira and Costantino Budroni, <a href="https://doi.org/10.22331/q-2022-01-18-623">Temporal correlations in the simplest measurement sequences</a>, Quantum 6 p. 623 (2022).

%F 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).

%e 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.

%e 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 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.

%t NumPrimitiveWords[k_, n_] := Sum[MoebiusMu[d] k^(n/d), {d, Divisors[n]}];

%t a[n_] := NumPrimitiveWords[3, n] + Sum[(3 - 1) 3^(i - 1) NumPrimitiveWords[3, n - i], {i, 1, n - 1}]

%Y Cf. A059412 for the case of binary strings.

%Y Cf. A143324 for psi(k,n).

%K nonn

%O 1,1

%A _Lucas B. Vieira_, Mar 02 2024