*Proof.* Given an ideal $\mathfrak{a} \subseteq \mathcal{O}_K$, we construct in polynomial time an $\mathcal{O}_K$-WA that is state-minimal if and only if $\mathfrak{a}$ is not principal.

By Lemma 23, compute first, in polynomial time a size-2 generating set $\{x, y\}$ of $\mathfrak{a}$, so that $\mathfrak{a} = x\mathcal{O}_K + y\mathcal{O}_K$. Compute moreover, again in polynomial time, $\mathfrak{a}^{-1}$ [42, Proposition 13] and the isomorphism $\mathfrak{a} \oplus \mathfrak{a}^{-1} \cong \mathcal{O}_K \oplus \mathcal{O}_K$ (as shown to be possible in the proof of Lemma 23). Let $\binom{x_1}{x_2}$ and $\binom{y_1}{y_2}$ be the respective images of $x$ and $y$ under this isomorphism. Construct finally the $\mathcal{O}_K$-WA $\mathcal{A}$ on the alphabet $\Sigma = \{a, b\}$ depicted in Figure 2.

<figure><img src="image_21.png" /><figcaption>Figure 2: An $\mathcal{O}_K$-WA encoding the ideal $\mathfrak{a}$.</figcaption></figure>

Let $L \in \mathcal{O}_K\langle\langle a, b \rangle\rangle$ be the language recognized by $\mathcal{A}$. Writing $L_1$ and $L_2$ for the languages recognized by $\mathcal{A}$ starting from states 1 and 2, we have

$$a^{-1}L = x_1L_1 + x_2L_2$$

$$b^{-1}L = y_1L_1 + y_2L_2$$

Moreover $L_1$ is zero on $b\{a, b\}^*$ while $L_2$ is zero on $a\{a, b\}^*$, hence $L_1$ and $L_2$ are linearly independent and

$$\mathcal{O}_K \cdot (x_1L_1 + x_2L_2) + \mathcal{O}_K \cdot (y_1L_1 + y_2L_2) \cong \mathfrak{a}$$

Note that $L$ is zero on words of odd length, so that $\mathcal{O}_K \cdot L \cap (\mathcal{O}_K \cdot a^{-1}L + \mathcal{O}_K \cdot b^{-1}L) = \{0\}$. Furthermore, $w^{-1}L \in \mathcal{O}_K \cdot L$ for any $w \in \{aa, ab, ba, bb\}$. It follows that the module spanned by the rows of the Hankel matrix of $L$ is the direct sum

$$\mathcal{O}_K \cdot L \oplus [\mathcal{O}_K \cdot (x_1L_1 + x_2L_2) + \mathcal{O}_K \cdot (y_1L_1 + y_2L_2)]$$

which is in turn isomorphic to $\mathcal{O}_K \oplus \mathfrak{a}$. Therefore, $\text{Min } L$ has rank 2.

We now show that this module, $\text{Min } L$, is saturated into $\mathcal{O}_K\langle\langle a, b \rangle\rangle$. We have that $\text{Min } L \subseteq \mathcal{O}_K \cdot L \oplus \mathcal{O}_K \cdot L_1 \oplus \mathcal{O}_K \cdot L_2$. Now $\mathcal{O}_K \cdot L \oplus \mathcal{O}_K \cdot L_1 \oplus \mathcal{O}_K \cdot L_2$ is saturated into $\mathcal{O}_K\langle\langle a, b \rangle\rangle$: if $\lambda f = \alpha L + \beta L_1 + \gamma L_2$ where $\lambda, \alpha, \beta, \gamma \in \mathcal{O}_K$ and $\lambda$ is non-zero, then it is easy to see that $f = f(\varepsilon)L + f(a)L_1 + f(b)L_2$. We therefore only need to show that $\text{Min } L$ is saturated into $\mathcal{O}_K \cdot L \oplus \mathcal{O}_K \cdot L_1 \oplus \mathcal{O}_K \cdot L_2$. But under the isomorphism $\mathfrak{a} \oplus \mathfrak{a}^{-1} \cong \mathcal{O}_K \cdot L_1 \oplus \mathcal{O}_K \cdot L_2$, this is equivalent to saying that $\mathcal{O}_K \oplus \mathfrak{a}$ is saturated into $\mathcal{O}_K \oplus \mathfrak{a} \oplus \mathfrak{a}^{-1}$, which is obviously true since $\mathcal{O}_K \oplus \mathfrak{a}$ and $\mathfrak{a}^{-1}$ are in direct sum there. $\text{Min } L$ is thus indeed saturated into $\mathcal{O}_K\langle\langle a, b \rangle\rangle$.

