How many reduced transducers are there?

Question

Let’s define a transducer as a $5$-tuple $(Q, A, B, \phi, \psi)$, where $Q$ is the collection of states, $A$ is the input alphabet, $\phi: Q\times A \to Q$ is the transition function and $\psi: Q \times A \to B$ is the output function.

Any transducer defines a transducer function $\overline{\psi}: Q\times A^* \to B^*$ described by the following recurrence:

$\overline{\psi}(q, \Lambda) = \Lambda$, where $\Lambda$ is the empty word.

$\overline{\psi}(q, a \alpha) = \psi(q, a) \overline{\psi}(\phi(q, a), \alpha)$, where $a \in A$, $\alpha \in A^*$.

We call $q_1, q_2 \in Q$ distinguishable iff $\exists \alpha \in A^*$ such that $\overline{\psi}(q_1, \alpha) \neq \overline{\psi}(q_2, \alpha)$.

We call a transducer reduced iff any two its states are distinguishable.

Suppose $n_t(k, m, n)$ is the number of distinct reduced deterministic transducers with input with $k$ states, $m$-symbol input alphabet and $n$-symbol output alphabet. Is there some sort of explicit formula (or at least asymptotic) for $n_t(k, m, n)$?

I managed to derive only the following three particular cases:

$n_t(1, m, n) = n^m$

Proof:

As there is only one state, the transducer is fully determined by its output function. And it is in this case just a map from the input alphabet to the output one.

$n_t(2, m, n) = (4n)^m(n^m - 1)$

Proof:

Suppose, $q_1$ and $q_2$ are the only two states of our transducer. It is not hard to see, that in this particular case they are not distinguishable iff $\psi(q_1, a) = \psi(q_2, a)$. Thus there are $n^m(n^m - 1)$ possible versions of $\psi$, that result in our transducer being reduced. And there are $4^m$ ways to chose $\phi$.

$n_t(k, m, 1) = 0$ $\forall k \geq 2$

Proof:

If $B$ is one-element, then $\overline{\psi}(q, \alpha)$ is determined only by the length of $\alpha$.

Answer 1

Generalising the argument for $n_t(2, m, n)$, we can say that two states $q_i$ and $q_j$ are similar, denoted $q_i \sim q_j$, if $\forall a \in A: \psi(q_i, a) = \psi(q_j, a)$. If $q_i \not\sim q_j$ then $q_i$ and $q_j$ are distinguishable by a one-symbol word.

• If all of the states are similar, none of them are distinguishable because $\overline{\psi}(q, w)$ depends solely on $w$.
• If none of the states are similar, the transducer is reduced. (Why not irreducible?)

For $k\le 2$ one of those two scenarios must occur. For $k > 2$ we can have situations with non-trivial non-universal clusters of similar states. We define

$$\overline\phi(q, w) = \begin{cases}q & \textrm{if } w = \Lambda \\ \overline\phi(\phi(q, a), \alpha) & \textrm{if } w = a\alpha \end{cases}$$

Then two similar states $q_i \sim q_j$ are distinguishable iff there is a word $w$ such that $\overline\phi(q_i, w) \not\sim \overline\phi(q_j, w)$.

From a computational point of view, the following algorithm serves to verify reducibility:

1. Partition the states into disjoint sets $P_{1,1}, \ldots, P_{1,p_1}$ where two sets are in the same part iff there are similar. Set $s := 1$.
2. Refine the partition: if two states in $P_{s,i}$ have a symbol $a$ for which $\phi$ maps them to elements of different parts in the partition at level $s$, then at level $s+1$ we split $P_{s,i}$ to place those two states in different parts.
3. If the refinement leads to a partition where every state is in a singleton part, the transducer is reduced. We've finished.
4. If the refinement makes no changes, we've finished. Two states in the same part are indistinguishable.
5. Otherwise increment $s$ and go to step 2.

---

We can apply this fairly straightforwardly for $k=3$.

• There are $27^m n^m(n^m-1)(n^m-2)$ transducers with no similar states.
• If we have $q_1 \sim q_2 \not\sim q_3$ then we must distinguish $q_1$ and $q_2$ by mapping one of them to $q_3$ and the other to $\{q_1, q_2\}$ for some symbol. There are $n^m$ options for $\lambda a.\psi(q_1, a)=\lambda a.\psi(q_2, a)$ and $n^m-1$ options for $\lambda a.\psi(q_3, a)$. There are $3^m$ options for $\lambda q.\phi(q_3, q)$. For the other two transition functions there are $\sum_{i=1}^m 5^{i-1} 4 \cdot 9^{m-i}$ possibilities (the first discrepancy is at symbol $i$; the symbols up to then have $2^2 + 1^2$ options each; the symbols after are free; and at symbol $i$ we have to choose which state moves to $q_3$ and which of $q_i$ or $q_2$ the other moves to). And we have a factor of $3$ for the choice of the odd state out.

Total: $27^m n^m(n^m-1)(n^m-2) + 3^{m+1} (9^m - 5^m) n^m(n^m-1)$ $= 3^m n^m(n^m-1)[9^m (n^m+1) - 3 \cdot 5^m]$

For higher $k$ the sum needs to be over all possible ways of refining the partition.

---

As for asymptotics: there are $(kn)^{km}$ transducers, and $k^{km}(n^m)^\underline{k}$ transducers in which no two states are similar, so for $k \ll n^m$ the reducible transducers are negligible. In that case, it makes more sense to ask about the asymptotics of the reducible transducers, for which the upper bound $k^{km}(n^{km} - (n^m)^\underline{k})$ has a first order approximation of $k^{km} \cdot \tfrac12 k(k-1) n^{k(m-1)}$.