We now have all the ingredients to conclude. Any 2-state automaton $\mathcal{B}$ computing $L$ must be such that $\text{Min } L \subseteq \mathcal{B}(\mathfrak{st}) \subseteq \text{sat}_{\mathcal{O}_K\langle\langle \Sigma^* \rangle\rangle}(\text{Min } L) = \text{Min } L$ by Lemma 50 below, and hence $\mathcal{O}_K^2 = \mathcal{B}(\mathfrak{st}) \cong \text{Min } L \cong \mathcal{O}_K \oplus \mathfrak{a}$. This holds only if $\mathfrak{a}$ is principal, and hence such a $\mathcal{B}$ may thus only exists when $\mathfrak{a}$ is principal. Conversely if $\mathfrak{a}$ is principal the minimal $\mathcal{O}_K$-modular automaton recognizing $L$, having state-space $\mathcal{O}_K \oplus \mathfrak{a} \cong \mathcal{O}_K^2$, is in fact a 2-state $\mathcal{O}_K$-WA computing $L$. $\square$

**Lemma 50.** Let $R$ be an integral domain with field of fractions $K$, and let $L: \Sigma^* \to R$ be a function whose minimal $K$-weighted automaton has $n$ states. If $\mathcal{B}$ is an $\text{rank-n}$ $R$-modular automaton computing $L$ (this includes in particular $n$-state $R$-weighted automata), then $\text{Min } L \subseteq \mathcal{B}(\mathfrak{st}) \subseteq \text{sat}_{\mathcal{O}_K\langle\langle \Sigma^* \rangle\rangle}(\text{Min } L)$.

*Proof.* $R^{-1}\mathcal{B}$ is (by definition of the rank) an $n$-state $K$-weighted automaton computing $L$, and is thus in fact the minimal $K$-weighted automaton computing $L$. The image of the morphism of automata $\mathcal{B} \to \mathcal{A}_{\text{final}}(L)$ by the functor $R^{-1}$— must thus be an injection (since composed with the canonical $K$-linear transformation $R^{-1}(\mathcal{O}_K\langle\langle \Sigma^* \rangle\rangle) \to K\langle\langle \Sigma^* \rangle\rangle$, it yields the injective morphism $R^{-1}\mathcal{B} \to \mathcal{A}_{\text{final}}(R^{-1}L)$) and hence so must be the morphism $\mathcal{B} \to \mathcal{A}_{\text{final}}(L)$ itself since $R^{-1}$— reflects injections. It follows that

$$\text{Min } L \subseteq \mathcal{B}(\mathfrak{st}) \subseteq \mathcal{O}_K\langle\langle \Sigma^* \rangle\rangle$$

Because $\text{Min } L$ and $\mathcal{B}(\mathfrak{st})$ have the same rank, $R^{-1}(\text{Min } L) \cong R^{-1}(\mathcal{B}(\mathfrak{st}))$, and so

$$\mathcal{B}(\mathfrak{st}) \subseteq \text{sat}_{\mathcal{O}_K\langle\langle \Sigma^* \rangle\rangle}(\mathcal{B}(\mathfrak{st})) = \text{sat}_{\mathcal{O}_K\langle\langle \Sigma^* \rangle\rangle}(\text{Min } L) \quad \square$$