# Learning Weighted Automata over Number Rings, Concretely and Categorically

Quentin Aristote, Sam van Gool, Daniela Petrişan, Mahsa Shirmohammadi

► To cite this version:

Quentin Aristote, Sam van Gool, Daniela Petrişan, Mahsa Shirmohammadi. Learning Weighted Automata over Number Rings, Concretely and Categorically. Logic in Computer Science (LICS) 2025, Jun 2025, Singapore, Singapore. 10.1109/LICS65433.2025.00038 . hal-05040143

HAL Id: hal-05040143

https://cnrs.hal.science/hal-05040143v1

Submitted on 18 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Learning Weighted Automata over Number Rings, Concretely and Categorically

Quentin Aristote* ◦, Sam van Gool†, Daniela Petrişan* ◦ and Mahsa Shirmohammadi† ◦

*Université Paris-Cité, CNRS, Inria, IRIF

†Université Paris-Cité, CNRS, IRIF

F-75013, Paris, France

**Abstract**—We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories.

As our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring $O_K$, we obtain an exact learning algorithm of $O_K$-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.

**Index Terms**—active learning, weighted automata, number rings, category theory, functorial automata, Fatou extension, computational algebraic number theory.

## I. INTRODUCTION

A celebrated result in computational learning theory is Angluin's algorithm for learning deterministic finite-state automata (DFAs) within the minimally adequate teacher (MAT) framework [1]. Angluin's algorithm, also known as the L\* algorithm, learns DFAs for unknown target regular languages by iteratively interacting with an oracle using *membership* and *equivalence* queries. A membership query asks whether a specific word belongs to the target language, whereas an equivalence query asks whether a hypothesis automaton recognizes the target language. In response to an equivalence query, the oracle either accepts the hypothesis as correct or provides a counterexample: a word on which the target language disagrees with the hypothesis language. In the MAT model, a given learning algorithm is *efficient* if its running time is polynomial in the minimal representation of the target concept and the length of the longest counterexample. The running time is an upper bound on the query complexity, that is, the total number of membership and equivalence queries. In contrast to the computational intractability of the problem of *passively* learning DFAs [2], L\* is an efficient procedure.

Extensions of Angluin-style model learning have been applied for uncovering errors in software and hardware systems, including bank cards, network protocols, and legacy software [3]–[8]. Such applications are constrained by limitations on the expressiveness of learning procedures. This has motivated various extensions of the algorithm to more expressive models, such as tree, timed, register and Büchi automata, weighted automata over fields, and sequential deterministic transducers [9]–[18]. Motivated by structural similarities in these extensions, several category-theoretic frameworks for learning have been introduced [19]–[22].

This paper combines computational and categorical aspects of automata learning. Our main focus is the exact learning of R-valued rational functions $L: \Sigma^* \to R$, that is, those computable by finite automata weighted over some ring R. This generalizes the classical efficient algorithm of [17] for learning weighted automata over fields, itself one of the most well-known extensions of L\*. In this setting, a membership query is adapted so that the oracle provides the value $L(w)$ for a given word $w \in \Sigma^*$.

The work of [23] extends [17] by developing an active learning procedure for weighted automata over (semi)rings satisfying certain computability assumptions, including in particular all principal ideal domains (PIDs). For PIDs, the termination of the proposed procedure relies on Noetherian properties, which does not yield a bound on its computational and query complexity.

A more recent work [18] reexamines the problem of learning over PIDs and reduces it to learning over their fields of fractions. The reduction places the problem in polynomial time for efficiently computable PIDs, such as $Z$ and $Q[x]$. In the setting of $Z$, the reduction acts as a *translator* between a learning procedure for $Q$ and the oracle for $Z$-learning, right before any equivalence query. It takes the hypothesis automaton from the learning procedure and, if possible, converts it into an equivalent minimal $Z$-weighted automaton, as the oracle only accepts such inputs. The translator then returns either the oracle's response if there is an equivalent $Z$-weighted automaton or a counterexample showing the hypothesis is not $Z$-valued, and thus not equivalent to the target. This reduction also provides an efficient construction witnessing that $Z$ is a strong Fatou ring. Here, a ring $R$ with field of fractions $K$ is *weak Fatou* if any $R$-weighted function computable by a finite $K$-weighted automaton is also computable by a finite $R$-weighted automaton; it is *strong Fatou* if, additionally, the canonical minimal $R$-weighted automaton has the same number of states as the equivalent minimal $K$-weighted automaton [24, Ch. 7].

Questions around the Fatou property of variants of weighted
automata are discussed, for example, in the monographs [24]–[26], and in the seminal 1971 textbook of Paz [27], who posed the question whether or not the minimal probabilistic automaton computing a $Q$-valued rational function can be defined over $Q$. This question was answered negatively by a counterexample constructed in [28], [29], showing that such minimal probabilistic automata require real algebraic numbers in transition entries.

A closely-related question is the characterization of minimal weighted automata over number rings, where the transition entries are *algebraic integers*, arguably the most natural generalization of automata weighted over integers. A first question is: *are rings of algebraic integers always strong Fatou?* The following example shows that this is not the case; a detailed proof is in Appendix C.

**Example 1.** Consider the number ring $R = \mathbb{Z}[i\sqrt{5}]$ and its field of fractions $K = \mathbb{Q}(i\sqrt{5})$. The 3-state $R$-weighted automaton over the alphabet $\{a, b\}$ given in Figure 1 is state-minimal but has an equivalent 2-state $K$-weighted automaton.

<figure><img src="image_2.png" /><figcaption>Figure 1: Two equivalent $\mathbb{Q}(i\sqrt{5})$-weighted automata.</figcaption></figure>

In this paper, we show that the strong Fatou property *almost* holds: the minimal automaton over a number ring has at most one more state than a minimal automaton over the corresponding number field. This follows from one of our main results: an efficient exact learning and almost-minimization algorithm for weighted automata over number rings.

The problem of designing learning algorithms for $R$-weighted automata beyond the case when $R$ is a field can be approached from a completely different angle, namely, by instantiating existing generic learning algorithms such as those provided in [19], [22]. For example, [22] builds on a view of automata as machines processing some input (such as words over a finite alphabet) and producing some effect (such as values in a semiring). This view can be formalized category-theoretically by seeing automata as functors that are valued in an output category, which is chosen to model a particular effect [30]. For instance, in the case of $R$-weighted automata, the output category is that of free $R$-modules. [22] gives a generic learning algorithm $\text{FunL}^*$ which is correct and terminates whenever the output category satisfies certain assumptions. These assumptions hold in particular for the category of vector spaces over a field $K$, and in this situation the

$\text{FunL}^*$ algorithm instantiates to the existing learning algorithm of $K$-weighted automata [31].

In the case of an arbitrary ring $R$, the category of free $R$-modules typically does not satisfy the assumptions required by $\text{FunL}^*$. This can be partially remedied by moving to a larger category: the category of all $R$-modules. This leads to the definition of a more general notion of automata, which we call *$R$-modular automata* in this paper, to which $\text{FunL}^*$ readily applies. Even if we obtain a formal minimal $R$-modular automaton in this way, a new difficulty arises: this automaton does not always correspond to an actual $R$-weighted automaton. Another drawback of the generic approach is its complexity. Even if we manage to move from an $R$-modular to an $R$-weighted automaton, $\text{FunL}^*$ might run in exponential time. The concrete representations of the modules involved and the ensuing complexity analysis require additional care.

In this paper we strive to reconcile the abstract and the concrete perspectives. We next summarize our main contributions.

## A. Overview of Main Results

We briefly introduce the necessary notions required to present a high-level overview of our contributions. A complex number $\alpha$ is *algebraic* if it is the root of a non-zero polynomial in $\mathbb{Q}[x]$. The *minimal polynomial* of $\alpha$ is the monic polynomial of least degree in $\mathbb{Q}[x]$ that has $\alpha$ as a root. The number $\alpha$ is called an *algebraic integer* if its minimal polynomial is in $\mathbb{Z}[x]$. A number field $K$ is a finite degree field extension of $\mathbb{Q}$, which, by the primitive element theorem, can be obtained by adjoining some algebraic number $\alpha$ to $\mathbb{Q}$. The *degree of $K$* is the degree of the minimal polynomial of $\alpha$. A number ring is the subring of a number field comprised of all its algebraic integers. We denote by $O_K$ the number ring of $K$.

The main algorithmic question we address is: *Can a target $O_K$-automaton be learned in polynomial-time?* This question is much more challenging than the analogous one for $\mathbb{Z}$-weighted automata, due to the structural differences between $\mathbb{Z}$ and $O_K$. For instance, in contrast to $\mathbb{Z}$, $O_K$ is not in general a principal ideal domain, but only a Dedekind domain: while a $\mathbb{Z}$-submodule of $\mathbb{Z}^n$ always has a basis of size at most $n$, an $O_K$-submodule of $O_K^n$ may not have a basis. In particular, there might be no basis for the usual forward or backward modules explored while learning. This underlines one of the primary difficulties in developing learning procedures over $O_K$. We can nevertheless prove:

**Theorem 2.** *Given a full representation of $O_K$, exact learning of $O_K$-weighted automata is within polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of $K$ and the logarithm of its discriminant.*

Our learning algorithm for $O_K$-weighted automata relies on a reduction procedure for $K$-weighted automata akin to [18, Algorithm 6], given in Algorithm 4. The $O_K$-automaton obtained by our learning algorithm may not be minimal, but is *almost-minimal*: it has at most one more state than the minimal one. Furthermore, we show in Proposition 26 that
deciding minimality of $O_K$-weighted automata allows us to decide the *principal ideal problem*, which has, to the best of our knowledge, *quantum polynomial time complexity* [32].

The proof of correctness of Algorithm 4 can be obtained at a concrete level, but it also relies on some more abstract principles. Another contribution of this paper is the generic Algorithm 3 that generalizes the reduction procedure of $Q$-weighted automata to $Z$-weighted automata [18]. Abstracting away from the concrete weighted automata, we can work at more general level with automata represented as functors, following [30]. We consider automata valued either in a category $C$ (that will be instantiated to a category of $R$-modules), or in a category $D$ (that will be instantiated to the category of $K$-vector spaces). In practice, we want to consider categories $C$ and $D$ such that computations are easier in $D$. The aim of Algorithm 3 is to transform a $D$-valued automaton $\mathcal{A}$ into a minimal $C$-valued one whenever the language accepted by $\mathcal{A}$ factors through $C$, or otherwise provides some word that witnesses this is not the case. Assuming $C$ and $D$ are related by a functor satisfying some reasonable assumptions, we prove in Theorem 18 that Algorithm 3 is correct and reduces the problem of learning $C$-automata to that of learning $D$-automata.

## B. Guideline for reading the paper

After a commutative algebra primer in Section II, we explain the categorical view on minimal weighted automata in Section III. Sections IV and V apply this to obtain a generic algorithm for reducing learning problems. Finally, in Section VI, we obtain our main theorem on number rings.

We adopt the following colour convention to help readers with various backgrounds navigate through the paper. We describe in yellow the concrete concepts on weighted automata, in blue those pertaining to the relevant categories of modules, and in purple concepts written in arbitrary categories. At times, the same concept is described in equivalent ways at different levels of abstraction, in order to ease the translation of terminology used across different communities. Readers only interested in the complexity aspects of our results may first skip the more abstract paragraphs in Sections III and IV, and Section V altogether.

# II. PRIMER ON COMMUTATIVE ALGEBRA

We recall a few definitions and facts about commutative algebra that we will need throughout this paper. Further details are given in Appendix A-A; also see, e.g., [33, Ch. 4, 6, 10].

Throughout this paper, *ring* means commutative ring with unit. The notion of *module* generalizes the idea of a vector space, which has scalars in a field, to having scalars in an arbitrary ring. *Free modules* are essential for the algebraic analysis of $R$-weighted automata. For any (possibly infinite) set $Q$, a finite $R$-linear combination is an expression $\sum_{i=1}^{n} r_i q_i$, with $r_i \in R$ and $q_i \in Q$ for each $1 \le i \le n$; said otherwise, it is a finitely supported function from $Q$ to $R$. The set of finite $R$-linear combinations, equipped with the expected addition and $R$-action, is a first example of a free $R$-module; we denote it by $R^Q$. The elements $1_R \cdot q$, for $q \in Q$, constitute a canonical

basis for $R^Q$; we identify each $q$ with its corresponding basis element. The *rank* of $R^Q$ is the cardinality of $Q$.

For any $R$-module $M$ and $(x_q)_{q \in Q}$ a $Q$-indexed set of elements of $M$, there exists a unique morphism $\phi: R^Q \to M$ that sends $q$ to $x_q$. The family $(x_q)_{q \in Q}$ is *free* in $M$ if $\phi$ is injective, *generating* for $M$ if $\phi$ is surjective, and a *basis* for $M$ if $\phi$ is bijective. The module $M$ is called *finitely generated* if it has a finite generating family and *free* if it has a basis. An element $m \in M$ has *torsion* if there exists $r \ne 0$ such that $rm = 0$. An $R$-module $M$ is *torsion-free* if there are no non-zero torsion elements. Free $R$-modules are torsion-free, but the converse is not true; for example, the ideal $(2, 1 + i\sqrt{5})$ in the ring $\mathbb{Z}[i\sqrt{5}]$ is not free. Note that a submodule of a torsion-free module is again torsion-free.

Let $R$ be an integral domain. The *field of fractions* of $R$ is obtained by adding formal inverses for all non-zero elements of $R$: its elements are pairs $r/s$, where $r \in R$ and $s \in R^\times$, and $r/s$ is identified with $r'/s'$ when $rs' = r's$; note that it is in particular an $R$-module. Let $K$ be the field of fractions of $R$. Extending this definition to modules, for any $R$-module $M$, there is a $K$-vector space $R^{-1}M$, called the *localization* or *extension of scalars* of $M$. Its elements are formal fractions $m/r$ of an element $m \in M$ and an element $r \in R^\times$, where we identify $m/r$ and $m'/r'$ if there is $s \in R^\times$ such that $sr \cdot m' = sr' \cdot m$. For any $R$-linear map $f: M \to N$, we obtain a $K$-linear map $R^{-1}f: R^{-1}M \to R^{-1}N$, which maps $m/r$ to $f(m)/r$. The *rank* of an $R$-module is the dimension of its localization.

A *fractional ideal* of a ring $R$ is a non-zero $R$-submodule $\alpha$ of $K$ such that, for some $r \in R \setminus \{0\}$, the submodule $ra := \{ra \mid a \in \alpha\}$ is contained in $R$. The *dual* of a fractional ideal $\alpha$ is the fractional ideal $\alpha^{-1} := \{x \in K \mid xa \subseteq R\}$, and $\alpha$ is *invertible* if $\alpha^{-1}\alpha = R$. An integral domain $R$ is a *Dedekind domain* if, and only if, every fractional ideal is invertible. It is a *principal ideal domain (PID)* when all its ideals are principal. Any PID is a Dedekind domain, and any Dedekind domain $R$ is *Noetherian*, meaning that any ideal of $R$ is finitely generated. Moreover, if $R$ is a Dedekind domain with field of fractions $K$, then every finitely generated torsion-free $R$-module $M$ is a direct sum of rank 1 submodules, $M = \bigoplus_{i=1}^n E_i$, where each $E_i$ is of the form $\mathfrak{a}_i e_i$, for some fractional ideal $\mathfrak{a}_i$ of $K$ and $e_i \in M$, such that the system $(e_i)_{i=1}^n$ is free, see, e.g., [33, Cor. 10.2.3]. Such a set of rank 1 submodules $E_1, \dots, E_n$ is called a *pseudo-basis* for $M$.

## III. MINIMAL WEIGHTED AND MODULAR AUTOMATA

In this section, we recall the fundamental definitions of weighted automata over a ring. We phrase each definition in two ways: using the more traditional automata-theoretic language, and using a category-theoretic formulation [30]. More details on the categorical notions are in Appendix E.

### A. Basic definitions

Let $R$ be a ring and $\Sigma$ a finite alphabet.

Let $Q, Q'$ be sets. Any linear transformation $f: R^Q \to R^{Q'}$ is uniquely determined by the values $(f(q))_{q \in Q}$, and can thus be represented by a matrix of size $|Q| \times |Q'|$, whose entry on
Let $\mathbf{C}$ be a category and $I, O$ two objects of $\mathbf{C}$. A $(\mathbf{C}, I, O)$-automaton is a functor $\mathcal{A}: \mathbf{I} \to \mathbf{C}$ such that $\mathcal{A}(\text{in}) = \mathbf{I}$ and $\mathcal{A}(\text{out}) = \mathbf{O}$. A morphism between $(\mathbf{C}, I, O)$-automata $\mathcal{A}$ and $\mathcal{A}'$ is a natural transformation $\alpha: \mathcal{A} \to \mathcal{A}'$ such that the components $\alpha_{\text{in}}$ and $\alpha_{\text{out}}$ are identities. $(\mathbf{C}, I, O)$-automata and their morphisms form a category denoted by $\mathbf{Auto}(\mathbf{C}, I, O)$.

We instantiate this definition for $\mathbf{R}$-modules:

**Definition 3.** An $\mathbf{R}$-modular automaton over the alphabet $\Sigma$ is a $(\mathbf{Mod}_R, \mathbf{R}, \mathbf{R})$-automaton.

**Definition 4.** An $\mathbf{R}$-modular automaton over the alphabet $\Sigma$ is a tuple $(M, \mathcal{A}(\triangleright), (\mathcal{A}(\sigma))_{\sigma \in \Sigma}, \mathcal{A}(\triangleleft))$ consisting of an arbitrary module $M$ and linear maps $\mathcal{A}(\triangleright): R \to M, \mathcal{A}(\sigma): M \to M$, for $\sigma \in \Sigma$ and $\mathcal{A}(\triangleleft): M \to R$.

**Remark 5.** For a commutative ring $R$, the $(\mathbf{FreeMod}_R, R, R)$-automata are the $\mathbf{R}$-weighted automata in the usual sense. $\mathbf{R}$-modular automata are similar, the only difference being that the state object is not necessarily a free $\mathbf{R}$-module, and thus cannot be represented via its basis elements. Notice that when $R = \mathbf{K}$ is a field, the categories $\mathbf{FreeMod}_K$ and $\mathbf{Mod}_K$ are equivalent, since any vector space is isomorphic to $K^X$, where $X$ is any chosen basis. For this reason, minimization and learning of $\mathbf{K}$-weighted automata are much simpler than for an arbitrary ring.

A $(\mathbf{C}, I, O)$-language is a functor $\mathcal{L}: \mathbf{O} \to \mathbf{C}$ such that $\mathcal{L}(\text{in}) = I$ and $\mathcal{L}(\text{out}) = \mathbf{O}$. The language recognized by a $(\mathbf{C}, I, O)$-automaton $\mathcal{A}$ is the composite $\mathcal{A} \circ \mathbf{I}$.

For a $(\mathbf{C}, I, O)$-language $\mathcal{L}: \mathbf{O} \to \mathbf{C}$ we denote by $\mathbf{Auto}(\mathcal{L})$ the category of automata recognizing $\mathcal{L}$. Notice that, if $\phi: \mathcal{A} \to \mathcal{A}'$ is a morphism of $(\mathbf{C}, I, O)$-automata, then the languages recognized by these automata coincide. Hence the categories $\mathbf{Auto}(\mathcal{L})$ are the connected components of the category $\mathbf{Auto}(\mathbf{C}, I, O)$.

The crucial idea behind the functorial view of automata is to view transformations between different kinds of automata as liftings of functors between the respective output categories.

**Fact 6.** Let $\mathcal{F}: \mathbf{C} \to \mathbf{D}$ be a functor and $I$ and $O$ be two objects of $\mathbf{C}$. If a $(\mathbf{C}, I, O)$-automaton $\mathcal{A}$ recognizes a $(\mathbf{C}, I, O)$-language $\mathcal{L}$, then $\mathcal{F} \circ \mathcal{A}$ is a $(\mathbf{D}, \mathcal{F}\mathbf{I}, \mathcal{F}\mathbf{O})$-automaton recognizing the $(\mathbf{D}, \mathcal{F}\mathbf{I}, \mathcal{F}\mathbf{O})$-language $\mathcal{F} \circ \mathcal{L}$.

This defines a functor $\bar{\mathcal{F}}: \mathbf{Auto}(\mathcal{L}) \to \mathbf{Auto}(\mathcal{F} \circ \mathcal{L})$, the lifting of $\mathcal{F}$.

An $\mathbf{R}$-weighted language $L: \Sigma^* \to \mathbf{R}$ can be seen as a $(\mathbf{FreeMod}_R, 1, 1)$-language or as a $(\mathbf{Mod}_R, \mathbf{R}, \mathbf{R})$-language. This is witnessed by a canonical functor $\mathbf{FreeMod}_R \to \mathbf{Mod}_R$ which sends an object $Q$ to the module $\mathbf{R}^Q$ freely generated by $Q$. Its lifting embeds the category of $\mathbf{R}$-weighted automata accepting $L$ as a subcategory of the category of $\mathbf{R}$-modular automata accepting $L$.

We now recall the construction of forward and backward modules for $\mathbf{R}$-weighted automata, and show how this is an instance of the functorial approach to minimization of [30]. In the rest of this section, let $\mathcal{A}$ be an $\mathbf{R}$-WA with states $Q$.

A configuration of $\mathcal{A}$ is a row vector $r \in \mathbf{R}^Q$; it is reachable if there is a linear combination $\sum_{i=1}^k \lambda_i w_i$ of words such that $r = \sum_{i=1}^k \lambda_i \mathcal{A}(\triangleright w_i)$. The forward module of $\mathcal{A}$ is the submodule $\text{Reach} \mathcal{A}$ of $\mathbf{R}^Q$ consisting of the reachable configurations in $\mathcal{A}$.

When $R$ is a field, $\text{Reach} \mathcal{A}$ is the state space of the forward conjugate $\bar{\mathcal{A}}$ of $\mathcal{A}$, see e.g. [34]. However, in general, the forward module is not necessarily free. This justifies the move to $\mathbf{R}$-modular automata.

Let $\mathcal{L}$ be the $(\mathbf{Mod}_R, R, R)$-language recognized by $\mathcal{A}$. The category $\mathbf{Auto}(\mathcal{L})$ of $\mathbf{R}$-modular automata recognizing $\mathcal{L}$ has an initial object $\mathcal{A}_{\text{init}}$ [30, Lemma 3.1]. We recall an explicit construction: $\mathcal{A}_{\text{init}}(\mathbf{st})$ is the free $\mathbf{R}$-module on the set $\Sigma^*$, the linear map $\mathcal{A}_{\text{init}}(\triangleright)$ sends 1 to $\varepsilon$, the transition map $\mathcal{A}_{\text{init}}(a)$ sends the generator $w$ to $wa$ and the final weights linear map $\mathcal{A}_{\text{init}}(\triangleleft)$ sends $w$ to $L(w)$. The unique morphism from $\mathcal{A}_{\text{init}}$ to $\mathcal{A}$ is given by the linear map $!_{\mathcal{A}}: \mathcal{A}_{\text{init}}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ that sends a generator $w \in \Sigma^*$ to the configuration $\mathcal{A}(\triangleright w) \in \mathcal{A}(\mathbf{st})$. The forward module $\text{Reach} \mathcal{A}$ is the image of $!_{\mathcal{A}}$, and carries the structure of an $\mathbf{R}$-modular automaton, since the concept of image lifts to the category $\mathbf{Auto}(\mathcal{L})$, see Appendix E-C.

Let $R \llcorner \langle \Sigma^* \rangle$ denote the module of $\mathbf{R}$-weighted languages. Given a configuration $r \in \mathbf{R}^Q$, the $\mathbf{R}$-weighted language $\mathcal{L}(\mathcal{A})_r$ observed by $\mathcal{A}$ starting from $r$ is defined as $\mathcal{L}(\mathcal{A})_r(v) := \mathcal{A}(v\triangleleft)(r)$, for $v \in \Sigma^*$. The backward module of $\mathcal{A}$ is the submodule $\text{Obs} \mathcal{A}$ of $R \llcorner \langle \Sigma^* \rangle$ consisting of the languages observed by $\mathcal{A}$, and is computed by merging the configurations of $\mathcal{A}$ that yield the same observed language.

When $R$ is a field, $\text{Obs} \mathcal{A}$ is the state space of the backward conjugate $\bar{\mathcal{A}}$ of $\mathcal{A}$ in the sense of [34]. In general, $\text{Obs} \mathcal{A}$ also carries the structure of an $\mathbf{R}$-modular automaton, and again, this is an instance of [35, Section 2.2].

The category $\mathbf{Auto}(\mathcal{L})$ has a final object $\mathcal{A}_{\text{final}}$, whose state space is the $\mathbf{R}$-module $R \llcorner \langle \Sigma^* \rangle$. The linear map $\mathcal{A}_{\text{final}}(\triangleright)$ sends 1 to $L$, the transition map $\mathcal{A}_{\text{final}}(a)$ sends $L' \in R \llcorner \langle \Sigma^* \rangle$ to the derivative language $a^{-1}L' - \text{sending } u \in \Sigma^* \text{ to } L'(au) -$ and the final weights linear map $\mathcal{A}_{\text{final}}(\triangleleft)$ sends $L': \Sigma^* \to R$ to $L'(\varepsilon)$.

The unique morphism from $\mathcal{A}$ to $\mathcal{A}_{\text{final}}$ is the linear map $i_{\mathcal{A}}: \mathcal{A}(\mathbf{st}) \to R \llcorner \langle \Sigma^* \rangle$ which sends a configuration $r \in \mathcal{A}(\mathbf{st})$ to $\mathcal{L}(\mathcal{A})_r$. The module $\text{Obs} \mathcal{A}$ is the image of $i_{\mathcal{A}}$.

When $R$ is a field, the minimization of $\mathcal{A}$ can be described as the forward conjugate of the backward conjugate of $\mathcal{A}$, see e.g. [34, Prop. 3.5]. The minimization can also be described more abstractly and more generally in the categorical framework, provided that the output category $\mathbf{C}$ carries additional structure:

**Definition 7.** A category $\mathbf{C}$ is called good-for-minimization when $\mathbf{C}$ has countable powers and countable copowers, and is moreover equipped with a factorization system (see Appendices E-B and E-C for these standard definitions).

A factorization system generalizes factorization of functions:
it consists of two classes $\mathcal{E}$ and $\mathcal{M}$ of C-morphisms such that in particular every $f: X \to Y$ factors, uniquely up to unique isomorphism, as $X \xrightarrow{e} Z \xrightarrow{m} Y$ with $e \in \mathcal{E}$ and $m \in \mathcal{M}$. We call both $Z$ and $m: Z \to Y$ the $(\mathcal{E}, \mathcal{M})$-image of $f$.

**Construction 8.** If $\mathbf{C}$ is good-for-minimization and $\mathcal{L}$ is a $(\mathbf{C}, I, O)$-language, then the category $\mathbf{Auto}(\mathcal{L})$ inherits a factorization system from $\mathbf{C}$, and has initial and final objects $\mathcal{A}_{\text{init}}$ and $\mathcal{A}_{\text{final}}$. A minimal automaton $\text{Min} \mathcal{L}$ is then obtained as the factorization of the unique morphism $!_{\mathcal{A}_{\text{final}}} : \mathcal{A}_{\text{init}} \to \mathcal{A}_{\text{final}}$, see [35, Lem. 3.2]. Furthermore, for any automaton $\mathcal{A}$ in $\mathbf{Auto}(\mathcal{L})$ we define $\text{Reach} \mathcal{A}$ as the factorization of the unique morphism $!_{\mathcal{A}} : \mathcal{A}_{\text{init}} \to \mathcal{A}$ and $\text{Obs} \mathcal{A}$ as the factorization of the unique morphism $i_{\mathcal{A}} : \mathcal{A} \to \mathcal{A}_{\text{final}}$. Then $\text{Min} \mathcal{L}$ is isomorphic to $\text{Reach}(\text{Obs} \mathcal{A})$ and to $\text{Obs}(\text{Reach} \mathcal{A})$ [35, Lem. 2.3].

**Fact 9.** The following categories are good-for-minimization: the category $\text{Mod}_R$ of $R$-modules and linear maps, its full subcategory $\text{Mod}^{\text{tf}}_R$ on torsion-free modules, and in particular the category $\text{Vec}_K$ of vector spaces over a field $K$. For all of these categories, we use the factorization system that factors any linear map as a surjective linear map followed by an injective linear map. By contrast, on $\text{FreeMod}_R$ for a general ring $R$, there is no obvious factorization system that yields a meaningful notion of minimization.

Instantiating Construction 8 to $\text{Mod}_R$-automata we obtain a minimal $R$-modular automaton $\text{Min} \mathcal{L}$ accepting $\mathcal{L}$ as $\text{Reach}(\text{Obs}(\mathcal{A}))$. However, an important caveat is that the state space of $\text{Min} \mathcal{L}$ is an $R$-module which is not necessarily free without further assumptions on the ring $R$. As a consequence, we cannot hope to always obtain a reasonable finite presentation of the minimal $R$-modular automaton. In the next subsection, we examine additional assumptions on $R$ that do allow for this, and are satisfied for all number rings.

### C. Minimal automata over Dedekind domains

Let $R$ be an integral domain, and let $K$ be its field of fractions. A first way to represent an $R$-modular automaton $\mathcal{A}$ is as a $K$-weighted automaton with state-space $R^{-1}\mathcal{A}(\text{st})$. This includes in particular the classical view of $R$-weighted automata as $K$-weighted automata with weights in $R$. We define the *rank* of an $R$-modular automaton $\mathcal{A}$ as the rank of the module $\mathcal{A}(\text{st})$ and the *rank* of a recognizable $R$-weighted language $L$ as the rank of the module $\text{Min} L$.

The $R$-module $R\langle\langle\Sigma^*\rangle\rangle$ is not necessarily free (even when $R = \mathbb{Z}$, see, e.g., [36]), but $R\langle\langle\Sigma^*\rangle\rangle$ is torsion-free, and thus any submodule of $R\langle\langle\Sigma^*\rangle\rangle$ is again torsion-free. In particular, for any $R$-weighted automaton $\mathcal{A}$, the backward module $\text{Obs} \mathcal{A}$ is torsion-free, and so is its forward submodule $\text{Reach}(\text{Obs} \mathcal{A})$. Thus, if $R$ is an integral domain, then the state module of a minimal $R$-modular automaton is always torsion-free. For a rational $R$-weighted language $L$, $\text{Min} L$ is also always finitely generated [37, Theorem 5.21].

In particular, if $R$ is a PID, then all finitely generated torsion-free modules are free, so that it is possible to choose a basis for $\text{Min} L$ and the minimal $R$-modular automaton is in

fact $R$-weighted. More generally, if $R$ is a *Dedekind domain*, then the finitely generated torsion-free modules, in particular $\text{Min} L$, do not necessarily have a basis, but they have a pseudo-basis. This is key in proving the following proposition, which motivates this work; we give a proof in Appendix D.

**Proposition 10.** Let $R$ be a *Dedekind domain*, and let $L$ be an $R$-weighted language of rank $n$ computed by a finite $R$-WA. There exists an $R$-WA computing $L$ with at most $n+1$ states.

We call an automaton as in the conclusion of Proposition 10 almost minimal. An illustration of Proposition 10 is given in Example 1. The goal of the present work is to provide an algorithm computing almost-minimal automata when $R$ is a number ring, and thus an effective *Dedekind domain*.

## IV. LEARNING PROBLEMS AND REDUCTION PROCEDURES

We now tackle the problem of computing the minimal automaton recognizing a language, focusing on *active learning*.

For a fixed ring $R$, the goal of the active learning algorithm is to compute the minimal $R$-weighted automaton recognizing a certain $R$-weighted language $L$ with the only help of an oracle able to answer two kind of queries:

* *value queries:* given an input word $w \in \Sigma^*$, the oracle returns the value $L(w)$;

* *equivalence queries:* given an $R$-weighted automaton $\mathcal{A}$, the oracle decides whether $\llbracket \mathcal{A} \rrbracket = L$, and, if this is not the case, outputs a counterexample input word $w \in \Sigma^*$ such that $\llbracket \mathcal{A} \rrbracket(w) \neq L(w)$.

More generally, the problem of active learning can be stated for $(\mathbf{C}, I, O)$-automata, as in Problem 1 below. In this setting, the oracle can answer:

* *value queries:* given an input word $w \in \Sigma^*$, the oracle returns a morphism $\mathcal{L}(\triangleright w \triangleleft): I \to O$;

* *equivalence queries:* the oracle decides whether a $(\mathbf{C}, I, O)$-automaton $\mathcal{A}$ recognizes the target $(\mathbf{C}, I, O)$-language $\mathcal{L}$, and, if this is not the case outputs a counterexample $w \in \Sigma^*$ such that $\mathcal{A} \circ \iota(\triangleright w \triangleleft) \neq \mathcal{L}(\triangleright w \triangleleft)$.

**Problem 1** Active learning of $(\mathbf{C}, I, O)$-automata

**Input:** an oracle able to answer value and equivalence queries for a $(\mathbf{C}, I, O)$-language $\mathcal{L}$

**Output:** $\text{Min} \mathcal{L}$

A generic category-theoretic algorithm for solving Problem 1 was given in [22]. It encompasses, among other things, the active learning algorithm for learning $K$-weighted automata [31], which runs in polynomial time. However, the generality of the algorithm in [22] comes at a cost. First, it takes for granted basic operations of $R$ and its modules which could be difficult to compute, or even undecidable. Second, it does not take into account possible optimizations for specific choices of $\mathbf{C}, I$ and $O$. This is the case, in particular, for $\mathbb{Z}$-weighted automata. On the one hand, by instantiating the generic algorithm of [22] to the case of $\mathbb{Z}$-weighted automata,
one obtains an algorithm that runs in exponential time. On the other hand, [18] gives a refined polynomial time algorithm, tailor-made for $\mathbb{Z}$-weighted automata, obtained by a clever reduction to the learning problem for $\mathbb{Q}$-weighted automata.

More generally, we consider a Noetherian integral domain $R$, and we first tackle the active learning problem for $R$-modular automata, which reduces to that of active learning for automata weighted in $R$'s field of fractions, $K$.

The key ingredient of this reduction is a procedure TRANSFORM which, given as input a $K$-weighted automaton $\mathcal{A}$ recognizing $L \in K\langle\langle\Sigma^*\rangle\rangle$, either (a) outputs a minimal $R$-modular automaton equivalent to $\mathcal{A}$, or, otherwise, (b) outputs a counterexample word $w \in \Sigma^*$ such that $L(w) \notin R$. Note that, in case (a), $L$ is actually in $R\langle\langle\Sigma^*\rangle\rangle$, while in case (b), no $R$-modular automaton equivalent to $\mathcal{A}$ can exist. The procedure TRANSFORM will be an instance of the more general Algorithm 3. Let us describe how it can be used for implementing the reduction between the learning problems.

Let $L_R: \Sigma^* \to R$ be an $R$-weighted language, and write $L_K: \Sigma^* \to K$ for the composite of $L_R$ with the inclusion map of $R$ into its field of fractions. Assume that ORACLE$_R$ is an oracle for the active learning of $L_R$. We implement an oracle ORACLE$_K$ for the active learning of $L_K$ as follows.

* Value queries to ORACLE$_K$ are transmitted to ORACLE$_R$.

* Consider a $K$-weighted automaton $\mathcal{A}$ submitted for an equivalence query to ORACLE$_K$. We run TRANSFORM with input $\mathcal{A}$. If the output is an $R$-modular automaton equivalent to $\mathcal{A}$, this automaton is in turn fed to ORACLE$_R$. Otherwise, if TRANSFORM outputs a word $w$ such that $[\mathcal{A}](w) \notin R$, then ORACLE$_K$ returns $w$ as a counterexample. This is correct, since $L_K(w) = L_R(w) \in R$, but $[\mathcal{A}](w) \notin R$, so $[\mathcal{A}](w) \neq L_K(w)$.

Once ORACLE$_K$ is implemented, we first learn a minimal $K$-weighted automaton recognizing $L_K$. Since $L_K$ factors through $R$, we can use TRANSFORM once more to transform the minimal $K$-weighted automaton into an equivalent $R$-modular automaton, which turns out to be minimal.

V. GENERIC REDUCTION OF LEARNING PROBLEMS

In this section, and as our first main contribution, we reconcile the generic and the tailor-made approaches to learning: we describe additional conditions on the categorical framework that allow for optimizations similar to those described in [18] for $\mathbb{Z}$-weighted automata. Moreover, this allows us to go beyond $\mathbb{Z}$-weighted automata: in Section VI we instantiate the generic Algorithm 3 to show that active learning of automata weighted over number rings can be solved in polynomial time.

To summarize the discussion in Section IV, the goal is to learn $R$-modular automata. However, switching to $K$-weighted automata makes computations easier. The fact that $R$-modular automata can be seen as $K$-weighted automata is witnessed at a category-theoretic level, as an instance of Fact 6 via the lifting of the localization functor $R^{-1}: \text{Mod}_R \to \text{Vec}_K$. The action of the latter functor on $R$-modules and $R$-linear maps was described in Section II.

We abstract this even further as follows.

**Assumption 11.** $\mathbf{C}$ and $\mathbf{D}$ are two good-for-minimization categories, with respective factorization systems $(\mathcal{E}_\mathbf{C}, \mathcal{M}_\mathbf{C})$ and $(\mathcal{E}_\mathbf{D}, \mathcal{M}_\mathbf{D})$, $I$ and $O$ two objects of $\mathbf{C}$, and $\mathcal{F}: \mathbf{C} \to \mathbf{D}$ is a functor.

The intuition behind Assumption 11 is that $\mathbf{C}$ is a category where we want to carry out some computation, but $\mathbf{D}$ is a category where it is easier to compute. Using the lifting of $\mathcal{F}$ (Fact 6), we aim to compute as much as possible in $\mathbf{D}$ before pulling the result back along $\mathcal{F}$ and finishing the computation in $\mathbf{C}$. Assumption 11 can be instantiated to our context by taking $\mathbf{C} := \text{Mod}_\mathbf{R}$, $\mathbf{D} := \text{Vec}_\mathcal{K}$, and $\mathcal{F} := R^{-1}$. We now ask: when does the problem of learning minimal $(\mathbf{C}, I, O)$-automata reduce to the problem of learning minimal $(\mathbf{D}, \mathcal{F}I, \mathcal{F}O)$-automata? Given sufficient assumptions, we will provide such a reduction by describing a procedure for solving the following problem.

**Problem 2** Transforming a $(\mathbf{D}, \mathcal{F}I, \mathcal{F}O)$-automaton into a $(\mathbf{C}, I, O)$-automaton

**Input:** a $(\mathbf{D}, \mathcal{F}I, \mathcal{F}O)$-automaton recognizing a language $\mathcal{L}$

**Output:** either $\text{Min } \mathcal{L}',$ where $\mathcal{L}'$ is a $(\mathbf{C}, I, O)$-language such that $\mathcal{L} = \mathcal{F} \circ \mathcal{L}',$ or a word $w \in \Sigma^*$ for which there does not exist $f: I \to O$ such that $\mathcal{F}f = \mathcal{L}(\triangleright w\triangleleft)$.

In Assumption 12 below, we will state additional conditions that we put on the functor $\mathcal{F}$ to be able to solve Problem 2. Being able to pull back computations from $\mathbf{D}$ to $\mathbf{C}$ intuitively requires some form of inverse of the functor $\mathcal{F}$. We require the existence a functor $\mathcal{G}$ which is right adjoint to $\mathcal{F}$. Briefly (see Appendix E-D for more details), this means that, for any objects $X$ in $\mathbf{C}$ and $Y$ in $\mathbf{D}$, we have a bijection between the sets of morphisms $\mathbf{D}(\mathcal{F}X, Y)$ and $\mathbf{C}(X, \mathcal{G}Y)$, which is moreover natural in both coordinates. For any object $X$ of $\mathbf{C}$, the unit of the adjunction at $X$ is the morphism $\eta_X: X \to \mathcal{G}FX$ corresponding to the identity morphism $\mathcal{F}X \to FX$. For any object $Y$ of $\mathbf{D}$, the count of the adjunction at $Y$ is the morphism $\varepsilon_Y: \mathcal{F}GY \to Y$ corresponding to the identity morphism $GY \to \mathcal{G}Y$.

**Assumption 12.** Under Assumption 11, assume moreover that

1) $\mathcal{F}[\mathcal{E}_\mathbf{C}] \subseteq \mathcal{E}_\mathbf{D}$ and $\mathcal{F}^{-1}[\mathcal{M}_\mathbf{D}] = \mathcal{M}_\mathbf{C}$;

2) $\mathcal{F}$ has a right-adjoint $\mathcal{G}: \mathbf{D} \to \mathbf{C}$;

3) for every object $X$ of $\mathbf{C}$, $\eta_X: X \to \mathcal{G}FX$ is in $\mathcal{M}_\mathbf{C}$;

4) for every object $Y$ of $\mathbf{D}$, $\varepsilon_X: \mathcal{G}FX \to X$ is in $\mathcal{M}_\mathbf{D}$.

In order to satisfy Assumption 12, the localization functor needs to be restricted to the category $\text{Mod}^{\text{tf}}_R$ of torsion-free $R$-modules and linear maps between them, which, just as $\text{Vec}_K$, is a good-for-minimization category, see Fact 9.

**Lemma 13.** The functor $R^{-1}: \text{Mod}^{\text{tf}}_R \to \text{Vec}_K$ satisfies Assumption 12.

**Remark 14.** The conditions in Assumption 12 are rather mild. For readers aware of fibrations: these conditions are automatically satisfied by functors $\mathcal{F}: \mathbf{C} \to \mathbf{D}$ that are of fibrations
and for which each fiber along $\mathcal{F}$ has a terminal object. The functor $R^{-1}$ is an example of one, and such ofibrations also come a dime a dozen in category theory: topological functors [38, §21], for instance the forgetful functors $\text{Top} \to \text{Set}$ or $\text{Meas} \to \text{Set}$, are a prominent example. We leave for further work the study of these other concrete examples.

Before giving the algorithm for solving Problem 2, let us start by relating the minimal automata in $\mathbf{C}$ and $\mathbf{D}$. A priori, in the setting of Assumption 11, they could be entirely unrelated, as we do not impose any relationship between the factorization systems. However, the additional Assumption 12 ensures that post-composing by $\mathcal{F}$ preserves minimality:

**Proposition 15.** Under Assumption 12, let $\mathcal{L}$ be a $(\mathbf{C}, I, O)$-language. Then $\mathcal{F} \circ \text{Min} \, \mathcal{L} \cong \text{Min}(\mathcal{F} \circ \mathcal{L})$.

What this says in the $R$-weighted setting is that the minimal $R$-modular automaton recognizing an $R$-weighted language $L_R: \Sigma^* \to R$ is also minimal among all $K$-weighted automaton recognizing $L_K: \Sigma^* \to R \hookrightarrow K$. This, combined with Proposition 10 and the fact that Nøetherian integral domains are weak Fatou rings, shows that Dedekind domains are what we call almost-strong Fatou rings:

**Corollary 16.** Let $R$ be a Dedekind domain, $K$ its field of fractions, and $L$ an $R$-weighted language. If $L$ is computed by a $K$-weighted automaton with $n$ states, then it is also computed by an $R$-weighted automaton with $n+1$ states.

This suggests a natural question: Are other rings, beyond Dedekind domains, still almost-strong Fatou rings, possibly with a different number of extra states than 1? We leave this for future work.

Notice how any algorithm that solves Problem 2 implements in particular minimization of $(\mathbf{C}, I, O)$-automata: given a $(\mathbf{C}, I, O)$-automaton $\mathcal{A}$, starting with $\mathcal{F} \circ \mathcal{A}$ as input $(\mathbf{D}, \mathcal{F}I, \mathcal{F}O)$-automaton, the output will be the minimal automaton equivalent to $\mathcal{A}$ (because $\mathcal{F} \circ \mathcal{A}$ recognizes a language that factors through $\mathcal{F}$). It is already known that minimization procedures can be understood categorically [30], [39], [40]. In the functorial framework, to minimize a $(\mathbf{C}, I, O)$-automaton $\mathcal{A}$, one should compute $\mathcal{A}' = \text{Obs} \, \mathcal{A}$ (intuitively, merging equivalent states) and then $\text{Reach}(\mathcal{A}')$ (intuitively, restricting to reachable states).

Recall from Construction 8 that, when working in a good-for-minimization category $\mathbf{C}$ equipped with a factorization system $(\mathcal{E}, \mathcal{M})$, the automaton $\text{Reach} \, \mathcal{A}'$ is defined as the $(\mathcal{E}, \mathcal{M})$-image of the unique morphism $\mathcal{A}'_A: \mathcal{A}_{\text{init}} \to \mathcal{A}'$. Its state object is – in view of [35, Lemma 3.2] – the image of a unique morphism $[\mathcal{A}'(\triangleright w)]_{w \in \Sigma^*} : \coprod_{\Sigma^*} I \to \mathcal{A}'(\mathbf{st})$ obtained via the universal property of the coproduct of $\Sigma^*$-many copies of $I$. A generic algorithm for computing $\text{Reach} \, \mathcal{A}'$ is explained in more detail in [41, §3]: one aims to find a finite $I$-generating family of words of $\mathcal{A}'(\mathbf{st})$, as we define now.

**Definition 17.** Given $W \subseteq \Sigma^*$ write $\mathcal{A}'(\triangleright W)$ for the $(\mathcal{E}, \mathcal{M})$-image of the morphism $[\mathcal{A}'(\triangleright w)]_{w \in W} : \coprod_W I \to \mathcal{A}'(\mathbf{st})$. A

finite $I$-generating family of words of $\mathcal{A}'(\mathbf{st})$ is a finite set $W \subseteq \Sigma^*$ such that $(\text{Reach} \, \mathcal{A}')(\mathbf{st}) \cong \mathcal{A}'(\triangleright W)$.

The idea of the generic algorithm for computing $\text{Reach}(\mathcal{A}')$ is to construct an increasing sequence of $\mathcal{M}$-subobjects $\mathcal{A}'(\triangleright W_0) \to \mathcal{A}'(\triangleright W_1) \to \dots \to \text{Reach}(\mathcal{A}')(\mathbf{st})$ – starting with $W_0 = \{\varepsilon\}$, and, while there is some $w \in W_i$ and $\sigma \in \Sigma$ that makes this image strictly increase, one adds $w\sigma$ to $W_{i+1}$. Under the right assumptions, this sequence stabilizes in finitely many steps and yields $\text{Reach}(\mathcal{A}')$.

For $R$-weighted automata, finding an $I$-generating family for the forward module of an automaton $\mathcal{A}'$ means finding a finite set $W$ of words such that any reachable configuration of $\mathcal{A}'$ is a linear combination of configurations reached by following some word in $W$. This can be achieved by starting with $W = \{\varepsilon\}$ and adding words to $W$ as long as this strictly increases the module of $W$-reachable configurations in $\mathcal{A}'(\mathbf{st})$.

If $R$ is a field, then the algorithm just described is precisely the usual minimization algorithm for $R$-weighted automata, and it has polynomial-time complexity in the dimension of the minimized automaton because any strictly increasing chain of vector spaces $V_0 \subset \dots \subset V_n = (\text{Reach} \, \mathcal{A}')(\mathbf{st})$ must have length at most the dimension of $(\text{Reach} \, \mathcal{A}')(\mathbf{st})$. But if $R$ is not a field, say if $R = \mathbb{Z}$ and $\text{Reach}(\mathcal{A}')(\mathbf{st}) = \mathbb{Z}$, then there exist chains of strictly increasing submodules of $\mathbb{Z}$ of arbitrary lengths, despite $\mathbb{Z}$ having rank 1. For example, for all $n > 0$, we have the chain $0 \subsetneq \langle 2^n \rangle \subsetneq \langle 2^{n-1} \rangle \subsetneq \dots \subsetneq \langle 1 \rangle = \mathbb{Z}$. To avoid this complexity pitfall, [18] develops the following strategy for $\mathbb{Z}$-weighted automata: they first compute a $\mathbb{Q}$-generating family of words $W$ for the corresponding $\mathbb{Q}$-weighted automaton, so as to first fill-up the rank of the module of $\mathbb{Q}$-reachable configurations, and only afterwards, the set $W$ is completed to an $R$-generating family.

In the remainder of this section we generalize this idea beyond $\mathbb{Z}$-automata to the abstract setting of Assumption 12.

The functor $\mathcal{F}$ already allows us to transform a $(\mathbf{C}, I, O)$-automaton into a $(\mathbf{D}, \mathcal{F}I, \mathcal{F}O)$-automaton. Furthermore, following [35, Lemma 3.4], the adjoint functors $\mathcal{F}$ and $\mathcal{G}$ can be lifted to adjoint functors $\mathcal{F}_b$ and $\mathcal{G}^\sharp$ between the categories $\text{Auto}(\mathbf{C}, I, \mathcal{F}O)$ and $\text{Auto}(\mathbf{D}, \mathcal{F}I, \mathcal{F}O)$, for which we recall the definitions in Appendix F. To understand the gist of Algorithm 3, we just recall that given a $(\mathbf{D}, \mathcal{F}I, \mathcal{F}O)$-automaton $\mathcal{A}$, the $(\mathbf{C}, I, \mathcal{F}O)$-automaton $\mathcal{G}^\sharp(\mathcal{A})$ with state object $\mathcal{G}(\mathcal{A}(\mathbf{st}))$ is given below, where $\mathcal{A}(\triangleright)^\sharp = \mathcal{G}\mathcal{A}(\triangleright) \circ \eta_I$ corresponds to $\mathcal{A}(\triangleright): \mathcal{F}I \to \mathcal{A}(\mathbf{st})$ via the adjunction:

$$ I \xrightarrow{\mathcal{A}(\triangleright)^\sharp} \mathcal{G}\mathcal{A}(\mathbf{st}) \underset{\mathcal{G}\mathcal{A}(\triangleright)}{\stackrel{\mathcal{G}\mathcal{A}(a)}{\rightleftharpoons}} \mathcal{F}O. $$

The crucial property of the functor $\mathcal{G}^\sharp$ is that it preserves observable automata, that is, automata $\mathcal{A}$ such that $\mathcal{A} \cong \text{Obs} \, \mathcal{A}$, see Appendix F for full proofs. For this reason, $\text{Reach}(\mathcal{G}^\sharp(\text{Obs} \, \mathcal{A}))$ is a minimal automaton, which happens to come from a minimal $(\mathbf{C}, I, O)$-automaton whenever the language accepted by $\mathcal{A}$ factors through $\mathcal{F}$. We can now
state the generic Algorithm 3, which aims to compute a generating family of words for Reach($G^#(\text{Obs } A)$), starting in $D$ and completing it in $C$. The algorithm only describes the steps to compute the state-space of the minimal automaton. Its transitions are easily inferred from the generating family of words, as explained, in the categorical setting, in [41, Algorithm 2].

**Algorithm 3** (within Assumption 12) Transforming a (D, FI, FO)-automaton into a (C, I, O)-one

**Input:** a (D, FI, FO)-automaton $\mathcal{A}$ recognizing $\mathcal{L}$

**Output:** if $\mathcal{L} = \mathcal{F} \circ \mathcal{L}'$ for some (C, I, O)-language $\mathcal{L}'$:

(Min $\mathcal{L}'$)(st);

otherwise: $w \in \Sigma^*$ such that $\mathcal{L}(\triangleright w \triangleleft) \notin \mathcal{F}[\mathcal{C}(I, O)]$
// Merge equivalent states to obtain $\mathcal{A}'$

1: compute $\mathcal{A}' = \text{Obs}_{(\mathcal{E}_D, \mathcal{M}_D)} \mathcal{A}$

// Compute an FI-generating family of words
for $\mathcal{A}'(\text{st})$ in D

2: $W := \{\epsilon\}$

3: **while** there is some $(w, \sigma) \in W \times \Sigma$ s.t. the $(\mathcal{E}_D, \mathcal{M}_D)$-images $\mathcal{A}'(\triangleright W)$ and $\mathcal{A}'(\triangleright (W \cup \{w\sigma\}))$ are not isomorphic **do**

4: if $\mathcal{A}'(\triangleright w\sigma\triangleleft) \notin \mathcal{F}[\mathcal{C}(I, O)]$ **then return** $w\sigma$

5: $W := W \cup \{w\sigma\}$

6: **end while**

// Complete W into an I-generating family
of words for $\mathcal{G}\mathcal{A}'(\text{st})$ in C

7: **while** there is some $(w, \sigma) \in W \times \Sigma$ s.t. the $(\mathcal{E}_C, \mathcal{M}_C)$-images $\mathcal{G}^#(\mathcal{A}')(\triangleright W)$ and $\mathcal{G}^#(\mathcal{A}')(\triangleright (W \cup \{w\sigma\}))$ are not isomorphic **do**

8: if $\mathcal{A}'(\triangleright w\sigma\triangleleft) \notin \mathcal{F}[\mathcal{C}(I, O)]$ **then return** $w\sigma$

9: $W := W \cup \{w\sigma\}$

10: **end while**

// (Min $\mathcal{L}'$)(st) is the space of W-reachable
states of $\mathcal{G}\mathcal{A}'(\text{st})$ in C

11: **return** the $(\mathcal{E}_C, \mathcal{M}_C)$-image $\mathcal{G}^#(\mathcal{A}')(\triangleright W)$

**Theorem 18.** *Algorithm 3 is correct<fnref n="1" /> and reduces the problem of learning minimal (C, I, O)-automata to that of learning minimal (D, FI, FO)-automata.*

We briefly describe Algorithm 3 in the case of R-weighted setting, i.e. for $\mathbf{C} = \text{Mod}_R^{\mathcal{I}}$ and $\mathbf{D} = \text{Mod}_K$ both equipped with the (surjections, injections) factorization system, $\mathcal{F} = \mathbb{R}^{-1}$ and $I = O = R$ so that $\mathcal{F}I = \mathcal{F}O = K$. We focus in particular on the case $R = \mathbb{Z}$ that was developed in [18].

The algorithm starts with a K-weighted automaton $\mathcal{A}$ (equivalently a $(\text{Vec}_K, K, K)$-automaton) recognizing a K-weighted language $\mathcal{L}$. On line 1, its equivalent states are first merged, thus computing its backward conjugate $\mathcal{A}'$ – a standard procedure whose complexity is linear in the dimension of $\mathcal{A}'(\text{st})$, as described, for example, in [34].

On lines 2 to 6, we start with $W = \{\epsilon\}$ and add $w\sigma$ (with $w \in W$ and $\sigma \in \Sigma$) to W whenever $\mathcal{A}'(\triangleright w\sigma)$ is not in the K-span $\langle \mathcal{A}'(\triangleright w') | w' \in W \rangle_K$. The number of words added to W then is bounded by the dimension of the vector space

(Min $\mathcal{L}$)(st). If at any point some $w\sigma$ is such that $\mathcal{A}'(\triangleright w\sigma\triangleleft) \notin \mathbb{R}$, the algorithm stops and outputs $w\sigma$ as a counterexample as $\mathcal{L}(\triangleright w\sigma\triangleleft) \notin \mathbb{R}$.

On lines 7 to 10, we continue expanding the set $W$ obtained above by adding $w\sigma$ to $W$ whenever $\mathcal{A}'(\triangleright w\sigma)$ is not in the R-span $\langle \mathcal{A}'(\triangleright w') | w' \in W \rangle_R$. It is not obvious how this can actually be checked: for $R = \mathbb{Z}$, the authors of [18] make use of the so-called *Smith Normal Form* of a matrix, which can be computed in polynomial time. Again, any counterexample to $\mathcal{L}$ actually being R-weighted interrupts the algorithm. The number of words added to $W$ in the second while loop is now bounded by the maximum length of certain strict chains of submodules $M_0 \subset \dots \subset M_n$, where $M_0$ and $M_n$ are fixed and of rank the dimension of $(\text{Min } \mathcal{L})(\text{st})$. For $R = \mathbb{Z}$, this maximum length is bounded polynomially in this rank and the bit-size of the encoding of $\mathcal{A}$ [18]. Requiring more generally that $R$ be Noetherian – this is the case in particular of PIDs and Dedekind domains – ensures that such chains will at least always be finite when $\mathcal{L}'$ is computed by a K-weighted automaton, and thus that the algorithm will terminate.

Finally line 11 is reached if and only if $\mathcal{L} = \mathbb{R}^{-1}\mathcal{L}'$ for some R-weighted language $\mathcal{L}'$. In this case, a representation of $(\text{Min } \mathcal{L}')(\text{st})$ is extracted from the generating family $W$. What this representation will actually be varies depending on $R$: for $R = \mathbb{Z}$ and when $\mathcal{L}'$ is computed by a Q-WA, $(\text{Min } \mathcal{L}')(\text{st})$ has a basis which can be computed using the *Smith Normal Form* [18]. But for other rings $R$ such a basis may not exist. For $R$ a Dedekind domain we have mentioned in Section III-C that when $(\text{Min } \mathcal{L}')(\text{st})$ is finitely-generated with rank $n$, it has a pseudo-basis of size $n$ which gives rise by Proposition 10 to an R-WA with $n+1$ states.

The main optimization of Algorithm 3 with respect to the usual learning algorithm lies in the result stated in Lemma 19, which generalizes the following key observation from the R-weighted setting: the R-module of W-reachable configurations in $\mathcal{A}'$ may increase during the second **while** loop, but the corresponding K-vector space of W-reachable configurations does not, therefore the module's rank is also fixed.

**Lemma 19.** *Let $W_i \subseteq W_{i+1} \subseteq \Sigma^*$ be any two consecutive values of W during Algorithm 3's second **while** loop (lines 7 to 10), and write $m_i: \mathcal{G}^#(\mathcal{A}')(\triangleright W_i) \to \mathcal{G}^#(\mathcal{A}')(\triangleright W_{i+1})$ for the $\mathcal{M}_C$-morphism between the corresponding $(\mathcal{E}_C, \mathcal{M}_C)$-images. Then, $Fm_i$ is an isomorphism in D.*

The genericity of Algorithm 3 leaves open three questions that should be addressed to get an actual implementation. The answers depend on the category C in which we work.

**Questions 20.** 1) What are the properties of $(\text{Min } \mathcal{L})(\text{st})$ (when $\mathcal{L}$ is recognizable) and how can these be used to represent it in memory? For $\mathbf{C} = \text{Mod}_{\mathbb{Z}}$, this was the existence of a basis for $(\text{Min } \mathcal{L})(\text{st})$.

2) How one should compute factorizations: how should it be checked that two $(\mathcal{E}_C, \mathcal{M}_C)$ images, as on line 7, coincide

<footnote n="1">¹We do not mention termination here but it could also be encompassed by the categorical framework, in a similar fashion to what is done in [22].</footnote>
and how should the representation of $(\text{Min } \mathcal{L})(\text{st})$ chosen above be deduced from the generating family of words $W$? In $\mathbf{C} = \text{Mod}_{\mathbb{Z}}$, we mentioned the answer relied on the *Smith Normal Form*.

3) Knowing Lemma 19, can the number of words added to $W$ in the second **while** loop be bounded, so that the overall complexity of the reduction can be bounded as well?

In the next section we answer these questions in the case $\mathbf{C} = \text{Mod}_{\mathcal{O}_K}^{\text{tf}}$, where $\mathcal{O}_K$ is a number ring.

## VI. POLYNOMIAL-TIME ALGORITHM FOR THE EXACT LEARNING OVER NUMBER RINGS

We give a concrete implementation of the general algorithm developed in Section V in the case of automata weighted over number rings, thereby proving Theorem 2.

Throughout this section, $K$ is a number field of degree $d$, and $\mathcal{O}_K$ is its ring of integers. See Appendices A and B for extended preliminaries and examples. Performing operations in $\mathcal{O}_K$ typically requires a suitable representation, such as a compactly represented primitive element. Following [42, p. 13], we require what we call a *full representation of $\mathcal{O}_K$, described in more detail in Section VI-D below*.

**Theorem 2.** *Given a full representation of $\mathcal{O}_K$, exact learning of $\mathcal{O}_K$-weighted automata is within polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of $K$ and the logarithm of its discriminant.*

Algorithm 4 implements a procedure, analogous to [18, Algorithm 6], which computes, given a K-WA, an equivalent $\mathcal{O}_K$-WA if possible, and returns a counterexample otherwise.

Lines 1 to 8 of Algorithm 4 implement Algorithm 3 in the specific case of $(\text{Mod}_{\mathcal{O}_K}^{\text{tf}}, \mathcal{O}_K, \mathcal{O}_K)$-automata, by answering Questions 20 in this setting. While an instantiation of Algorithm 3 only computes a minimal $\mathcal{O}_K$-modular automaton, in practice we are interested in $\mathcal{O}_K$-weighted automata. This is why Algorithm 4 performs an additional step and calls Algorithm 6, in order to transform an $\mathcal{O}_K$-modular automaton into an $\mathcal{O}_K$-weighted one.

We now first give an overview of Algorithm 4, then give more details in Sections VI-A and VI-B, and prove its polynomial-time complexity in Sections VI-C and VI-D.

Let $\mathcal{A} = (Q, \mathcal{A}(\triangleright), (\mathcal{A}(\sigma))_{\sigma \in \Sigma}, \mathcal{A}(\triangleleft))$ be a $K$-weighted automaton, and write $n = |Q|$. Recall from Section III-B that the forward and backward spaces of $\mathcal{A}$ are the subspaces of $K^n$ consisting of all reachable and observable vectors, respectively. That is, the forward space is the $K$-span of $\{\mathcal{A}(\triangleright w) | w \in \Sigma^*\}$ and the backward space is that of $\{\mathcal{A}(w \triangleleft) | w \in \Sigma^*\}$. Similarly, the forward $\mathcal{O}_K$-module of $\mathcal{A}$ is the $\mathcal{O}_K$-span of $\{\mathcal{A}(\triangleright w) | w \in \Sigma^*\}$.

We now give an overview of Algorithm 4 and its ingredients. We refer to the corresponding steps of Algorithm 3 in blue.

Line 1 of Algorithm 3. Algorithm 4 first conjugates $\mathcal{A}$ with a matrix $B$, whose $m$ columns form a basis of the backward space of $\mathcal{A}$. Denote by $\mathcal{A}'$ the resulting automaton, defined

## Algorithm 4 Computing an $\mathcal{O}_K$-WA from a K-WA

**Input:** A $K$-WA $\mathcal{A} = (Q, \mathcal{A}(\triangleright), (\mathcal{A}(\sigma))_{\sigma \in \Sigma}, \mathcal{A}(\triangleleft))$
// Find a basis $B$ of the backward space

1: $W_B = \{\varepsilon\}$

2: **while** there is a $(\sigma, w) \in \Sigma \times W_B$ such that $\mathcal{A}(\sigma w \triangleleft) \notin \langle \mathcal{A}(w \triangleleft) | w \in W_B \rangle_K \text{ do } W_B = W_B \cup \{\sigma w\} \text{ end}$

3: $B = [\mathcal{A}(w_1 \triangleleft) \cdots \mathcal{A}(w_m \triangleleft)]$ if $W_B = \{w_1, \dots, w_m\}$
// Conjugate $\mathcal{A}$ with $B$ to obtain $\mathcal{A}'$

4: Define $\mathcal{A}' = (Q', \mathcal{A}'(\triangleright), (\mathcal{A}'(\sigma))_{\sigma \in \Sigma}, \mathcal{A}'(\triangleleft))$ such that, for all $\sigma \in \Sigma$,

$$ \mathcal{A}'(\triangleright) = \mathcal{A}(\triangleright)B, B\mathcal{A}'(\sigma) = \mathcal{A}(\sigma)B, B\mathcal{A}'(\triangleleft) = \mathcal{A}(\triangleleft) $$

// Compute a generating set of the forward module of $\mathcal{A}'$ via Algorithm 5

5: **match** the output of Algorithm 5 ran on $\mathcal{A}'$ with

6: **some** $w \in \Sigma^*$: **return** $w$

7: **some** $W \subset \Sigma^*$:

8: Extract a pseudo-basis $\{(v_i, a_i) | 1 \le i \le \ell\}$ for the forward $\mathcal{O}_K$-module $\mathcal{R}$ using pseudo-HNF.
// Compute an (almost) minimal generating set for the forward module of $\mathcal{A}'$

9: Call Algorithm 6 on the pseudo-basis, obtaining a generating set $\{y_i | 1 \le i \le \ell+1\}$.
Let $F := (y_1 \cdots y_{\ell+1})^t$
// Conjugate $\mathcal{A}'$ with $F$ to obtain $\mathcal{A}''$

10: Find $\mathcal{A}'' = (Q, \mathcal{A}''(\triangleright), (\mathcal{A}''(\sigma))_{\sigma \in \Sigma}, \mathcal{A}''(\triangleleft))$ such that, for all $\sigma \in \Sigma$,

$$ \mathcal{A}''(\triangleright)F = \mathcal{A}'(\triangleright), \mathcal{A}''(\sigma)F = F\mathcal{A}'(\sigma), F\mathcal{A}''(\triangleleft) = \mathcal{A}(\triangleleft) $$

11: **return** $\mathcal{A}''$

in line 4 of Algorithm 4. Assuming that $\mathcal{A}$ has an equivalent $\mathcal{O}_K$-WA, the forward $\mathcal{O}_K$-module of $\mathcal{A}'$ is a submodule of $\mathcal{O}_K^m$ (this matters when it comes to the complexity of the algorithm). Indeed, for all words $w \in \Sigma^*$, by definition of $\mathcal{A}'$, $\mathcal{A}'(\triangleright w) = \mathcal{A}(\triangleright w)B = [\mathcal{A}(\triangleright ww_1 \triangleleft) \cdots \mathcal{A}(\triangleright ww_m \triangleleft)]$, and this vector only contains values from $\mathcal{O}_K$, by assumption.

Lines 2 to 10 of Algorithm 3. Next, Algorithm 4 calls Algorithm 5, which, on an input WA with $m$ states, either returns a generating set for the forward $\mathcal{O}_K$-module, if this forward module lies within $\mathcal{O}_K^m$, or returns a counterexample, otherwise. Note that the generating set may be very large.

Line 11 of Algorithm 3. If it were possible to extract a basis from the generating set for the forward $\mathcal{O}_K$-module, then we could simply conjugate $\mathcal{A}'$ with the matrix whose rows form that basis, directly producing an $\mathcal{O}_K$-automaton. This is precisely the approach taken in the case of $\mathbb{Z}$ in [18, Algorithm 6]. However, the essential difference, when moving from $\mathbb{Z}$ to $\mathcal{O}_K$, is that $\mathcal{O}_K$-submodules of $\mathcal{O}_K^m$ may fail to have a basis, precisely because $\mathcal{O}_K$ is not a PID in general. However, $\mathcal{O}_K$ is still a Dedekind domain, and we can use the notion of pseudo-basis for $\mathcal{O}_K$-modules, recalled in Section II.

Pseudo-bases answer Question 20.1 for number rings: how to represent the minimal $\mathcal{O}_K$-modular automaton?
The pseudo-Hermite Normal Form (pseudo-HNF) is a means to compute a pseudo-basis of an $O_K$-submodule of $O_K^m$, starting from a generating set [43, Sec. 1.4], also see [44, Thm. 2.4]. This is analogous to using the HNF for computing a $\mathbb{Z}$-basis for a $\mathbb{Z}$-submodule of $\mathbb{Z}^m$. We provide an introduction to HNF and $\mathbb{Z}$-modules in Appendix G-A, and we give details about pseudo-HNF and $O_K$-modules in Section VI-C. Algorithm 4 uses the pseudo-HNF in Line 8 to compute a pseudo-basis from the generating set output by Algorithm 5.

The pseudo-HNF answers Question 20.2 for number rings: how to represent images of linear maps computationally?

The pseudo-basis obtained in this way gives a minimal representation of the forward module of $\mathcal{A}'$. However, if we were to conjugate $\mathcal{A}'$ with the pseudo-basis directly, then we would not be sure to obtain an $O_K$-weighted automaton, but only a $K$-weighted automaton. This is because the fractional ideals in the pseudo-basis may contain elements outside $O_K$. A main added ingredient in our algorithm, compared to [18, Algorithm 6], is that we compute, starting from a size-$\ell$ pseudo-basis for a submodule $M$ of $O_K^\ell$, an $O_K$-generating set for $M$ of size at most $\ell+1$ (Algorithm 6). Conjugating $\mathcal{A}'$ with a matrix whose rows are formed by this generating set produces an $O_K$-weighted automaton whose number of states is at most one more than the number of states of the canonical minimal $K$-weighted automaton equivalent to $\mathcal{A}$.

This last added ingredient is not encompassed by Algorithm 3; it is an additional step taken to transform the resulting minimal $O_K$-modular automaton into an $O_K$-weighted automaton, and can also be understood as a constructive version of the generic Proposition 10, which holds for all Dedekind domains.

### A. Ideals in Number Rings

The ring $O_K$ of algebraic integers in $K$ is a $\mathbb{Z}$-module of rank $[K:\mathbb{Q}]$. An integral basis of $O_K$ is a $\mathbb{Z}$-basis $\{\omega_1, \dots, \omega_d\}$ of $O_K$ as a $\mathbb{Z}$-module, that is,

$$O_K = \mathbb{Z}\omega_1 \oplus \dots \oplus \mathbb{Z}\omega_d. \qquad (1)$$

Since $\mathbb{Z}$ is a PID, each $\mathbb{Z}$-submodule of $O_K$ is finitely generated; by this, each ideal $\mathfrak{a} \subseteq O_K$ can be viewed as a finitely generated $\mathbb{Z}$-module. Every ideal $\mathfrak{a} \subseteq O_K$ is even a full-rank $\mathbb{Z}$-submodule of $O_K$; its norm, denoted by $N(\mathfrak{a})$, is defined as $|O_K/\mathfrak{a}|$, see [45, Prop. 4.6.3]. The fractional ideals of $O_K$ are the finitely generated full-rank $\mathbb{Z}$-submodules $\mathfrak{b}$ of $K$. For clarity, we sometimes refer to ideals $\mathfrak{a} \subseteq O_K$ as integral ideals. For any fractional ideal $\mathfrak{b}$, there exists $r \in O_K$ such that $r\mathfrak{b}$ is integral.

The number rings $O_K$ are not in general PIDs, see Examples 27 and 28 in Appendix B. Still, the ring of integers $O_K$ of a number field $K$ is a Dedekind domain, see for instance [43, Prop. 1.2.3]. Moreover, each fractional ideal $\mathfrak{b}$ can be written uniquely as a product of powers of prime ideals. We provide a detailed discussion about representation and complexity of manipulating algebraic numbers and ideals in Appendix G. Since $O_K$ is a Dedekind domain, the set of fractional ideals of $K$ forms a commutative group under ideal multiplication with

identity element $O_K$, see for example [45, Thm. 4.6.14]. We note in passing that ideals in $O_K$ when seen as $O_K$-modules are finitely generated, but might not have a basis.

### B. Modules Over Number Rings

After recalling the notion of pseudo-basis from [46], we state several facts we use about modules over number rings. Let $M \subseteq O_K^n$ be an $O_K$-module. Let $v_1, \dots, v_k \in K^n$ and $a_1, \dots, a_k$ be fractional ideals, we say that $\{(v_i, a_i) | 1 \le i \le k\}$ is a pseudo-generating set of $M$ if $M = a_1v_1 + \dots + a_kv_k$, and we say that it is a pseudo-basis of $M$ if $M = a_1v_1 \oplus \dots \oplus a_kv_k$. By [43, Cor. 1.2.25], every $O_K$-module $M \subseteq O_K^n$ has a pseudo-basis.

**Lemma 21** ([43, Lemma 1.2.20]). If $\mathfrak{a}$ and $\mathfrak{b}$ are fractional ideals of $O_K^n$, there is an isomorphism of $O_K$-modules such that $\mathfrak{a} \oplus \mathfrak{b} \simeq O_K \oplus \mathfrak{a}\mathfrak{b}$.

We outline the key elements required to prove Lemma 21 in Appendix H. We employ similar arguments to those used in the outline in Algorithm 6. The following proposition follows from iteratively applying Lemma 21.

**Proposition 22** ([43, Prop. 1.2.19]). Let $M$ be a finitely generated, torsion-free $O_K$-module of rank $n$. Then there exists a fractional ideal $\mathfrak{b}$ of $O_K$ such that $M \simeq O_K^{n-1} \oplus \mathfrak{b}$.

As each fractional ideal $\mathfrak{b}$ of $O_K$ can be generated by two elements, $M$ in the above proposition has a generating set of cardinality $n+1$.

To compute a pseudobasis for an $O_K$-module, we recall a definition of pseudo-HNF [43, Sec. 1.4]. For simplicity we only give the definition for full-rank modules; it can be extended to lower-rank modules. Let $M$ be a full-rank $O_K$-module of $O_K^n$ and $\{(v_i, a_i) | 1 \le i \le k\}$ be a pseudo-generating set for $M$; in particular, $k \ge n$. Let $A = [a_{i,j}]_{1 \le i \le n, 1 \le j \le k}$ be the $n \times k$ matrix whose $i$-th column is $v_i$. By [43, Thm. 1.4.6], there exist fractional ideals $b_1, \dots, b_k$ and a $k \times k$ matrix $U$ such that (1) $AU = [0|H]$ where $H$ is upper triangular with 1 on the diagonal, and (2) $\{(h_i, c_i) | 1 \le i \le n\}$ is a pseudo-basis for $M$, where $h_i$ is the $i$-th column of $H$ and $c_i := b_{k-n+i}$ for $1 \le i \le n$.

By [43, Thm. 1.4.9], the ideals $c_i$ in this computation are unique and only depend on $M$ and not on the basis element $h_i$. The ideal $\prod_{i=1}^n c_i$ corresponds to the ideal $\mathfrak{b}$ in Proposition 22. It is integral, and can be computed from the minor ideals of $A$ and the fractional ideals $a_i$. The $r \times r$ minor ideals are defined, for $I \subseteq \{1, \dots, n\}$ and $J \subseteq \{1, \dots, k\}$ of size $r$, as

$$\mathfrak{d}_{I,J} := \det([a_{i,j}]_{i \in I, j \in J}) \prod_{j \in J} a_j. \qquad (2)$$

Then $\prod_{i=1}^n c_i$ is the sum of the $a_i$'s and all $n \times n$ minor ideals of $A$ [43, Def. 1.4.8 and Thm. 1.4.9]. Given a full representation of $O_K$, the main Theorem of [42] shows that the pseudo-HNF for full-rank modules is computable within polynomial-time. A crucial lemma in our learning algorithm is the computation of a reasonably small generating set of $O_K$-submodules of $O_K^n$ from a pseudo-basis:
**Lemma 23.** Let $\{(a_i, v_i) | 1 \le i \le n\}$ be a pseudo-basis for an $O_K$-module $M \subseteq O_K^n$. Given a full representation of $O_K$, a generating set of cardinality at most $n+1$ is computable within polynomial time in the size of the input pseudo-basis.

Algorithm 6 provides a high-level description of the steps required in Lemma 23 (the detailed proof can be found in Appendix H). The derived complexity bound relies on the notion of ideal factor refinement [47, Alg. 5.6 and Prop. 5.7] and an adaptation of [48, Lemma 5.2.2] and [43, Props. 1.3.10 and 1.3.12].

### C. Fast Computation of an Almost Minimal Generating Set

As described in the overview, Algorithm 4 calls Algorithm 5 to compute a generating set for the forward $O_K$-module of $A'$, if the forward module lies within $O_K^m$.

In Lemma 24 we establish an upper bound on the length of strictly increasing chains of $O_K$-submodules of $O_K^n$, which is a key result in the complexity analysis of Algorithm 5. A similar bound for $\mathbb{Z}$-submodules of $\mathbb{Z}^m$ is derived in [18, Prop. 3.1] using the elementary divisor theorem. There, the proof relies on the fact that if $M \subset N \subseteq \mathbb{Z}^m$ are $\mathbb{Z}$-modules of equal rank $r \le m$, there is a basis $v_1, \dots, v_r$ of $N$ and nonzero scalars $d_1, \dots, d_r \in \mathbb{Z}$ such that $N = \mathbb{Z}v_1 \oplus \dots \oplus \mathbb{Z}v_r$ and $M = \mathbb{Z}d_1v_1 \oplus \dots \oplus \mathbb{Z}dcephar1.5em>d_rv_r$. The scalars $d_i$ are the primary divisors of the quotient module $N/M \cong \mathbb{Z}/(d_1\mathbb{Z}) \oplus \dots \oplus \mathbb{Z}/(d_r\mathbb{Z})$. Since $N/M$ is a finite group, using Lagrange's Theorem, its cardinality gives an upper bound on the length of strictly increasing chains of modules between $M$ and $N$. In [18, Prop. 3.1], the cardinality of $N/M$ is derived by computation of primary divisors through the Smith Normal Form (a combination of an HNF and an HNF of the transpose [45, Sec. 2.4.4]).

We generalize this to the number ring setting as follows.

**Lemma 24.** Let $\{(a_i, v_i) | 1 \le i \le m\}$ be a pseudo-generating set for a full-rank $O_K$-module $M \subseteq O_K^n$. Let $A$ be the $n \times m$ matrix whose $i$-th column is $v_i$. Let $\delta$ be the sum of all $n \times n$ minor ideals of $A$ and of the $a_i$'s. Then all strictly increasing chains of $O_K$-modules $M = M_1 \subset M_2 \subset \dots \subset M_{k-1} \subset M_k \subseteq O_K^n$ have length at most $\log(\mathcal{N}(\delta))$.

This lemma is the answer, in the number ring setting, to Question 20.3: how to bound the length of strictly increasing chains of $O_K$-submodules?

We briefly argue that the HNF and pseudo-HNF suffice to establish complexity bounds for [18, Algorithm 5] and for our analogous Algorithm 5 over number fields. Both procedures employ a two-pass search strategy: (1) The first pass identifies elements that increase the rank of the sought-after module. (2) The second pass augments the module until the complete forward module is constructed.

This two-pass approach is noted to be crucial for ensuring polynomial time already in the $\mathbb{Z}$ setting. The first pass induces a strictly increasing sequence of vector spaces, and has length at most $m$. Given the $\mathbb{Z}$-module $M$ at the end of the first phase, the second phase may iterate over as many times as

there are strictly increasing $\mathbb{Z}$-modules of rank $r$ equal to that of $M$ and lying between $M$ and $\mathbb{Z}^m$. As described above computing an upper bound on such chains was proved by the elementary divisor theorem and the SNF in [18, Prop. 3.1]. We argue that $M$ can be assumed to be full-rank in our algorithms, so that $|\mathbb{Z}^m/M|$ is computable through a full-rank HNF (see Lemma 49 in the appendix). Because the minimization over both $\mathbb{Q}$ and $K$ is in polynomial time, we can indeed assume without loss of generality that the input automaton is minimal so that its forward module is full-rank. In fact in the reduction of the learning over a number ring to the learning over its field of fractions, this property is even automatically satisfied.

### D. Overall Complexity of Algorithms 4 and 5

Before stating the complexity of Algorithms 4 and 5, we first outline the elements needed for the full representation of $O_K$. Let $C_K := d^4(\log d + \log \Delta)$ such that $d = [K:\mathbb{Q}]$ and $\Delta$ is the discriminant of $K$; see Appendix G for more details on the discriminant of $K$ and the symbolic and regular representation of algebraic numbers. A full representation of $O_K$ consists of an integral basis $\Omega$ of $O_K$, as in (1), where $1 \in \Omega$, together with a primitive element $\theta$, whose minimal polynomial $m_\theta = x^d + \sum_{i=0}^{d-1} a_i x^i$ is such that $\log(\prod_{1 \le i \le j \le d} |\sigma_i(\theta) - \sigma_j(\theta)|^2) \le C_K$, where the $\sigma_i(\theta)$ are the $d$ distinct zeros of $m_\theta$, and the bit length of $a_i$ is bounded by $C_K$. It is shown in [42, pp. 590–591] that there exists such a primitive element $\theta$, which is a sum of a subset of $\Omega$. The elements of $\Omega$ and $\theta$ are given both in symbolic and regular representations. We note that while [42, pp. 590–591] require more extensive precomputed data, we omit these prerequisites, as they are computable in polynomial time from $\Omega$ and $\theta$.

The detailed complexity analysis of Algorithms 4 and 5, stated below, can be found in Appendix H.

**Lemma 25.** Given a full representation of $O_K$, Algorithms 4 and 5 run within polynomial time in the size of the input automaton, the degree of $K$ and the logarithm of its discriminant.

Recall that the principal ideal problem (PIP) is to decide if an integral ideal $a \subseteq O_K$, given by its basis as a $\mathbb{Z}$-module, is principal. The PIP can be solved in quantum polynomial time [32]. To conclude this paper, we relate this problem to computing minimal $O_K$-WA; the proof is in Appendix H.

**Proposition 26.** Deciding whether an $O_K$-WA is state-minimal is PIP-hard.

Number rings play a central role in cryptography, and Proposition 26 can be seen in this light: a number of cryptographic schemes rely on the hardness of finding the generator of a principal ideal [32, §6].

This research has received financial support from the Agence Nationale de la Recherche (ANR), grants ANR-23-CE48-0012-01 and ANR-22-CE48-0005, from the European Research Council (ERC) under the European Union's Horizon research and innovation program (grant agreement No. 101167526), and from United Kingdom Research and Innovation (UKRI), grant EP/X033813/.
REFERENCES

[1] D. Angluin, “Learning regular sets from queries and counterexamples,” *Information and Computation*, vol. 75, no. 2, pp. 87–106, 1987. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0890540187900526

[2] L. G. Valiant, “A theory of the learnable,” *Communications of the ACM*, vol. 27, no. 11, pp. 1134–1142, 1984.

[3] F. Vaandrager, “Model learning,” *Communications of the ACM*, vol. 60, no. 2, pp. 86–95, 2017.

[4] D. Peled, M. Vardi, and M. Yannakakis, “Black box checking,” *J. Autom. Lang. Comb.*, vol. 7, no. 2, pp. 225–246, 2002.

[5] C. Higuera, *Grammatical inference : learning automata and grammars.* Cambridge New York: Cambridge University Press, 2010.

[6] T. Berg, O. Grinchtein, B. Jonsson, M. Leucker, H. Raffelt, and B. Steffen, “On the correspondence between conformance testing and regular inference,” in *FASE 2005*, ser. LNCS, vol. 3442, 2005, pp. 175–189.

[7] G. Chalupar, S. Peherstorfer, E. Poll, and J. de Ruiter, “Automated reverse engineering using lego®,” in *WOOT ’14, San Diego, CA, USA, August 19, 2014*. USENIX Association, 2014.

[8] M. Leucker, “Learning meets verification,” in *International Symposium on Formal Methods for Components and Objects*. Springer, 2006, pp. 127–151.

[9] I. Marusic and J. Worrell, “Complexity of equivalence and learning for multiplicity tree automata,” *J. Mach. Learn. Res.*, vol. 16, pp. 2465–2500, 2015. [Online]. Available: https://dl.acm.org/doi/10.5555/2789272.2912078

[10] M. Shahbaz and R. Groz, “Inferring mealy machines,” in *FM 2009: Formal Methods*, A. Cavalcanti and D. R. Dams, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 207–222.

[11] B. Bollig, P. Habermehl, C. Kern, and M. Leucker, “Angluin-style learning of nfa,” in *Proceedings of the 21st International Joint Conference on Artificial Intelligence*, ser. IJCAI’09. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2009, p. 1004–1009.

[12] F. Howar, B. Steffen, B. Jonsson, and S. Cassel, “Inferring canonical register automata,” in *Verification, Model Checking, and Abstract Interpretation*, V. Kuncak and A. Rybalchenko, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 251–266.

[13] F. Aarts, P. Fiterau-Brostean, H. Kuppens, and F. Vaandrager, “Learning register automata with fresh value generation,” in *Theoretical Aspects of Computing - ICTAC 2015*, M. Leucker, C. Rueda, and F. D. Valencia, Eds. Cham: Springer International Publishing, 2015, pp. 165–183.

[14] J. M. Vilar, “Query learning of subsequential transducers,” in *Grammatical Inference : Learning Syntax from Sentences, 3rd International Colloquium, ICGI-96, Montpellier, France, September 25-27, 1996, Proceedings*, ser. Lecture Notes in Computer Science, L. Miclet and C. de la Higuera, Eds., vol. 1147. Springer, 1996, pp. 72–83. [Online]. Available: https://doi.org/10.1007/BFb0033343

[15] J. Moerman, M. Sammartino, A. Silva, B. Klin, and M. Szynwelski, “Learning nominal automata,” in *Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages*, ser. POPL ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 613–625. [Online]. Available: https://doi.org/10.1145/3009837.3009879

[16] D. Angluin and D. Fisman, “Learning regular omega languages,” *Theoretical Computer Science*, vol. 650, pp. 57–72, 2016, algorithmic Learning Theory. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0304397516303760

[17] A. Beimel, F. Bergadano, N. H. Bshouty, E. Kushilevitz, and S. Varricchio, “Learning functions represented as multiplicity automata,” *J. ACM*, vol. 47, no. 3, pp. 506–530, 2000.

[18] A. Buna-Marginean, V. Cheval, M. Shirmohammadi, and J. Worrell, “On Learning Polynomial Recursive Programs,” *Proceedings of the ACM on Programming Languages*, vol. 8, no. POPL, pp. 34:1001–34:1027, Jan. 2024. [Online]. Available: https://dl.acm.org/doi/10.1145/3632876

[19] H. Urbat and L. Schröder, “Automata learning: An algebraic approach,” in *Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science*, ser. LICS ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 900–914. [Online]. Available: https://doi.org/10.1145/3373718.3394775

[20] G. v. Heerdt, M. Sammartino, and A. Silva, “Learning automata with side-effects,” in *Coalgebraic Methods in Computer Science: 15th IFIP WG 1.3 International Workshop, CMCS 2020, Colocated with ETAPS 2020, Dublin, Ireland, April 25–26, 2020, Proceedings.* Berlin, Heidelberg: Springer-Verlag, 2020, p. 68–89. [Online]. Available: https://doi.org/10.1007/978-3-030-57201-3_5

[21] S. Barlocco, C. Kupke, and J. Rot, “Coalgebra learning via duality,” in *Foundations of Software Science and Computation Structures*, M. Bojańczyk and A. Simpson, Eds. Cham: Springer International Publishing, 2019, pp. 62–79.

[22] T. Colcombet, D. Petrișan, and R. Stabile, “Learning Automata and Transducers: A Categorical Approach,” in *29th EACSL Annual Conference on Computer Science Logic (CSL 2021)*, ser. Leibniz International Proceedings in Informatics (LIPIcs), C. Baier and J. Goubault-Larrecq, Eds., vol. 183. Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021, pp. 15:1–15:17. [Online]. Available: https://drops.dagstuhl.de/opus/volltexte/2021/13449

[23] G. v. Heerdt, C. Kupke, J. Rot, and A. Silva, “Learning Weighted Automata over Principal Ideal Domains,” in *Foundations of Software Science and Computation Structures*, J. Goubault-Larrecq and B. König, Eds. Cham: Springer International Publishing, 2020, pp. 602–621.

[24] J. Berstel and C. Reutenauer, *Noncommutative Rational Series with Applications*, ser. Encyclopedia of Mathematics and Its Applications. Cambridge: Cambridge University Press, 2010. [Online]. Available: https://www.cambridge.org/core/books/noncommutative-rational-series-with-applications/ CADC75E4ADDA69E99BB8B0D8FE9AD119

[25] A. Salomaa and M. Soittola, *Automata-theoretic aspects of formal power series*. Springer Science & Business Media, 2012.

[26] C. Martín-Vide and V. Mitrana, *Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back*. CRC Press, 2004, vol. 9.

[27] A. Paz, *Introduction to probabilistic automata*. Academic Press, 1971.

[28] D. Chistikov, S. Kiefer, I. Marusic, M. Shirmohammadi, and J. Worrell, “On restricted nonnegative matrix factorization,” in *43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy*, ser. LIPIcs, I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, and D. Sangiorgi, Eds., vol. 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, pp. 103:1–103:14. [Online]. Available: https://doi.org/10.4230/LIPIcs.ICALP.2016.103

[29] ——, “On rationality of nonnegative matrix factorization,” in *Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19*, P. N. Klein, Ed. SIAM, 2017, pp. 1290–1305. [Online]. Available: https://doi.org/10.1137/1.9781611974782.84

[30] T. Colcombet and D. Petrisan, “Automata minimization: a functorial approach,” in *7th Conference on Algebra and Coalgebra in Computer Science, CALCO 2017, June 12-16, 2017, Ljubljana, Slovenia*, ser. LIPIcs, F. Bonchi and B. König, Eds., vol. 72. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 8:1–8:16. [Online]. Available: https://doi.org/10.4230/LIPIcs.CALCO.2017.8

[31] F. Bergadano and S. Varricchio, “Learning behaviors of automata from multiplicity and equivalence queries,” in *Algorithms and Complexity*, ser. Lecture Notes in Computer Science, M. Bonuccelli, P. Crescenzi, and R. Petreschi, Eds. Berlin, Heidelberg: Springer, 1994, pp. 54–62.

[32] J.-F. Biasse and F. Song, “Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields,” in *Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, ser. Proceedings. Society for Industrial and Applied Mathematics, Dec. 2015, pp. 893–902. [Online]. Available: https://epubs.siam.org/doi/10.1137/1.9781611974331.ch64

[33] M. Broué, *From Rings and Modules to Hopf Algebras*. Springer, 2024.

[34] S. Kiefer, “Notes on Equivalence and Minimization of Weighted Automata,” Sep. 2020. [Online]. Available: http://arxiv.org/abs/2009.01217

[35] T. Colcombet and D. Petrișan, “Automata Minimization: A Factorial Approach,” *Logical Methods in Computer Science*, vol. Volume 16, Issue 1, Mar. 2020. [Online]. Available: https://lmcs.episciences.org/6213/pdf

[36] S. Schröer, “Baer’s result: The infinite product of the integers has no basis,” *Amer. Math. Monthly*, vol. 115, pp. 660–663, 2008.

[37] M. Droste and D. Kuske, “Weighted automata,” in *Handbook of Automata Theory*, J.-É. Pin, Ed. European Mathematical Society Publishing House, Zürich, Switzerland, 2021, pp. 113–150. [Online]. Available: https://doi.org/10.4171/Automata-1/4
[38] J. Adámek, H. Herrlich, and G. E. Strecker, *Abstract and Concrete Categories: The Joy of Cats*, ser. Dover Books on Advanced Mathematics. Dover Publications, Aug. 2009.

[39] J. Adámek, F. Bonchi, M. Hülsbusch, B. König, S. Milius, and A. Silva, “A coalgebraic perspective on minimization and determination,” in *Foundations of Software Science and Computational Structures*, L. Birkedal, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 58–73.

[40] J. Rot, “Coalgebraic minimization of automata by initiality and finality,” *Electronic Notes in Theoretical Computer Science*, vol. 325, pp. 253–276, 2016, the Thirty-second Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXII). [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1571066116300937

[41] Q. Aristote, “Functorial approach to minimizing and learning deterministic transducers with outputs in arbitrary monoids,” Nov. 2023. [Online]. Available: https://ens.hal.science/hal-04172251v3

[42] J.-F. Biasse, C. Fieker, and T. Hofmann, “On the computation of the HNF of a module over the ring of integers of a number field,” *Journal of Symbolic Computation*, vol. 80, pp. 581–615, May 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0747717116300736

[43] H. Cohen, *Advanced topics in computational number theory*. Springer, 2000.

[44] W. Bosma and M. Pohst, “Computations with finitely generated modules over Dedekind rings,” in *Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation*, ser. ISSAC '91. New York, NY, USA: Association for Computing Machinery, 1991, p. 151–156. [Online]. Available: https://doi.org/10.1145/120694.120714

[45] H. Cohen, *A course in computational algebraic number theory*. Springer, 1993.

[46] —, “Hermite and Smith normal form algorithms over Dedekind domains,” *Mathematics of Computation*, vol. 65, no. 216, pp. 1681–1699, 1996. [Online]. Available: https://www.ams.org/mcom/1996-65-216/S0025-5718-96-00766-1

[47] G. Ge, “Recognizing units in number fields,” *Mathematics of computation*, vol. 63, no. 207, pp. 377–387, 1994.

[48] W. Stein, “Algebraic number theory, a computational approach,” *Harvard, Massachusetts*, 2012.

[49] S. Mac Lane, *Categories for the working mathematician*. Springer-Verlag New York Heidelberg Berlin, 1971.

[50] P. D. Domich, R. Kannan, and L. E. Trotter, “Hermite Normal Form Computation Using Modulo Determinant Arithmetic,” *Mathematics of Operations Research*, vol. 12, no. 1, pp. 50–59, Feb. 1987. [Online]. Available: https://pubsonline.informs.org/doi/10.1287/moor.12.1.50

[51] J. Sonn and H. Zassenhaus, “On the theorem on the primitive element,” *The American Mathematical Monthly*, vol. 74, no. 4, pp. 407–410, 1967.

[52] E. Bach, J. Driscoll, and J. Shallit, “Factor refinement,” *Journal of Algorithms*, vol. 15, no. 2, pp. 199–222, 1993.

[53] J. Blömer, “A probabilistic zero-test for expressions involving roots of rational numbers,” in *Algorithms—ESA’98: 6th Annual European Symposium Venice, Italy, August 24–26, 1998 Proceedings 6*. Springer, 1998, pp. 151–162.

[54] J. Buchmann and F. Eisenbrand, “On factor refinement in number fields,” *Mathematics of computation*, vol. 68, no. 225, pp. 345–350, 1999.
# APPENDIX A
## EXTENDED ALGEBRAIC PRELIMINARIES

### A. Commutative Algebra

1) **Rings:** Throughout the paper, 'ring' means 'commutative ring with unit'. That is, a ring $R$ is a set $R$ equipped with binary operations, addition and multiplication, satisfying the following conditions: $R$ is a commutative group under addition, $R$ is a commutative monoid under multiplication, and multiplication is distributive with respect to addition. An element $r$ of $R$ is invertible if there exists $s \in R$ such that $rs = 1$. We write $R^\times$ for the set of invertible elements of $R$.

2) **Modules:** Let $R$ be a ring. An $R$-module is an additive group $M$ equipped with an action $R \times M \to M$, called scalar multiplication, which is unital, associative, and bilinear: for any $r, s \in R$ and $m, n \in M$: $1_R m = m$, $r(sm) = (rs)m$, and both $(r+s)m = rm + sm$ and $r(m+n) = rm + rn$. A submodule of a module $M$ is a subgroup $N$ of $M$ that is invariant under scalar multiplication: for any $r \in R$ and $n \in N$, we have $rn \in N$.

For any subset $S$ of $M$, the *submodule generated by* $S$ is the smallest submodule of $M$ that contains $S$. The *sum of* two submodules $M_1, M_2$ of $M$ is the submodule generated by the union $M_1 \cup M_2$, and is denoted $M_1 + M_2$. If moreover $M_1 \cap M_2 = \{0_M\}$, then $M_1 + M_2$ is a *direct sum*, and it is then denoted $M_1 \oplus M_2$. Note that $R$ itself can be seen as an $R$-module. Its submodules are exactly the *ideals* of $R$, and the ideals generated by a singleton are called *principal*. A *morphism* or *$R$-linear map* between $R$-modules $M$ and $N$ is a group homomorphism $\phi: M \to N$ that respects the actions, i.e., $\phi(rm) = r\phi(m)$ for all $r \in R$ and $m \in M$.

Free modules are essential for the algebraic analysis of $R$-weighted automata. For any (possibly infinite) set $Q$, a *finite $R$-linear combination* is an expression $\sum_{i=1}^n r_i q_i$, with $r_i \in R$ and $q_i \in Q$ for each $1 \le i \le n$; said otherwise, it is a finitely supported function from $Q$ to $R$. The set of finite $R$-linear combinations, equipped with the expected addition and $R$-action, is a first example of a free $R$-module; we denote it by $R^Q$. The elements $1_R \cdot q$, for $q \in Q$, constitute a *canonical basis* for $R^Q$; we identify each $q$ with its corresponding basis element. The *rank* of $R^Q$ is the cardinality of $Q$.

For any $R$-module $M$ and $(x_q)_{q \in Q}$ a $Q$-indexed set of elements of $M$, there exists a unique morphism $\phi: R^Q \to M$ that sends $q$ to $x_q$. The family $(x_q)_{q \in Q}$ is *free* in $M$ if $\phi$ is injective, *generating* for $M$ if $\phi$ is surjective, and a *basis* for $M$ if $\phi$ is bijective. The module $M$ is called *finitely generated* if it has a finite generating family and *free* if it has a basis. An element $m \in M$ has *torsion* if there exists $r \ne 0$ such that $rm = 0$. An $R$-module $M$ is *torsion-free* if there are no non-zero torsion elements. Free $R$-modules are torsion-free, but the converse is not true; for example, the ideal $(2, 1 + i\sqrt{5})$ in the ring $\mathbb{Z}[i\sqrt{5}]$ is not free. Note that a submodule of a torsion-free module is again torsion-free.

3) **Field of fractions:** A ring $R$ is an *integral domain* if it has no zero divisors, i.e., for any $r, s \in R$, if $rs = 0$, then $r = 0$ or $s = 0$. Let $R$ be an integral domain. The *field of fractions* of $R$ is obtained by adding formal inverses for all non-zero elements of $R$: its elements are pairs $r/s$, where $r \in R$ and $s \in R^\times$, and $r/s$ is identified with $r'/s'$ when $rs' = r's$; note that it is in particular an $R$-module. Let $K$ be the field of fractions of $R$. Extending this definition to modules, for any $R$-module $M$, there is a $K$-vector space $R^{-1}M$, called the *localization* or *extension of scalars* of $M$. Its elements are formal fractions $m/r$ of an element $m \in M$ and an element $r \in R^\times$, where we identify $m/r$ and $m'/r'$ if there is $s \in R^\times$ such that $sr \cdot m' = sr' \cdot m$. For any $R$-linear map $f: M \to N$, we obtain a $K$-linear map $R^{-1}f: R^{-1}M \to R^{-1}N$, which maps $m/r$ to $f(m)/r$. The *rank* of an $R$-module is the dimension of its localization.

4) **Ideals:** Given a ring $R$, a subset $I \subseteq R$ is said to be an *ideal* if $I$ is a subgroup of $R$ under addition, and is closed under multiplication by elements of $R$, i.e., for all $r \in R$ and $a \in I$, we have $ra \in I$. An ideal $I$ of $R$ is *proper* if it is not equal to $R$. A proper ideal $I$ is called a *prime* ideal if for any $a, b \in R$ such that $ab \in I$, at least one of $a$ or $b$ is in $I$. The ring $R$ is called a *principal ideal domain (PID)* if every ideal $I \in R$ is generated by a single element, that is, there exists $a \in R$ such that $I = \{ra | r \in R\} = (a)$.

A *fractional ideal* of a ring $R$ is a non-zero $R$-submodule $\mathfrak{a}$ of $K$ such that, for some $r \in R \setminus \{0\}$, the submodule $\mathfrak{a} := \{\mathfrak{r}\alpha | \alpha \in \mathfrak{a}\}$ is contained in $R$. The *dual* of a fractional ideal $\mathfrak{a}$ is the fractional ideal $\mathfrak{a}^{-1} := \{x \in K \mid x\mathfrak{a} \subseteq R\}$, and $\mathfrak{a}$ is *invertible* if $\mathfrak{a}^{-1}\mathfrak{a} = R$. An integral domain $R$ is a *Dedekind domain* if, and only if, every fractional ideal is invertible.

5) **On PIDs and Dedekind domains:** Any PID is a Dedekind domain, and any Dedekind domain $R$ is Noetherian, meaning that any ideal of $R$ is finitely generated. An $R$-module $M$ is Noetherian if every submodule of $M$ is finitely generated. Equivalently, a ring $R$ is Noetherian if every ascending chain of ideals in $R$ stabilizes, and an $R$-module $M$ is Noetherian if every ascending chain of submodules of $M$ stabilizes. In a Noetherian ring, all finitely generated modules are Noetherian.

In $R$ is a PID, then every finitely generated torsion-free $R$-module is free, and thus has a basis. If $R$ is a Dedekind domain with field of fractions $K$, then every finitely generated torsion-free $R$-module $M$ is a direct sum of rank 1 submodules, $M = \bigoplus_{i=1}^n E_i$, where each $E_i$ is of the form $\mathfrak{a}_i e_i$, for some fractional ideal $\mathfrak{a}_i$ of $K$ and $e_i \in M$, such that the system $(e_i)_{i=1}^n$ is free, see, e.g., [33, Cor. 10.2.3]. Such a set of rank 1 submodules $E_1, \dots, E_n$ is called a *pseudo-basis* for $M$.
## APPENDIX B
ALGEBRAIC NUMBER FIELDS

Denote by $\mathbb{Q}[x]$ the ring of univariate polynomials with rational coefficients. A non-zero polynomial in $\mathbb{Q}[x]$ is *monic* when its leading coefficient is equal to 1.

Recall that a complex number $\alpha \in \mathbb{C}$ is algebraic if it is the root of a non-zero polynomial in $\mathbb{Q}[x]$. The minimal polynomial of $\alpha$ (over $\mathbb{Q}$) is the monic polynomial of least degree in $\mathbb{Q}[x]$ that has $\alpha$ as a root. The degree of $\alpha$ is defined to be the degree of its minimal polynomial. The roots of the minimal polynomial of $\alpha$ are called the Galois conjugates of $\alpha$. The (absolute) norm of $\alpha$, denoted $N(\alpha)$, is the product of the Galois conjugates of $\alpha$.

A number field $K$ is a subfield of $\mathbb{C}$ having finite degree over $\mathbb{Q}$, meaning it can be viewed as a finite dimensional vector space over $\mathbb{Q}$. By the primitive element theorem, every number field has the form $\mathbb{Q}[\theta]$ for some algebraic number $\theta$, where

$$ \mathbb{Q}[\theta] := \left\{ \sum_{i=1}^{d} a_i \theta^i \mid a_i \in \mathbb{Q} \right\} $$

and $d$ is the degree of $\theta$. We say that $\theta$ is a primitive element for $K$, and define the degree of $K$ over $\mathbb{Q}$, denoted by $[K:\mathbb{Q}]$, to be $d$.

An algebraic integer $\alpha$ is *integral* (over $\mathbb{Z}$) if its minimal polynomial is in $\mathbb{Z}[x]$. The set of all algebraic integers $\mathbb{A} \subset \mathbb{C}$ is closed under addition, subtraction and multiplication and therefore is a commutative ring.

Given any number field $K$, its ring of integers $O_K := K \cap \mathbb{A}$ can be characterized as a $\mathbb{Z}$-module of rank $[K:\mathbb{Q}]$. Since $\mathbb{Z}$ is a PID, each $\mathbb{Z}$-submodule of $O_K$ is finitely generated; by this, each ideal $\alpha \subseteq O_K$ can be viewed as a finitely generated $\mathbb{Z}$-module. Indeed, by [45, Proposition 4.6.3], each ideal $\alpha \subseteq O_K$ is even a full-rank $\mathbb{Z}$-submodules of $O_K$. The finitely generated full-rank $\mathbb{Z}$-modules $b$ of $K$ are called *fractional ideals*. For clarity, we sometimes refer to ideals $\alpha \subseteq O_K$ as *integral ideals*. The set of fractional ideals of $K$ forms a commutative group [45, Theorem 4.6.14] under ideal multiplication with identity element $O_K$. Hence, the inverse of $\alpha$ is defined as $\alpha^{-1} := \{\alpha \in K | \alpha\alpha \subseteq O_K\}$. Moreover, for each fractional ideal $b$, there exists $r \in \mathbb{Z}$ such that $rb$ is integral.

The number rings $O_K$ are not in general unique factorization domains, where every (non-zero) element can be uniquely written as a product of irreducible elements; see Example 27 and Example 28 for instance. Ideals in $O_K$ when seen as $O_K$-modules are finitely generated, but might not have a basis. In this manner number rings differ from PIDs which, on the contrary, form a strict subset of unique factorization domains, and have all their ideals have a basis by definition.

In fact, by [43, Proposition 1.2.3], number rings are Dedekind domains. In particular, each fractional ideal is equal to a unique product of powers of prime ideals and can be generated by at most two elements.

**Example 27 (Cyclotomic fields).** An $n$-th root of unity $\alpha$ is a root of the polynomial $x^n - 1$. It is called *primitive* if it is not an $m$-th root of unity for any $m < n$.

Let $\zeta_n$ be a primitive $n$-th root of unity. The minimal polynomial $\Phi_n$ of $\zeta_n$ is known as the $n$-th cyclotomic polynomial. When $n$ is a (rational) prime, $\Phi_n$ takes the form $\Phi_n(x) = 1 + x + x^2 + \dots + x^{n-1}$.

The $n$-th cyclotomic field is $\mathbb{Q}(\zeta_n)$, whose ring of integers is $\mathbb{Z}[\zeta_n]$. An example is the Gaussian integers $\mathbb{Z}[i]$ which is the ring of integers of $\mathbb{Q}(i)$. The ideal $(1+2i)\mathbb{Z}[i]$ of $\mathbb{Z}[i]$ can be viewed as

* a $\mathbb{Z}[i]$-module generated by $(1+2i)$,

* a $\mathbb{Z}$-module generated by $1+2i$ and $-2+i$.

The ring $\mathbb{Z}[i]$ is a PID, but in general the cyclotomic rings $\mathbb{Z}[\zeta_n]$ are not PIDs. For example, $\mathbb{Z}[\zeta_{23}]$ does not satisfy unique factorization of elements, meaning it is not a UFD and therefore cannot be a PID. All number rings are Dedekind domains, where the unique factorization of elements is replaced by the unique factorization of ideals.

**Example 28 (Quadratic fields).** A number field $K$ is quadratic if there exists a square-free $\beta$ such that $K = \mathbb{Q}[\sqrt{\beta}]$. The ring of integers $O_K$ of $K$ is of the form $\mathbb{Z}[\theta]$, where

$$ \theta = \begin{cases} \sqrt{\beta} & \text{if } \beta \neq 1 \pmod{4}, \\ \frac{\sqrt{\beta}-1}{2} & \text{if } \beta \equiv 1 \pmod{4}. \end{cases} $$

For example, the ring of integers $O_K$ of $K = \mathbb{Q}(\sqrt{5})$ is $\mathbb{Z}[\frac{1+\sqrt{5}}{2}]$. The subring $\mathbb{Z}[\sqrt{5}]$ is called an order (as it has finite index in $O_K$). The order $\mathbb{Z}[\sqrt{5}]$ is not a PID, as shown by the factorizations

$$ 4 = 2 \cdot 2 = (3 + \sqrt{5})(3 - \sqrt{5}). $$

An order is a subring of $K$ whose additive group is free of rank $n$. The maximal order in $K$ is simply the ring $O_K$ of integers. While the number rings $O_K$ are Dedekind Domains, their proper orders are not necessarily. This is because Dedekind
domains require all nonzero ideals to factor uniquely into prime ideals, whereas proper orders may fail this property due to the presence of non-invertible ideals<fnref n="2" />.

## APPENDIX C
PROOFS FOR SECTION I

**Example 1.** Consider the number ring $R = \mathbb{Z}[i\sqrt{5}]$ and its field of fractions $K = \mathbb{Q}(i\sqrt{5})$. The 3-state $R$-weighted automaton over the alphabet $\{a, b\}$ given in Figure 1 is state-minimal but has an equivalent 2-state $K$-weighted automaton.

*Proof.* It is easy to see that these two automata are equivalent once we notice that they compute the same values for words of length 2, using that $(2 - i\sqrt{5})(i\sqrt{5} - 1) = 3(1 + i\sqrt{5})$. The automaton of Figure 1a is the one constructed in the proof of Proposition 26 for the ideal $\mathfrak{a} = (3, 2 - i\sqrt{5})$. It is indeed easy to check that

$$ \mathfrak{a}^{-1} = \frac{1}{3} (1 - i\sqrt{5}, 2 + i\sqrt{5}) $$

and there is an isomorphism

$$ \phi: (3, 2 - i\sqrt{5}) \oplus \frac{1}{3} (1 - i\sqrt{5}, 2 + i\sqrt{5}) \cong \mathbb{Z}[i\sqrt{5}]^2 $$

given by the formula

$$ \binom{a}{b} \mapsto a \left( \frac{i\sqrt{5}-1}{3} \right) + b \left( \frac{i\sqrt{5}-2}{3} \right) $$

(notice that $\phi(\begin{pmatrix} 3 \\ -1 \end{pmatrix}) = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ and $\phi(\begin{pmatrix} 2 - i\sqrt{5} \\ \frac{i\sqrt{5}-1}{3} \end{pmatrix}) = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$ so that the image of $\phi$ is indeed precisely $\mathbb{Z}[i\sqrt{5}]^2$).

We now show that $\mathfrak{a}$ is not principal and thus, by the proof of Proposition 26, that this $\mathbb{Z}[i\sqrt{5}]$-weighted automaton is indeed minimal. An integral basis for $\mathbb{Z}[i\sqrt{5}]$ is given by the two elements $1$ and $i\sqrt{5}$. In this integral basis, the two generators of $\mathfrak{a}$ are the vectors $\begin{pmatrix} 3 \\ 0 \end{pmatrix}$ and $\begin{pmatrix} 2 \\ -1 \end{pmatrix}$. By [45, §4.6.1], putting these two vectors in a matrix, the norm $\mathcal{N}(\mathfrak{a})$ of $\mathfrak{a}$ is the absolute value of the determinant of this matrix, namely 3. And by loc. cit., if $\mathfrak{a}$ were principal and generated by some $a + bi\sqrt{5}$, we would then have $3 = \mathcal{N}(\mathfrak{a}) = a^2 + 5b^2$ with $a, b \in \mathbb{Z}$: this is clearly impossible. $\square$

## APPENDIX D
PROOFS FOR SECTION III

**Proposition 10.** Let $R$ be a Dedekind domain, and let $L$ be an $R$-weighted language of rank $n$ computed by a finite $R$-WA. There exists an $R$-WA computing $L$ with at most $n + 1$ states.

*Proof.* We have already argued that $\text{Min } L$ has a pseudo-basis. In fact, by [43, Theorem 1.2.19] we may even choose this pseudo-basis so that all except one of the fractional ideals are $R$: we write $\text{Min } L \cong R^{n-1} \oplus \mathfrak{a}$ for some fractional ideal $\mathfrak{a}$. Because this is an isomorphism, the $R$-modular automaton structure on $\text{Min } L$ can be conjugated to equip $R^{n-1} \oplus \mathfrak{a}$ with an $R$-modular automaton structure as well. Write $\mathcal{A}$ for this $R$-modular automaton.

By [43, Lemma 1.2.20], there is an isomorphism $\mathfrak{a} \oplus \mathfrak{a}^{-1} \cong \mathbb{R}^2$. Extend this isomorphism to get an injection $m: R^{n-1} \oplus \mathfrak{a} \to R^{n+1}$ and a surjection $e: R^{n+1} \to R^{n-1} \oplus \mathfrak{a}$ such that $e \circ m$ is the identity. We can now conjugate $\mathcal{A}$ into an $R$-modular automaton $\mathcal{A}'$ such that $\mathcal{A}'(\mathfrak{st}) = R^{n+1}$ by setting $\mathcal{A}'(\mathfrak{d}) = m \circ \mathcal{A}(\mathfrak{d})$, $\mathcal{A}'(\sigma) = m \circ \mathcal{A}(\sigma) \circ e$ for all $\sigma \in \Sigma$ and $\mathcal{A}'(\langle\rangle) = \mathcal{A}(\langle\rangle) \circ e$.

Because $\mathcal{A}'(\mathfrak{st})$ is a free module of rank $n + 1$ and because $e$ is a morphism of automata $\mathcal{A}' \to \mathcal{A}$, $\mathcal{A}'$ is an $R$-weighted automaton with $n + 1$ states that computes $L$. $\square$

## APPENDIX E
CATEGORY THEORY PRELIMINARIES

In this section, we recall the notions from category theory used in this paper. More details can be found in any standard text on category theory, such as [49] or [38]. As a running example we recall in particular the functorial framework for automata minimization of [30].

<footnote n="2">²Due to this fact, our learning algorithm for WAs over $\mathcal{O}_K$, in the current form, cannot be used for learning WAs over orders of $\mathcal{O}_K$.</footnote>
### A. Categories, functors, natural transformations, and examples

A category $\mathbf{C}$ is a pair of classes (ob $\mathbf{C}$, mor $\mathbf{C}$), called the objects and morphisms of $\mathbf{C}$, respectively, equipped with the following structure:

* for any morphism $f$ of $\mathbf{C}$, a domain object $\operatorname{dom}(f)$ and a codomain object $\operatorname{cod}(f)$; the notation $f: A \to B$ means that $\operatorname{dom}(f) = A$ and $\operatorname{cod}(f) = B$;

* for any object $C$ of $\mathbf{C}$, a distinguished morphism $1_C: C \to C$, the identity on $C$;

* for any morphisms $f: A \to B$ and $g: B \to C$ of $\mathbf{C}$, a morphism $g \circ f: A \to C$, the composition of $f$ and $g$;

satisfying the following axioms:

* composition is associative: for any $f: A \to B$, $g: B \to C$, $h: C \to D$, we have $h \circ (g \circ f) = (h \circ g) \circ f$;

* the identities are neutral elements: for any $f: A \to B$, $f \circ 1_A = f = 1_B \circ f$.

For objects $A$ and $B$ in a category $\mathbf{C}$, we write $\mathbf{C}(A, B)$ for the class of morphisms from $A$ to $B$. A category is called locally small if $\mathbf{C}(A, B)$ is a set for any objects $A, B$, and small if the class mor $\mathbf{C}$ is a set.

A subcategory $\mathbf{D}$ of a category $\mathbf{C}$ is a pair (ob $\mathbf{D}$, mor $\mathbf{D}$), where ob $\mathbf{D}$ is a subclass of ob $\mathbf{C}$ and mor $\mathbf{D}$ is a subclass of mor $\mathbf{C}$, such that for any composable pair of morphisms $f, g \in \operatorname{mor} \mathbf{D}$, the composition $g \circ f$ is also in mor $\mathbf{D}$. The subcategory $\mathbf{D}$ is called full if, for any objects $A, B \in \operatorname{ob} \mathbf{D}$, we have $\mathbf{D}(A, B) = \mathbf{C}(A, B)$.

A morphism $f: A \to B$ is a *monomorphism*, or just *mono*, if it is left-cancellable, i.e., for any $g_1, g_2: A' \to A$, if $f \circ g_1 = f \circ g_2$ then $g_1 = g_2$. Analogously, a morphism is an *epimorphism*, or just *epi*, if it is right-cancellable. A morphism $f: A \to B$ is an *isomorphism*, or just *iso*, if it admits a two-sided inverse, i.e., there exists $g: B \to A$ such that $g \circ f = 1_A$ and $f \circ g = 1_B$; in this case, the objects $A$ and $B$ are *isomorphic*, and we write $A \cong B$. In any category, isomorphisms are both mono and epi, but there may in general be morphisms that are both mono and epi without being iso.

**Example 29.** The following are examples of locally small categories that are relevant to this paper:

1) The category **Set** of sets, i.e., ob **Set** is the class of sets and, for any sets $A, B$, Set($A, B$) is the set of morphisms from $A$ to $B$.

2) For any ring $R$, the category Mod$_R$ of $R$-modules, i.e., ob Mod$_R$ is the class of $R$-modules and, for any $R$-modules $M$ and $N$, Mod$_R(M, N)$ is the set of $R$-linear maps from $M$ to $N$.

3) For any field $K$, the category Vec$_K$ of $K$-vector spaces, which is just the category Mod$_R$ in the special case $R = K$.

4) For any ring $R$, the category FreeMod$_R$ of free $R$-modules, i.e., the full subcategory of Mod$_R$ whose objects are the free $R$-modules.

5) For any ring $R$, the category Modtf$_R$ of torsion-free $R$-modules, i.e., the full subcategory of Mod$_R$ whose objects are the torsion-free $R$-modules.

6) A *directed multigraph* is a structure $G = (V, E)$, where $V$ is a set of nodes and $E$ is a multiset of pairs of nodes. For any directed multigraph $G$, there is a *free category* Free($G$) on $G$, which can be realized concretely as follows: the objects of Free($G$) are the nodes of $G$, and for any nodes $v, w$ of $G$, the set of morphisms Free($G$)($v, w$) consists of the finite paths from $v$ to $w$ in $G$. For any node $v$ of $G$, the identity $1_v$ on $v$ is the empty path. The composition of paths $e: v \to w$ and $f: w \to x$ is defined by concatenation.

7) In particular, for fixed finite alphabet $\Sigma$, we denote by **I** the category free over the multigraph

<figure><img src="image_3.png" /></figure>

Concretely, the morphisms of **I** can be described as follows: in addition to the three identity morphisms $1_{\text{in}}$, $1_{\text{st}}$ and $1_{\text{out}}$, for any word $w \in \Sigma^+$, we have four morphisms: $w: \text{st} \to \text{st}$, $\triangleright w: \text{in} \to \text{st}$, $w\triangleleft: \text{st} \to \text{out}$, and $\triangleright w\triangleleft: \text{in} \to \text{out}$.
We denote by **O** the full subcategory of **I** on the objects in and out: it consists in these two objects, and, identities excluded, a morphism $\triangleright w\triangleleft: \text{in} \to \text{out}$ for every $w \in \Sigma^*$.

Let $\mathbf{C}$ and $\mathbf{D}$ be categories. A functor $\mathcal{F}: \mathbf{C} \to \mathbf{D}$ is a pair of mappings, one from ob $\mathbf{C}$ to ob $\mathbf{D}$ and one from mor $\mathbf{C}$ to mor $\mathbf{D}$, such that the following properties hold:

* for any morphism $f: A \to B$ in $\mathbf{C}$, we have $\mathcal{F}f: \mathcal{F}A \to \mathcal{F}B$, i.e., $\operatorname{dom}(\mathcal{F}f) = FA$ and $\operatorname{cod}(\mathcal{F}f) = FB$;

* for any object $A$ of $\mathbf{C}$, $\mathcal{F}(1_A) = 1_{\mathcal{F}A}$;

* for any morphisms $f: A \to B$, $g: B \to C$ in $\mathbf{C}$, we have $\mathcal{F}(g \circ f) = \mathcal{F}g \circ \mathcal{F}f$.

If $\mathcal{F}: \mathbf{C} \to \mathbf{D}$ and $\mathcal{G}: \mathbf{D} \to \mathcal{E}$ are functors, then their composition is the functor $\mathcal{G} \circ \mathcal{F}: \mathbf{C} \to \mathcal{E}$ which sends an object $A$ of $\mathbf{C}$ to the object $\mathcal{G}\mathcal{F}A$ and a morphism $f: A \to B$ of $\mathbf{C}$ to the morphism $\mathcal{G}\mathcal{F}f$. The identity functor on a category $\mathbf{C}$ is the functor $\mathbf{C} \to \mathbf{C}$ which is the identity on both objects and morphisms.
**Example 30.** 1) There is a functor $\mathcal{U}: \text{Mod}_R \to \text{Set}$ which sends an $R$-module $M$ to its underlying set, and an $R$-linear map $M \to N$ to its underlying function. This is called the *forgetful functor* from $\text{Mod}_R$ to $\text{Set}$. There are many other categories whose objects are 'sets with additional structure' and whose morphisms are 'functions preserving the additional structure', and they always admit an analogous forgetful functor to $\text{Set}$.

2) Let $R$ be a ring with field of fractions $K$. The construction which associates to a torsion-free $R$-module $M$ the localization $R^{-1}M$ and to an $R$-linear map $\phi: M \to N$ the vector space map $R^{-1}\phi: R^{-1}M \to R^{-1}N$ (see Section II) is the localization functor $R^{-1}-: \text{Mod}_R^{\text{tf}} \to \text{Vec}_K$.

In the other direction, we have a functor $-R: \text{Vec}_K \to \text{Mod}_R^{\text{tf}}$, called *restriction of scalars*, which views a $K$-vector space as only being an $R$-module and a $K$-linear transformation as only being $R$-linear.

3) Let $\mathbf{C}$ be a category and $I, O$ two objects of $\mathbf{C}$. Recall that a $(\mathbf{C}, I, O)$-automaton is, by definition, a functor $\mathcal{A}: \mathbf{I} \to \mathbf{C}$ such that $\mathcal{A}(\text{in}) = \mathbf{I}$ and $\mathcal{A}(\text{out}) = \mathbf{O}$.

4) A subcategory $\mathbf{C}$ of a category $\mathbf{D}$ comes with a functor that sends every object of $\mathbf{C}$ to the corresponding object of $\mathbf{D}$, and every morphism of $\mathbf{C}$ to the corresponding morphism of $\mathbf{D}$.

Write $\iota: \mathbf{O} \to \mathbf{I}$ for this functor in the case where $\mathbf{C} = \mathbf{O}$ and $\mathbf{D} = \mathbf{I}$. For any $(\mathbf{C}, I, O)$-automaton given as a functor $\mathcal{A}: \mathbf{I} \to \mathbf{C}$, the composite functor $\mathcal{L} = \mathcal{A} \circ \iota: \mathbf{O} \to \mathbf{C}$ is the $(\mathbf{C}, I, O)$-language recognized or computed by $\mathcal{A}$.

Let $\mathbf{C}$ and $\mathbf{D}$ be categories and $\mathcal{F}, \mathcal{G}: \mathbf{C} \to \mathbf{D}$ functors. A natural transformation $\alpha$ from $\mathcal{F}$ to $\mathcal{G}$, written $\alpha: \mathcal{F} \Rightarrow \mathcal{G}$, is an ob $\mathbf{C}$-indexed family of $\mathbf{D}$-morphisms, $(\alpha_{\mathcal{C}}: \mathcal{F}\mathcal{C} \to \mathcal{G}\mathcal{C})_{\mathcal{C} \in \text{ob } \mathbf{C}}$, such that, for any morphism $f: A \to B$ in $\mathbf{C}$, we have $(\mathcal{G}f) \circ \alpha_A = \alpha_B \circ (\mathcal{F}f)$, i.e., the following diagram commutes:

<figure><img src="image_4.png" /></figure>

For any categories $\mathbf{C}$ and $\mathbf{D}$, the functor category $\text{Fun}(\mathbf{C}, \mathbf{D})$ has as its objects the functors from $\mathbf{C}$ to $\mathbf{D}$, and, given two such functors $\mathcal{F}$ and $\mathcal{G}$, the class of morphisms $\text{Fun}(\mathbf{C}, \mathbf{D})(\mathcal{F}, \mathcal{G})$ consists of the natural transformations from $\mathcal{F}$ to $\mathcal{G}$. For morphisms $\alpha: \mathcal{F} \to \mathcal{G}$ and $\beta: \mathcal{G} \to \mathcal{H}$ in $\text{Fun}(\mathbf{C}, \mathbf{D})$, the composition $\beta \circ \alpha$ is defined to be the family $(\beta_C \circ \alpha_C)_{C \in \text{ob } \mathbf{C}}$. For any functor $\mathcal{F}$, the identity $1_{\mathcal{F}}: \mathcal{F} \Rightarrow \mathcal{F}$ is the family $(1_{\mathcal{F}\mathcal{C}})_{\mathcal{C} \in \text{ob } \mathbf{C}}$.

**Remark 31.** For $\mathbf{C}$ a category and $I, O$ two objects of $\mathbf{C}$, the category of automata, $\text{Auto}(\mathbf{C}, I, O)$, is a subcategory of $\text{Fun}(\mathbf{I}, \mathbf{C})$, whose objects are the functors that send in to $I$ and out to $O$, and whose morphisms are the natural transformations $\alpha$ for which $\alpha_{\text{in}} = 1_I$ and $\alpha_{\text{out}} = 1_O$. Concretely, such a natural transformation is uniquely given by its component $\alpha_{\text{st}}$, and the naturality diagrams are then the ones given immediately after the definition of automaton morphism in the main text. Given a $(\mathbf{C}, I, O)$-language $\mathcal{L}$, we also write $\text{Auto}(\mathcal{L})$ for the full subcategory of $\text{Auto}(\mathbf{C}, I, O)$ whose objects are those $(\mathbf{C}, I, O)$-automata computing $\mathcal{L}$.

## B. Products, coproducts, powers, copowers, final and initial objects

1) **Products, powers, final objects:** Let $\mathbf{C}$ be a category and let $(A_i)_{i \in I}$ be a family of objects indexed by a set $I$. A product of the objects $(A_i)_{i \in I}$ in $\mathbf{C}$ is an object $P$, together with a family of morphisms $(\pi_i: P \to A_i)_{i \in I}$, such that, for any object $B$ and $I$-indexed family of morphisms $(f_i: B \to A_i)_{i \in I}$, there exists a unique morphism $f: B \to P$ such that $\pi_i \circ f = f_i$ for every $i \in I$. In this case, we denote the object $P$ by $\coprod_{i \in I} A_i$, and the morphism $f$ by $\langle f_i \rangle_{i \in I}$. In the special case where there is an object $A$ such that $A_i = A$ for all $i \in I$, we denote such an object $P$ by $\prod_I A$, and call it the $I$-fold power of the object $A$.

To expand upon this definition a bit more, consider the case where $I = \{1, 2\}$. The product of two objects $A_1$ and $A_2$ is then denoted $A_1 \times A_2$, and it is an object of $\mathbf{C}$ equipped with two morphisms $p_1: A_1 \times A_2 \to A_1$ and $p_2: A_1 \times A_2 \to A_2$, such that, for any pair of morphisms $f_1: B \to A_1, f_2: B \to A_2$, there exists a unique $f: B \to A_1 \times A_2$ such that $p_1 \circ f = f_1$ and $p_2 \circ f = f_2$, as in the following diagram:

<figure><img src="image_5.png" /></figure>

For example, in the category $\text{Set}$, note that this property indeed holds for the Cartesian product of sets, and indeed could be used to define it uniquely, up to a bijection.
Now also consider the special case where $I = \emptyset$. In this case, a product of the empty family in $C$ is just an object $P$ such that, for any object $B$, there is a unique morphism from $B$ to $P$. Such an object $P$ is called a final object of $C$, and we denote the unique morphism from $B$ to $P$ by $i_B$. In the category Set, any singleton set is a final object.

In a general category, one may prove that, if $P$ and $P'$ are both products of the same family of objects, then $P \cong P'$. This is an instance of the general fact that objects defined by universal properties are unique up to isomorphism. We can thus harmlessly (for the purposes of this paper) speak about ‘the’ product of the family $(A_i)_{i \in I}$. However, note that, in an arbitrary category, the product of a family of objects may fail to exist; for instance, the category $\mathbf{I}$ above does not have a final object.

**Remark 32.** Most category-theoretic literature writes $A^I$ for the power, instead of $\coprod_I A$. However, this clashes with common notation for free modules: although it is true that, in the category $\mathbf{Mod}_R$, when $Q$ is a finite set, the free $R$-module $R^Q$ is $\coprod_Q R$ in the category $\mathbf{Mod}_R$, when $Q$ is infinite, this is no longer true in general. The free $R$-module on $Q$ only contains the finitely supported functions from $Q$ to $R$, and is therefore still a submodule of the categorical power $\coprod_Q R$, but the latter fails to be a free module in general, see, e.g., [36].

Let $C$ be a category with fixed objects $I$ and $O$ such that $C$ has countable powers of $O$, and let $\mathcal{L}: O \to C$ be a $(C, I, O)$-language. The final object of $\mathbf{Auto}(\mathcal{L})$ exists and is given by the following formulæ:

$$
\begin{align*}
\mathcal{A}_{\text{final}}(\mathcal{L})(\text{st}) &= \coprod_{\Sigma^*} O \\
\mathcal{A}_{\text{final}}(\mathcal{L})(\triangleright) &= \langle \mathcal{L}(\triangleright w \triangleleft) \rangle_{w \in \Sigma^*} \\
\mathcal{A}_{\text{final}}(\mathcal{L})(\sigma) &= \langle \pi_{\sigma w} \rangle_{w \in \Sigma^*} \\
\mathcal{A}_{\text{final}}(\mathcal{L})(\triangleleft) &= \pi_{\varepsilon}
\end{align*}
$$

For any other $(C, I, O)$-automaton $\mathcal{A}$ computing $\mathcal{L}$, the underlying $C$-arrow $\mathcal{A}(\text{st}) \to \mathcal{A}_{\text{final}}(\text{st}) = \coprod_{\Sigma^*} O$ of the unique morphism $i_{\mathcal{A}}: \mathcal{A} \to \mathcal{A}_{\text{final}}(\mathcal{L})$ is given by

$$(i_{\mathcal{A}})_{\text{st}} = \langle \mathcal{A}(w\triangleleft) \rangle_{w \in \Sigma^*}$$

**Example 33.** Given a ring $R$, the category $\mathbf{Mod}_R$ has all products. The product of a family of modules $(M_i)_{i \in I}$ is the module whose elements are families $(m_i)_{i \in I}$ with $m_i \in M_i$, equipped with component-wise addition and scalar multiplication. Note that this differs from the usual direct sum, whose elements are families $(m_i)_{i \in I}$ with $m_i \in M_i$ but such that only a finite numbers of the $m_i$'s are non-zero.

The final $(\mathbf{Mod}_R, R, R)$-automaton computing a $(\mathbf{Mod}_R, R, R)$-language thus exists. $\mathcal{A}_{\text{final}}(\mathcal{L})(\text{st})$ is the module $R\langle\langle\Sigma^*\rangle\rangle$ of power-series, whose elements are functions $\Sigma^* \to R$. $\mathcal{A}_{\text{final}}(\mathcal{L})(\triangleright)$ is the linear transformation $R \to R\langle\langle\Sigma^*\rangle\rangle$ that sends $1 \in R$ to the series $w \mapsto \mathcal{L}(\triangleright w \triangleleft)$. $\mathcal{A}_{\text{final}}(\mathcal{L})(\sigma)$ sends a series $s \in R\langle\langle\Sigma^*\rangle\rangle$ to its derivative $\sigma^{-1}s: w \mapsto s(\sigma w)$. $\mathcal{A}_{\text{final}}(\mathcal{L})(\triangleleft)$ sends a series $s \in R\langle\langle\Sigma^*\rangle\rangle$ to the scalar $s(\varepsilon)$.

Given any other $(\mathbf{Mod}_R, R, R)$-automaton $\mathcal{A}$ computing $\mathcal{L}$, the unique morphism of $(\mathbf{Mod}_R, R, R)$-automata $\mathcal{A} \to \mathcal{A}_{\text{final}}(\mathcal{L})$ is given by the linear transformation $\mathcal{A}(\text{st}) \to R\langle\langle\Sigma^*\rangle\rangle$ that sends some $m \in \mathcal{A}(\text{st})$ to the series $w \mapsto \mathcal{A}(w\triangleleft)(m)$. In particular if $\mathcal{A}(\text{st})$ is free and has $Q$ for a basis, this linear transformation can be represented by the infinite $Q \times \Sigma^*$ matrix whose $(q, w)$ entry is $\mathcal{A}(w\triangleleft)(q)$.

When $R$ is an integral domain, $R\langle\langle\Sigma^*\rangle\rangle$ is a torsion-free module. More generally, a product of torsion-free modules is again torsion-free, so that $\mathbf{Mod}_R^{\text{tf}}$ has all products as well, and these products are computed just as in $\mathbf{Mod}_R$. In particular, the final $(\mathbf{Mod}_R, R, R)$- and $(\mathbf{Mod}_R^{\text{tf}}, R, R)$-automata computing a language coincide.

2) Coproducts, copowers, initial objects: Dual to products, powers, and final objects, we have coproducts, copowers, and initial objects, which we define now. Let $C$ be a category and let $(A_i)_{i \in I}$ be a family of objects indexed by a set $I$. A coproduct of the objects $(A_i)_{i \in I}$ in $C$ is an object $C$, together with a family of morphisms $(j_i: A_i \to C)_{i \in I}$, such that, for any object $B$ and $I$-indexed family of morphisms $(f_i: A_i \to B)_{i \in I}$, there exists a unique morphism $f: C \to B$ such that $f \circ j_i = f_i$ for every $i \in I$. In this case, we denote the object $C$ by $\coprod_{i \in I} A_i$, and the morphism $f$ by $[f_i]_{i \in I}$. In the special case where there is an object $A$ such that $A_i = A$ for all $i \in I$, we denote such an object $C$ by $\coprod_I A$, and call it the I-fold copower of the object $A$.

In Set, the coproduct of a family of sets is its disjoint union. In $\mathbf{Mod}_R$, the coproduct of a family of modules is their direct sum. For instance, for any set $Q$, the free $R$-module $R^Q$ is the $Q$-fold copower of the module $R$ in the category $\mathbf{Mod}_R$, and can thus also be denoted $\coprod_Q R$. A coproduct of the empty family is called an initial object, i.e., an object $C$ such that, for every object $B$, there is a unique morphism $!_B: C \to B$.
Let $\mathbf{C}$ be a category with fixed objects $I$ and $O$ such that $\mathbf{C}$ has countable copowers of $I$, and let $\mathcal{L}: \mathbf{O} \to \mathbf{C}$ be a $(\mathbf{C}, I, O)$-language. The initial object of $\mathbf{Auto}(\mathcal{L})$ exists and is given by the following formulæ:

$$ \mathcal{A}_{init}(\mathcal{L})(\mathbf{st}) = \coprod_{\Sigma^*} I $$

$$ \mathcal{A}_{init}(\mathcal{L})(\triangleleft) = [\mathcal{L}(\triangleright w \triangleleft)]_{w \in \Sigma^*} $$

$$ \mathcal{A}_{init}(\mathcal{L})(\sigma) = [j_w \sigma]_{w \in \Sigma^*} $$

$$ \mathcal{A}_{init}(\mathcal{L})(\triangleright) = j_{\varepsilon} $$

For any other $(\mathbf{C}, I, O)$-automaton $\mathcal{A}$ computing $\mathcal{L}$, the underlying $\mathbf{C}$-arrow $\coprod_{\Sigma^*} I = \mathcal{A}_{init}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ of the unique morphism $!_{\mathcal{A}}: \mathcal{A}_{init}(\mathcal{L}) \to \mathcal{A}$ is given by

$$ (!_{\mathcal{A}})_{\mathbf{st}} = [\mathcal{A}(\triangleright w)]_{w \in \Sigma^*} $$

**Example 34.** Given a ring $R$, the category $\mathbf{Mod}_R$ has all coproducts. The coproduct of a family of modules $(M_i)_{i \in I}$ is the usual direct sum of these modules, i.e. the module whose elements are families $(m_i)_{i \in I}$ with $m_i \in M_i$ such that only a finite number of the $m_i$'s, equipped with component-wise addition and scalar multiplication.

The initial $(\mathbf{Mod}_R, R, R)$-automaton computing a $(\mathbf{Mod}_R, R, R)$-language thus exists. $\mathcal{A}_{init}(\mathcal{L})(\mathbf{st})$ is the free module $R^{\Sigma^*}$, whose elements are finitely-supported functions $\Sigma^* \to R$. $\mathcal{A}_{init}(\mathcal{L})(\triangleright)$ is the linear transformation $R \to R^{\Sigma^*}$ that sends $1 \in R$ to the function that sends $\varepsilon$ onto 1 and every other word onto 0. $\mathcal{A}_{init}(\mathcal{L})(\sigma)$ sends a function $f \in R^{\Sigma^*}$ to the function that sends $w \in \Sigma^*$ to $f(w\sigma)$. $\mathcal{A}_{init}(\mathcal{L})(\triangleleft)$ sends a function $f$ to the (finite) sum $\sum_{w \in \Sigma^*} f(w)\mathcal{L}(\triangleright w \triangleleft)$.

Given any other $(\mathbf{Mod}_R, R, R)$-automaton $\mathcal{A}$ computing $\mathcal{L}$, the unique morphism of $(\mathbf{Mod}_R, R, R)$-automata $\mathcal{A}_{init}(\mathcal{L}) \to \mathcal{A}$ is given by the linear transformation $R^{\Sigma^*} \to \mathcal{A}(\mathbf{st})$ that sends a finitely-supported function $f: \Sigma^* \to R$ to the (finite) sum $\sum_{w \in \Sigma^*} f(w)\mathcal{A}(\triangleright w)$. If $\mathcal{A}(\mathbf{st})$ is free and has $Q$ for a basis, this linear transformation can be represented by the infinite $\Sigma^* \times Q$ matrix whose $w$-indexed row is $\mathcal{A}(\triangleright w)$ (written as a row vector in the basis $Q$).

A coproduct of torsion-free modules is again torsion-free, so that $\mathbf{Mod}_R^{tf}$ has all coproducts as well, and these coproducts are computed just as in $\mathbf{Mod}_R$. In particular, the initial $(\mathbf{Mod}_R, R, R)$- and $(\mathbf{Mod}_R^{tf}, R, R)$-automata computing a language coincide.

### C. Factorization systems

A factorization system on a category $\mathbf{C}$ is a pair $(\mathcal{E}, \mathcal{M})$ of subclasses of mor $\mathbf{C}$, each closed under composition and containing all the isomorphisms, such that, for any morphism $f: X \to Y$, there exists a factorization $f = m \circ e$ with $e: X \to Z$ in $\mathcal{E}$ and $m: Z \to Y$ in $\mathcal{M}$ which is unique up to isomorphism: if $f = m' \circ e'$ with $e': X \to Z'$ and $m': Z' \to Y$ is another such factorization, there is a unique isomorphism $\chi: Z \cong Z'$ such that $\chi \circ e = e'$ and $m' \circ \chi = m$.

Notice in particular how $\mathcal{E}$-morphisms are depicted with $\dasharrow$ and $\mathcal{M}$-morphisms are depicted with $\dashrightarrow$. It is natural to call the $\mathcal{M}$-morphism $m: Z \to Y$ in the factorization of a morphism $f: X \to Y$ its $(\mathcal{E}, \mathcal{M})$-image, and we do so here.

**Example 35.** The following are examples of factorization systems relevant to this paper:

* the category Set is equipped with the factorization system (Surj, Inj) of surjections and injections: every function factors through its image, the latter being unique up to bijections;

* given any ring $R$, the category $\mathbf{Mod}_R$ is equipped with the factorization system (Surj, Inj) of surjective linear transformations and injective linear transformations: every linear transformation factors through its image, the latter being unique up to bijections;

* when $R$ is an integral domain, the factorization system (Surj, Inj) on $\mathbf{Mod}_R$ restricts to a factorization system on $\mathbf{Mod}_R^{tf}$: this is because the image of a linear transformation between torsion-free modules, as a submodule of a torsion-free module, is again torsion-free;

* unless $R$ is a field, in which case every $R$-module is free, the factorization system (Surj, Inj) on $\mathbf{Mod}_R$ does not restrict to a factorization system on $\mathbf{FreeMod}_R$: this is because the image of a linear transformation between free modules need not be a free module.

We recall a few useful facts about factorization systems, also see, e.g. [38, Ch. 14]. Suppose $\mathbf{C}$ is equipped with a factorization system $(\mathcal{E}, \mathcal{M})$. Then the following diagonal fill-in property holds: for any morphisms $e: A \to B$ in $\mathcal{E}$, $m: C \to D$ in $\mathcal{M}$, and arbitrary morphisms $f: A \to C$, $g: B \to D$ in $\mathbf{C}$, if $m \circ f = g \circ e$, then there exists a unique morphism $d: B \to C$ such that both $d \circ e = f$ and $m \circ d = g$. This morphism is then called a diagonal fill-in for the commutative square $m \circ f = g \circ e$; the following diagram shows why:

<figure><img src="image_6.png" /></figure>
The intersection $\mathcal{E} \cap \mathcal{M}$ is exactly the class of all isomorphisms. If a composite $g \circ f$ is in $\mathcal{E}$ and $f$ is in $\mathcal{E}$ as well, then $g$ is also in $\mathcal{E}$. Dually, if a composite $g \circ f$ is in $\mathcal{M}$ and $g$ is in $\mathcal{M}$ as well, then $f$ is also in $\mathcal{M}$. Together with the diagonal fill-in property, one may deduce from this the following fact: there is a (necessarily unique) $\mathcal{M}$-morphism between the $(\mathcal{E}, \mathcal{M})$-image of a composite $g \circ f$ and that of $g$ that makes the following diagram commute:

<figure><img src="image_7.png" /></figure>

This generalizes the basic fact that the image of a composite function $g \circ f$ is a subset of the image of the function $g$.

A final, more involved example of factorization system is the following. Let $\mathbf{C}$ and $\mathbf{D}$ be two categories, and let $(\mathcal{E}, \mathcal{M})$ be a factorization system on $\mathbf{D}$. In $\mathbf{Fun}(\mathbf{C}, \mathbf{D})$, let $\mathcal{E}_{\mathbf{Fun}}$ denote the class of those natural transformations $\alpha$ whose every component $\alpha_X$, with $X$ an object of $\mathbf{C}$, is in $\mathcal{E}$. Dually, let $\mathcal{M}_{\mathbf{Fun}}$ denote the class of those natural transformations $\alpha$ whose every component $\alpha_X$, with $X$ an object of $\mathbf{C}$, is in $\mathcal{M}$.

Then $(\mathcal{E}_{\mathbf{Fun}}, \mathcal{M}_{\mathbf{Fun}})$, which we also just write $(\mathcal{E}, \mathcal{M})$, forms a factorization system on $\mathbf{Fun}(\mathbf{C}, \mathbf{D})$, for which natural transformations are factored component-wise. More precisely, given $\alpha: \mathcal{F} \Rightarrow \mathcal{G}$ and some $\mathbf{C}$-morphism $f: X \to Y$, denote by $\mathcal{F}X \xrightarrow{\beta_X} \mathcal{H}X \xrightarrow{\gamma_X} \mathcal{G}X$ the $(\mathcal{E}, \mathcal{M})$ factorization of $\alpha_X$, and similarly along $Y$. Denote finally by $\mathcal{H}f$ the diagonal fill-in:

<figure><img src="image_8.png" /></figure>

By uniqueness of the diagonal fill-in, this definition makes $\mathcal{H}$ into a functor and $\beta$ and $\gamma$ into natural transformations. The $(\mathcal{E}_{\mathbf{Fun}}, \mathcal{M}_{\mathbf{Fun}})$-factorization of $\alpha$ is then given by $\alpha = \gamma \circ \beta$.

Taking in particular $\mathbf{C}$ to be the freely generated category $I$ defined in Example 29, this factorization system on $\mathbf{Fun}(\mathbf{I}, \mathbf{D})$ restricts to a factorization system on $\mathbf{Auto}(\mathbf{D}, I, O)$ where $\mathbf{I}$ and $\mathbf{O}$ are any two objects of $\mathbf{D}$. In concrete words: morphisms of $(\mathbf{D}, I, O)$-automata can be factored by factoring their underlying $\mathbf{D}$-morphisms, and the $(\mathcal{E}, \mathcal{M})$-image of a morphism of $(\mathbf{D}, I, O)$-automata is itself canonically equipped with the structure of a $(\mathbf{D}, I, O)$-automaton. In a diagram, the image $\mathrm{im}\mathcal{A}$ of a morphism of automata $\mathcal{A} \to \mathcal{A}'$ is given as

<figure><img src="image_9.png" /></figure>

If $\mathcal{A}$ is a $(\mathbf{D}, I, O)$-automaton computing $\mathcal{L}$, we denote in particular by $\mathrm{Reach} \mathcal{A}$ the image of the unique morphism $!_{\mathcal{A}}: \mathcal{A}_{\mathrm{init}}(\mathcal{L}) \to \mathcal{A}$, by $\mathrm{Obs} \mathcal{A}$ the image of the unique morphism $i_{\mathcal{A}}: \mathcal{A} \to \mathcal{A}_{\mathrm{final}}(\mathcal{L})$ and by $\mathrm{Min} \mathcal{L}$ the image of the unique morphism $i_{\mathcal{A}_{\mathrm{init}}(\mathcal{L})} = !_{\mathcal{A}_{\mathrm{final}}(\mathcal{L})}: \mathcal{A}_{\mathrm{init}}(\mathcal{L}) \to \mathcal{A}_{\mathrm{final}}(\mathcal{L})$, and the uniqueness of a factorization entails that $\mathrm{Reach}(\mathrm{Obs} \mathcal{A}) \cong \mathrm{Obs}(\mathrm{Reach} \mathcal{A}) \cong \mathrm{Min} \mathcal{L}$.

**Example 36.** We describe $\mathrm{Reach}$, $\mathrm{Obs}$ and $\mathrm{Min}$ for $(\mathrm{Mod}_R, R, R)$-automata. Because $\mathrm{Mod}_R^{\mathrm{tf}}$ shares the coproducts, products and the factorization system of $\mathrm{Mod}_R$, this description also applies to $(\mathrm{Mod}_R^{\mathrm{tf}}, R, R)$-automata. Let $\mathcal{A}$ be a $(\mathrm{Mod}_R, R, R)$-automaton recognizing a $(\mathrm{Mod}_R, R, R)$-language $\mathcal{L}$.

($\mathrm{Reach} \mathcal{A}$)(st) is the submodule of reachable configurations of $\mathcal{A}(st)$, also called its forward module: its elements are those elements $m \in \mathcal{A}(st)$ for which there is an $R$-linear combination $\sum_{i=1}^n r_i w_i$ such that $m = \sum_{i=1}^n r_i \mathcal{A}(\triangleright w_i)(1)$. The injective morphism of automata $\mathrm{Reach} \mathcal{A} \to \mathcal{A}$ is the embedding of this submodule into the bigger module $\mathcal{A}(st)$.

($\mathrm{Obs} \mathcal{A}$)(st) is the quotient of $\mathcal{A}(st)$ by the equivalence relation $m \sim m' \iff \forall w \in \Sigma^*, \mathcal{A}(w \triangleleft)(m) = \mathcal{A}(w \triangleleft)(m')$, also called its backward module – it is a module because this equivalence relation is a congruence, i.e. is compatible with the module structure of $\mathcal{A}(st)$. The surjective morphism of automata $\mathcal{A} \to \mathrm{Obs} \mathcal{A}$ is the linear transformation that sends some $m \in \mathcal{A}(st)$ to its equivalence class.
Finally, notice that the unique morphism $A_{init}(\mathcal{L}) = R^{\Sigma^*} \to R\langle\langle\Sigma^*\rangle\rangle = A_{final}(\mathcal{L})$ sends a word $w \in \Sigma^*$ – an element of the basis of $R^{\Sigma^*}$ – to the derivative $w^{-1}\mathcal{L}$, the series given by $w' \mapsto \mathcal{L}(\vdash ww'\langle\rangle)$. It can be represented by an infinite $\Sigma^* \times \Sigma^*$ matrix, whose $(w, w')$-indexed entry is $\mathcal{L}(\vdash ww'\langle\rangle)$. This matrix is called the *Hankel matrix* of $\mathcal{L}$ in the literature. The image $(\text{Min } \mathcal{L})(\text{st})$ of this morphism is thus the submodule of $R\langle\langle\Sigma^*\rangle\rangle$ generated by all the derivatives $\{w^{-1}\mathcal{L} | w \in \Sigma^*\}$, the rows of the Hankel matrix.

### D. Adjunctions

We recall the definition of an *adjunction* and introduce the notations we need. See, e.g., [49, p. 78–81] for more details.

Let C and D be locally small categories. An *adjunction* between C and D is a pair of functors, $\mathcal{F}: C \to D$ and $\mathcal{G}: D \to C$, together with, for any objects A of C and B of D, a bijection

$$ -^{\sharp}: \mathbf{D}(\mathcal{F}A, B) \to \mathbf{C}(A, \mathcal{G}B) $$

that is *natural in both coordinates*, meaning that, for any $f \in \mathbf{D}(\mathcal{F}A, B)$:

* for any C-morphism $c: A' \to A$ we have $(f \circ \mathcal{F}c)^{\sharp} = f^{\sharp} \circ c$, and

* for any D-morphism $d: B \to B'$, we have $(d \circ f)^{\sharp} = \mathcal{G}d \circ f^{\sharp}$.

In this situation, the functor $\mathcal{F}$ is called *left adjoint* to $\mathcal{G}$, and the functor $\mathcal{G}$ is called *right adjoint* to $\mathcal{F}$.

**Example 37.** The forgetful functor $\mathcal{U}: \mathbf{Mod}_R \to \mathbf{Set}$ given in Example 30.1 has a left adjoint: it is the functor $\mathcal{R}^{-}$ which sends any set $Q$ to the free $R$-module over $Q$, and any function $f: Q \to Q'$ the unique $R$-linear map $R^f: R^Q \to R^{Q'}$ that sends each basis element $q \in R^Q$ to the basis element $f(q)$ of $R^{Q'}$.

In this case, for any set $Q$ and any module $M$, the function $-^{\sharp}: \mathbf{Mod}_R(R^Q, M) \to \mathbf{Set}(Q, UM)$ is given by restricting an $R$-linear map $f: R^Q \to M$ to the basis $Q$, giving a function $Q \to UM$. The fact that $-^{\sharp}$ is a bijection is precisely the familiar fact that any $R$-linear map $R^Q \to M$ is uniquely described by its action on the basis elements. The first naturality property then says that, for any function $c: Q' \to Q$, the restriction of $f \circ R^c$ to the basis $Q'$ is the same function $Q' \to UM$ as the one obtained by first doing $c$, followed by the restriction of $f^{\sharp}$ to the basis $Q$. The second naturality property says that, for any $R$-linear map $d: M \to M'$, the restriction of $d \circ f$ to the basis $Q$ is the same function $Q \to UM'$ as the one obtained by first doing the restriction of $f$ to the basis $Q$, followed by the function underlying $d$.

We denote the inverse to $-^{\sharp}$ by $-_{\flat}$. Explicitly, for any objects A of C and B of D, we have a function

$$ -_{\flat}: \mathbf{C}(A, \mathcal{G}B) \to \mathbf{D}(\mathcal{F}A, B) $$

in such a way that $(f^{\sharp})_{\flat} = f$ and $(g_{\flat})^{\sharp} = g$ for any $f \in \mathbf{D}(\mathcal{F}A, B)$ and $g \in \mathbf{C}(A, \mathcal{G}B)$. It follows from the naturality of $-^{\sharp}$ that $-_{\flat}$ is also natural in both coordinates, which in this case means that, for any $g \in \mathbf{C}(A, \mathcal{G}B)$:

* for any C-morphism $c: A' \to A$ we have $(g \circ c)_{\flat} = g_{\flat} \circ \mathcal{F}c$, and

* for any D-morphism $d: B \to B'$, we have $(\mathcal{G}d \circ g)_{\flat} = d \circ g_{\flat}$.

The *unit* and *count* of an *adjunction* are important natural transformations, defined as follows. For any object A of C, let $\eta_A := (1_A)^{\sharp}$, which is a C-morphism $A \to \mathcal{G}FA$. For any object B of D, let $\varepsilon_B := (1_B)_{\flat}$, which is a D-morphism $\mathcal{F}GB \to B$. It follows from the naturality properties of $-^{\sharp}$ and $-_{\flat}$ that $\eta$ is a natural transformation $1_C \Rightarrow \mathcal{G} \circ \mathcal{F}$, and $\eta$ is a natural transformation $\mathcal{F} \circ \mathcal{G} \Rightarrow 1_D$.

The following fact is standard, but we use it repeatedly in the categorical proofs in this paper, so we give a proof for the reader's convenience.

**Lemma 38.** Let $\mathcal{F}: C \simeq D: \mathcal{G}$ be an *adjunction*, with $-^{\sharp}, -_{\flat}, \eta$, and $\varepsilon$ as above.

1) For any D-morphism $f: \mathcal{F}A \to B$, we have $f^{\sharp} = \mathcal{G}f \circ \eta_A$.

2) For any C-morphism $g: A \to \mathcal{G}B$, we have $g_{\flat} = \varepsilon_B \circ \mathcal{F}g$.

*Proof.* Using first the definition of $\eta_A$ and then the second naturality property of $-^{\sharp}$, we have

$$ \mathcal{G}f \circ \eta_A = \mathcal{G}f \circ (1_A)^{\sharp} = (f \circ id_A)^{\sharp} = f^{\sharp}, $$

establishing (1). The proof of (2) is similar, using the first naturality property of $-_{\flat}$.

□

# APPENDIX F

## PROOFS FOR SECTION V

**Lemma 13.** The functor $R^{-1}: \mathbf{Mod}_R^{tf} \to \mathbf{Vec}_K$ satisfies Assumption 12.

*Proof.* First let us recall that $\mathbf{Mod}_R^{tf}$ and $\mathbf{Vec}_K$ are both equipped with factorization systems consisting of (surjective linear maps, injective linear maps).
1) Assumption 12-1 first requires that $R^{-1}$- preserves surjections. Assume $f: M \to N$ is surjective and $n/r \in R^{-1}N$. There exists $m \in f^{-1}(n)$. Then $R^{-1}f(m/r) = n/r$. More abstractly preservation of surjections also follows from $\mathcal{F}$ being a left adjoint.

The assumption also requires that if $f: M \to N$ in $\mathbf{Mod}_R^{tf}$ is such that $R^{-1}f$ is injective, then $f$ itself is injective. This is true because $M$ is torsion-free: if $m \in M$ is such that $f(m) = 0$, then $f(m/1) = 0$ hence $m/1 = 0$ and thus $s \cdot m = 0$ for some $s \in R$, implying that $m$ itself is zero.

2) The right adjoint to $R^{-1}$: $\mathbf{Mod}_R^{tf} \to \mathbf{Vec}_K$ is the functor $-R: \mathbf{Vec}_K \to \mathbf{Mod}_R^{tf}$, called restriction of scalars, that views a $K$-vector space as only being an $R$-module and a $K$-linear transformation as only being $R$-linear. Given an $R$-module $M$ and a $K$-vector space $V$, notice that an $R$-linear transformation $f: M \to V_R$ indeed extends uniquely to a $K$-linear transformation $R^{-1}M \to V$ by $f(m/r) = 1/r \cdot f(m)$.

3) The unique morphism $\eta_M: M \to (R^{-1}M)_R$ that extends to the identity $R^{-1}M \to R^{-1}M$ is the embedding of $M$ into $R^{-1}M$, sending some $m \in M$ to $m/1$. This embedding is an injection as long as $M$ is torsion-free.

4) The identity $V_R \to V_R$ extends uniquely to the morphism $\varepsilon_V: R^{-1}V_R \to V$ which sends some $v/r \in R^{-1}V_R$ to $1/r \cdot v$. $\varepsilon_V$ is easily seen to be an isomorphism, and hence an injection. $\square$

**Proposition 15.** Under Assumption 12, let $\mathcal{L}$ be a $(C, I, O)$-language. Then $\mathcal{F} \circ \mathrm{Min} \mathcal{L} \cong \mathrm{Min}(\mathcal{F} \circ \mathcal{L})$.

*Proof.* By definition, $\mathrm{Min} \mathcal{L}$ is the unique (up to isomorphism) $(C, I, O)$-automaton such that, in $\mathbf{Auto}(\mathcal{L})$, the unique morphism $A_{init}(\mathcal{L}) \to \mathrm{Min} \mathcal{L}$ is in $\mathcal{E}_C$ and the unique morphism $\mathrm{Min} \mathcal{L} \to A_{final}(\mathcal{L})$ is in $M_C$. By Assumption 12-1, we get, in $\mathbf{Auto}(\mathcal{F} \circ \mathcal{L})$, an $\mathcal{E}_D$-morphism $\mathcal{F} \circ A_{init}(\mathcal{L}) \to \mathcal{F} \circ \mathrm{Min} \mathcal{L}$ and an $M_D$-morphism $\mathcal{F} \circ \mathrm{Min} \mathcal{L} \to \mathcal{F} \circ A_{final}(\mathcal{L})$. (Note that the second part of Assumption 12-1 entails that $\mathcal{F}$ maps morphisms in $M_C$ to morphisms in $M_D$.)

Because $\mathcal{F}$ is a left adjoint by Assumption 12-2, there is an isomorphism $A_{init}(\mathcal{F} \circ \mathcal{L}) \cong \mathcal{F} \circ A_{init}(\mathcal{L})$: this can be seen either by the fact that $A_{init}(\mathcal{F} \circ \mathcal{L})(\mathrm{st}) = \coprod_{\Sigma^*} \mathcal{F}I \cong \mathcal{F}(\coprod_{\Sigma^*} I)$ (left adjoints preserve coproducts), or more generally by the fact that $A_{init}$ is always a left Kan extension [35, Lemma 2.9], and composing by left adjoints preserves left Kan extensions. Hence the unique morphism $A_{init}(\mathcal{F} \circ \mathcal{L}) \to \mathcal{F} \circ \mathrm{Min} \mathcal{L}$ is in $\mathcal{E}_D$.

It is not true that $A_{final}(\mathcal{F} \circ \mathcal{L})$ and $\mathcal{F} \circ A_{final}(\mathcal{L})$ are isomorphic. Still, the unique morphism $\mathcal{F} \circ A_{final}(\mathcal{L}) \to A_{final}(\mathcal{F} \circ \mathcal{L})$ is given on $\mathrm{st}$ by the canonical morphism

$$ \langle \mathcal{F} \pi_w \rangle_{w \in \Sigma^*} : \mathcal{F} \left( \prod_{\Sigma^*} \mathcal{O} \right) \to \prod_{\Sigma^*} \mathcal{F} \mathcal{O} $$

which can be written as the composite

$$ \mathcal{F} \prod_{\Sigma^*} \mathcal{O} \xrightarrow{\mathcal{F} \prod_{\Sigma^*} \eta_{\mathcal{O}}} \mathcal{F} \prod_{\Sigma^*} \mathcal{G} \mathcal{F} \mathcal{O} \cong \mathcal{F} \mathcal{G} \prod_{\Sigma^*} \mathcal{F} \mathcal{O} \xrightarrow{\varepsilon_{\prod_{\Sigma^*} \mathcal{F} \mathcal{O}}} \prod_{\Sigma^*} \mathcal{F} \mathcal{O} $$

(for the isomorphism in the middle, recall that $\mathcal{G}$, as a right adjoint, preserves products).

The proof that this is indeed the morphism we are looking for is given by the universal property of the product and the following commuting diagram, where the vertical arrows are the projections.

<figure><img src="image_10.png" /></figure>

Each term in this decomposition is in $M_D$, because, from left to right: $\eta_F$ is in $M_C$ by Assumption 12-3, $M_C$ is stable under products [38, Proposition 14.15] and $\mathcal{F}$ sends $M_C$-morphisms to $M_D$-ones by Assumption 12-1; $M_D$ contains all isomorphisms; $\varepsilon_{\prod_{\Sigma^*} \mathcal{F} \mathcal{O}}$ is in $M_D$ by Assumption 12-4.

Hence the unique morphism $\mathcal{F} \circ A_{final}(\mathcal{L}) \to A_{final}(\mathcal{F} \circ \mathcal{L})$ is in $M_D$, and so is the unique morphism $\mathcal{F} \circ \mathrm{Min} \mathcal{L} \to A_{final}(\mathcal{F} \circ \mathcal{L})$ as the composite $\mathcal{F} \circ \mathrm{Min} \mathcal{L} \to \mathcal{F} \circ A_{final}(\mathcal{L}) \to A_{final}(\mathcal{F} \circ \mathcal{L})$.

It follows that $\mathcal{F} \circ \mathrm{Min} \mathcal{L}$ must be $\mathrm{Min}(\mathcal{F} \circ \mathcal{L})$ up to isomorphism. $\square$

**Corollary 16.** Let $R$ be a Dedekind domain, $K$ its field of fractions, and $L$ an $R$-weighted language. If $L$ is computed by a $K$-weighted automaton with $n$ states, then it is also computed by an $R$-weighted automaton with $n+1$ states.

*Proof.* Let $n$ be the number of states of the minimal $K$-weighted automaton recognizing $L$. By Proposition 15, $R^{-1}(\mathrm{Min} L) \cong K^n$ and $\mathrm{Min} L$ has rank $n$. Dedekind domains are Noetherian and integral, and thus in particular weak Fatou rings [24, Chapter 7, Corollary 4.3]: this entails that $L$ is computed by a finite $R$-weighted automaton. Applying Proposition 10, it follows that there is an $R$-weighted automaton with $n+1$ states computing $L$. $\square$
To properly understand what happens under the hood of Algorithm 3, [35, Lemma 3.4] can be very useful. Informally, it says that adjunctions lift to categories of automata. We first spell out how the adjunction gives a correspondence at the level of languages.

**Lemma 39.** Let $\mathcal{F}: \mathbf{C} \to \mathbf{D}$ be left adjoint to $\mathcal{G}: \mathbf{D} \to \mathbf{C}$ and fix two objects $\mathbf{C}$ in $\mathbf{C}$ and $\mathbf{D}$ in $\mathbf{D}$. Then $(\mathbf{C}, \mathcal{C}, \mathcal{G}\mathbf{D})$-languages are in one-to-one correspondence with $(\mathbf{D}, \mathcal{F}\mathbf{C}, \mathbf{D})$-languages.

*Proof.* Recall the natural isomorphism $-^\sharp: \mathbf{D}(\mathcal{F}\mathbf{C}, \mathbf{D}) \to \mathbf{C}(\mathcal{C}, \mathcal{G}\mathbf{D})$ and its inverse $-_b: \mathbf{C}(\mathcal{C}, \mathcal{G}\mathbf{D}) \to \mathbf{D}(\mathcal{F}\mathbf{C}, \mathbf{D})$.

Let $\mathcal{L}$ be a $(\mathbf{D}, \mathcal{F}\mathbf{C}, \mathbf{D})$-language. Then, given a word $w \in \Sigma$, we have a morphism $\mathcal{L}(\triangleright w \triangleleft): \mathcal{F}\mathbf{C} \to \mathbf{D}$. We define $\mathcal{L}^\sharp$ to be the language defined by $\mathcal{L}^\sharp(\triangleright w \triangleleft) = (\mathcal{L}(\triangleright w \triangleleft))^\sharp$. Conversely, for a $(\mathbf{C}, \mathcal{C}, \mathcal{G}\mathbf{D})$-language $\mathcal{L}$, we define $\mathcal{L}_b$ to be the $(\mathbf{D}, \mathcal{F}\mathbf{C}, \mathbf{D})$-language defined by $\mathcal{L}_b(\triangleright w \triangleleft) = (\mathcal{L}(\triangleright w \triangleleft))_b$. $\square$

Through the remaining of this section, we make a small abuse of notation and use $\mathcal{L}^\sharp$ and $\mathcal{L}_b$ to describe languages obtained via the above correspondence.

For an example of this, consider $R^{-1}: \mathrm{Mod}_R \to \mathrm{Vec}_K$ and, as seen in Lemma 13, its right adjoint $-_R: \mathrm{Vec}_K \to \mathrm{Mod}_R$. Then $R^{-1}R = K$ and $K_R = K$, and so $(\mathrm{Mod}_R, R, K)$-languages are in one-to-one correspondence with $(\mathrm{Vec}_K, K, K)$-languages: in both cases, we just specify an element $\mathcal{L}(\triangleright w \triangleleft) \in K$ for every word $w \in \Sigma^*$, and this extends to an $R$-linear map from $R$ or a $K$-linear map from $K$.

**Proposition 40** ([35, Lemma 3.4]). Let $\mathcal{F}: \mathbf{C} \to \mathbf{D}$ be left adjoint to $\mathcal{G}: \mathbf{D} \to \mathbf{C}$ and fix two objects $\mathbf{C}$ in $\mathbf{C}$ and $\mathbf{D}$ in $\mathbf{D}$. Let $\mathcal{L}$ be a $(\mathbf{C}, \mathcal{C}, \mathcal{G}\mathbf{D})$-language, and let $\mathcal{L}_b$ be the corresponding $(\mathbf{D}, \mathcal{F}\mathbf{C}, \mathbf{D})$-language. There is a functor $\mathcal{F}_b: \mathrm{Auto}(\mathcal{L}) \to \mathrm{Auto}(\mathcal{L}_b)$ with a right adjoint $\mathcal{G}^\sharp: \mathrm{Auto}(\mathcal{L}_b) \to \mathrm{Auto}(\mathcal{L})$.

The action of $\mathcal{F}_b$ on a $(\mathbf{C}, \mathcal{C}, \mathcal{G}\mathbf{D})$-automaton $\mathcal{A}$ and of $\mathcal{G}^\sharp$ on a $(\mathbf{D}, \mathcal{F}\mathbf{C}, \mathbf{D})$-automaton $\mathcal{A}'$ are depicted below:

<figure><img src="image_11.png" /></figure>

The unit and counit of this adjunction respectively have for st-components $\mathcal{A}(\mathbf{st}) \to \mathcal{G}\mathcal{F}\mathcal{A}(\mathbf{st}) = (\mathcal{G}^\sharp\mathcal{F}_b\mathcal{A})(\mathbf{st})$ and $(\mathcal{F}_b\mathcal{G}^\sharp\mathcal{A}')(\mathbf{st}) = \mathcal{F}\mathcal{G}\mathcal{A}'(\mathbf{st}) \to \mathcal{A}'(\mathbf{st})$ the unit and counit of the adjunction between $\mathcal{F}$ and $\mathcal{G}$.

Recall that $\mathrm{Auto}(\mathcal{L})$ and $\mathrm{Auto}(\mathcal{L}_b)$ are subcategories of $\mathrm{Auto}(\mathbf{C}, \mathcal{C}, \mathcal{G}\mathbf{D})$ and $\mathrm{Auto}(\mathbf{D}, \mathcal{F}\mathbf{C}, \mathbf{D})$, respectively. The functors $\mathcal{F}_b$ and $\mathcal{G}^\sharp$ easily extend to an adjunction between these larger categories. These functors of course preserve the correspondence of languages described in Lemma 39. As an instance of this, when $\mathbf{C} = \mathbf{I}$ and $\mathbf{D} = \mathcal{F}\mathbf{O}$ for some $\mathbf{C}$-objects $\mathbf{I}$ and $\mathbf{O}$, we obtain the following adjunction

<figure><img src="image_12.png" /></figure>

Note that $\mathcal{F}_b$ and $\mathcal{G}^\sharp$, do not act on automata by mere functor composition, as in Fact 6. Adjoint transposes $(-)^\sharp$ and $(-)_b$ are used in the definitions of $\mathcal{F}_b$ and $\mathcal{G}^\sharp$ to get the input and output object right – thus justifying the notation we adopted for these functors. Nevertheless, the functor $\bar{\mathcal{F}}$ as defined in Fact 6 does play a role in Algorithm 3. Recall also from Section V the identity-on-morphisms functor $\eta_*: \mathrm{Auto}(\mathbf{C}, \mathbf{I}, \mathbf{O}) \to \mathrm{Auto}(\mathbf{C}, \mathbf{I}, \mathcal{G}\mathbf{F}\mathbf{O})$ defined as follows:

<figure><img src="image_13.png" /></figure>

The categories of automata appearing in Algorithm 3 can be summarized as follows.
**Proposition 41.** In the next diagram, $\mathcal{F}_b$ is left adjoint to $\mathcal{G}^\sharp$, $\bar{\mathcal{F}} = \mathcal{F}_b \circ \eta_*$, but $\eta_* \neq \mathcal{G}^\sharp \circ \bar{\mathcal{F}}$.

<figure><img src="image_14.png" /></figure>

*Proof.* We verify that $\bar{\mathcal{F}} = \mathcal{F}_b \circ \eta_*$. Given an $(C, I, O)$-automaton $\mathcal{A}$, $\mathcal{F}_b \circ \eta_*(\mathcal{A})$ is the automaton described below

$$ \mathcal{F}I \xrightarrow{\mathcal{F}\mathcal{A}(\triangleright)} \mathcal{F}\mathcal{A}(\text{st}) \xrightarrow{(\eta_O \circ \mathcal{A}(\triangle))_b} \mathcal{F}O $$

An easy computation shows that $(\eta_O \circ \mathcal{A}(\triangle))_b = (\eta_O)_b \circ \mathcal{F}\mathcal{A}(\triangle) = \mathcal{F}\mathcal{A}(\triangle)$, thus proving that the automaton above is in fact $\bar{\mathcal{F}}(\mathcal{A})$. $\square$

In Problem 2, we thus start with an automaton $\mathcal{A}$ (in the top-left corner) recognizing a $(D, \mathcal{F}I, \mathcal{F}O)$-language $\mathcal{L}$, and we want to compute some $(C, I, O)$-automaton $\text{Min} \, \mathcal{L}'$ (in the bottom corner) such that $\mathcal{F} \circ \mathcal{L}' = \mathcal{L}$, i.e. such that $\mathcal{F}(\text{Min} \, \mathcal{L}')$ is equivalent to $\mathcal{A}$. The strategy of Algorithm 3 can be summed up as: first compute $\mathcal{A}' = \text{Obs} \, \mathcal{A}$, and then compute $\text{Reach}(\mathcal{G}^\sharp \mathcal{A}')$ in $\text{Auto}(\mathcal{L}^\sharp)$ (in the bottom-right corner). For efficiency purposes (Lemma 19), this second computation is done in two steps, which correspond to the two **while** loops. If no counterexample word was produced in the process, the resulting automaton happens to come from the minimal automaton $\text{Min} \, \mathcal{L}'$. This is proved below in Lemma 47.

In the $R$-weighted setting, we consider the localization functor $\mathcal{F} = R^{-1} - : \text{Mod}_R^{tf} \to \text{Vec}_K$ and we instantiate the diagram of Proposition 41 as follows.

<figure><img src="image_15.png" /></figure>

The functor $\bar{\mathcal{F}}$ views an $R$-modular automaton as a $K$-weighted one. The diagonal functor $\mathcal{G}^\sharp$ restricts a $K$-weighted automaton to an extended kind of $R$-weighted automaton: its state-space is still a vector-space, but seen as an $R$-module, and its output weights are still in $K$, not in $R$. Finally, the functor $\eta_*$ takes an $R$-weighted automaton and sees it as having output weights in $K$.

For the rest of this section we work under the Assumption 12 which we recall below.

**Assumption 12.** Under Assumption 11, assume moreover that

1) $\mathcal{F}[\mathcal{E}_C] \subseteq \mathcal{E}_D$ and $\mathcal{F}^{-1}[M_D] = M_C$;

2) $\mathcal{F}$ has a right-adjoint $\mathcal{G}: D \to C$;

3) for every object $X$ of $C$, $\eta_X: X \to \mathcal{G}FX$ is in $M_C$;

4) for every object $Y$ of $D$, $\varepsilon_X: \mathcal{G}FX \to X$ is in $M_D$.

We state some consequences of these assumptions, that will be needed in the following.

**Lemma 42.** *Assuming Assumption 12, the following hold*

1) $m: C \to \mathcal{G}D$ is in $M_C$ if and only if $m_b: \mathcal{F}C \to D$ is in $M_D$;

2) $m: \mathcal{F}C \to D$ is in $M_D$ if and only if $m^\sharp$ is in $M_C$;

3) if $m: D \to D'$ is in $M_D$, then $\mathcal{G}m \in M_C$.

*Proof.* 1) Assume $m: C \to \mathcal{G}D$ is in $M_C$. Recall that $m_b = \varepsilon_D \circ \mathcal{F}m$. Since $\varepsilon_D \in M_D$ (by Item 4) and $\mathcal{F}m \in M_D$ (by Assumption 12-1), so is their composition $m_b$.

In other direction, assume $m_b \in M_D$. Using [38, Proposition 14.9.(2)], we infer from the fact that $m_b = \varepsilon_D \circ \mathcal{F}m \in M_D$ and $\varepsilon_D \in M_D$ that $\mathcal{F}m \in M_D$. By Assumption 12-1 we conclude that $m \in M_C$.

2) This follows trivially from the previous item, since $(m_b)^\sharp = m = (m^\sharp)_b$.
3) Assume $m: D \to D'$ is in $M_D$. By the first item, it suffices to show that $(Gm)_b$ is in $M_D$. Using the naturality of $\epsilon$, we can show that $(Gm)_b = \epsilon_{D'} \circ \mathcal{F}Gm = m \circ \epsilon_D$. Since both $m$ and $\epsilon_D$ are in $M_D$, it follows that so is their composition $(Gm)_b$.

☐

**Lemma 43.** The functor $\mathcal{F}_b$ also satisfies Assumption 12.

*Proof.* The factorizations system we consider on **Auto**(C, C, GD) and **Auto**(D, FC, D) are inherited from C, respectively D, in the sense that, for example an **Auto**(C, C, GD)-morphism in $\mathcal{E}_{\mathcal{Auto}(C,C,GD)}$ iff its st-component is in $\mathcal{E}_C$. Since $\mathcal{F}_b$ is defined on morphisms just as $\mathcal{F}$, Assumption 12-1 readily follows. For Assumption 12-2 recall the functor $\mathcal{G}^\sharp$. Since the units of this adjunction are defined on the st-component as the units of the adjunction $\mathcal{F} \dashv \mathcal{G}$, the remaining two items are also easy to check.
☐

Using the above we can show that the right adjoint $\mathcal{G}^\sharp$ preserves observable automata.

**Lemma 44.** Under the Assumption 12, given an automaton $A$ in **Auto**(D, FI, FO) accepting a language $\mathcal{L}$ the $(C, I, GFO)$-automaton $\mathcal{G}^\sharp(\mathrm{Obs} A)$ is observable, that is, the unique morphism from $\mathcal{G}^\sharp(\mathrm{Obs} A) \to A_{\mathrm{final}}(\mathcal{L}^\sharp)$ has an underlying $M_C$-morphism.

*Proof.* This is an immediate consequence of the following two facts: When restricted to the subcategories **Auto**($\mathcal{L}$) $\to$ **Auto**($\mathcal{L}^\sharp$), $\mathcal{G}^\sharp$ is still a right adjoint and hence preserves final objects. That is $\mathcal{G}^\sharp(A_{\mathrm{final}}(\mathcal{L})) \cong A_{\mathrm{final}}(\mathcal{L}^\sharp)$. We now use the third item of Lemma 42 applied to the $M_D$-morphism $\mathrm{Obs} A \to A_{\mathrm{final}}\mathcal{L}$. It follows that we have an $M_C$-morphism $\mathcal{G}^\sharp(\mathrm{Obs} A) \to \mathcal{G}^\sharp(A_{\mathrm{final}}\mathcal{L}) \cong A_{\mathrm{final}}(\mathcal{L}^\sharp)$.
☐

As an immediate corollary we obtain:

**Corollary 45.** Under Assumption 12, for any (D, FI, FO)-automaton A, the (C, I, GFO)-automata $\mathrm{Reach}_C(\mathcal{G}^\sharp(\mathrm{Obs}_D(A)))$ and $\mathrm{Reach}_C(\mathcal{G}^\sharp(\mathrm{Reach}_D(\mathrm{Obs}_D(A))))$ are minimal, and thus isomorphic.

*Proof.* For the second automaton, recall that $\mathrm{Reach}_D(\mathrm{Obs}_D(A))$ is none other than $\mathrm{Min} \mathcal{L}$, where $\mathcal{L}$ is the language computed by $A$. But $\mathrm{Min} \mathcal{L} \cong \mathrm{Obs}(\mathrm{Min} \mathcal{L})$, hence Lemma 44 applies.
☐

Similar to Proposition 15, we can show that the functor $\eta_*$ preserves minimality.

**Proposition 46.** Let $\mathrm{Min} \mathcal{L}$ be the minimal $(C, I, O)$-automaton for a language $\mathcal{L}$. Then $\eta_*(\mathrm{Min} \mathcal{L})$ is a minimal automaton for the language $\eta_*(\mathcal{L})$, defined by $\eta_*(\mathcal{L})(\vdash w \triangleleft) = \eta_O \circ \mathcal{L}(\vdash w \triangleleft)$.

*Proof.* Note that $\mathrm{Min}(\mathcal{st})$ is obtained as the following factorization $\coprod_{\Sigma^*} I \dashrightarrow \mathrm{Min} \mathcal{L}(\mathcal{st}) \dashrightarrow \coprod_{\Sigma^*} O$. Note that, by virtue of [38, Proposition 14.15], $M_C$ is stable under products. Since $\eta_O \in M_C$, it follows that the map $\coprod_{\Sigma^*} \eta_O : \coprod_{\Sigma^*} O \to \coprod_{\Sigma^*} GFO$ is also in $M_C$. Therefore, we obtain a factorization

$$ \coprod_{\Sigma^*} I \dashrightarrow (\mathrm{Min} \mathcal{L})(\mathcal{st}) \dashrightarrow \coprod_{\Sigma^*} O \dashrightarrow \coprod_{\Sigma^*} GFO $$

proving that $(\mathrm{Min} \mathcal{L})(\mathcal{st})$ is also the state object of the minimal automaton for $\eta_*(\mathcal{L})$. The rightmost map also underlies a morphism of automata, the unique one $\eta_*(A_{\mathrm{final}}(\mathcal{L})) \to A_{\mathrm{final}}(\eta_*\mathcal{L})$. It follows that $\eta_*(\mathrm{Min} \mathcal{L})$ is the factorization of the unique morphism $\eta_*A_{\mathrm{init}}(\mathcal{L}) \cong A_{\mathrm{init}}(\eta_*\mathcal{L}) \to A_{\mathrm{final}}(\eta_*\mathcal{L})$, that is $\mathrm{Min}(\eta_*\mathcal{L})$.
☐

**Lemma 47.** For any (D, FI, FO)-automaton A recognizing a language $\mathcal{L}$ and any (C, I, O)-language $\mathcal{L}'$, $\mathcal{L} = \mathcal{F} \circ \mathcal{L}'$ if and only if $\mathrm{Reach}(\mathcal{G}^\sharp(\mathrm{Obs} A))$ is in the image of $\eta_*$, and in that case $\mathrm{Reach}(\mathcal{G}^\sharp(\mathrm{Obs} A)) \cong \eta_*(\mathrm{Min} \mathcal{L}')$.

*Proof.* Assume $\mathrm{Reach}(\mathcal{G}^\sharp(\mathrm{Obs} A))$ is in the image of $\eta_*$. Then $\mathrm{Reach}(\mathcal{G}^\sharp(\mathrm{Obs} A))$ and also $\mathcal{G}^\sharp(\mathrm{Obs} A)$ recognize a language of the form $\eta_*\mathcal{L}'$ for some (C, I, O)-language $\mathcal{L}'$. This entails that $\mathrm{Obs} A$ recognizes the language $(\eta_*\mathcal{L}')_b$. But by assumption $\mathrm{Obs} A$ also recognizes $\mathcal{L}$, hence for any word $w \in \Sigma^*$ we have

$$ \begin{aligned} \mathcal{L}(\vdash w \triangleleft) &= (\eta_* \mathcal{L}')_b (\vdash w \triangleleft) \\ &= \varepsilon_{\mathcal{F}O} \circ \mathcal{F}((\eta_* \mathcal{L}') (\vdash w \triangleleft)) \\ &= \varepsilon_{\mathcal{F}O} \circ \mathcal{F}(\eta_O \circ \mathcal{L}' (\vdash w \triangleleft)) \\ &= \varepsilon_{\mathcal{F}O} \circ \mathcal{F}(\eta_O) \circ \mathcal{F}(\mathcal{L}' (\vdash w \triangleleft)) \\ &= \mathcal{F}(\mathcal{L}' (\vdash w \triangleleft)) \end{aligned} $$

Hence $\mathcal{L} = \mathcal{F} \circ \mathcal{L}'$.
Conversely, assume $\mathcal{L} = \mathcal{F} \circ \mathcal{L}'$. By Corollary 45, $\text{Reach}(\mathcal{G}^{\#}(\text{Obs} \mathcal{A}))$ is the minimal automaton for the language $\mathcal{L}^{\#}$. But $\mathcal{L}^{\#} = (\mathcal{F} \circ \mathcal{L}')^{\#} = ((\eta_{*}\mathcal{L}')_{b})^{\#} = \eta_{*}\mathcal{L}'$. On the other hand, Proposition 46 establishes that the minimal automaton for $\eta_{*}\mathcal{L}'$ is $\eta_{*}(\text{Min } \mathcal{L}')$. Hence, $\text{Reach}(\mathcal{G}^{\#}(\text{Obs} \mathcal{A})) \cong \eta_{*}(\text{Min } \mathcal{L}')$. $\square$

The correctness of Algorithm 3, claimed in Theorem 18, follows:

**Lemma 48.** Algorithm 3 either outputs some $w \in \Sigma^*$ such that $\mathcal{L}(\triangleright w \triangleleft) \notin \mathcal{F}[\mathcal{C}(I, O)]$, or there is some $(\mathcal{C}, I, O)$-language $\mathcal{L}'$ such that $\mathcal{L} = \mathcal{F} \circ \mathcal{L}$ in which case Algorithm 3 computes an I-generating family for and outputs $(\text{Min } \mathcal{L}')(\mathbf{st})$.

*Proof.* Again, in the setting of Algorithm 3, write $\mathcal{A}' = \text{Obs } \mathcal{A}$. If Algorithm 3 stops and outputs some $w \in \Sigma^*$, then it is clear that $\mathcal{L}(\triangleright w \triangleleft) \notin \mathcal{F}[\mathcal{C}(I, O)]$ as $\mathcal{A}'$ recognizes $\mathcal{L}$.

Assume now that Algorithm 3 does not output any word and reaches line 11. Let $W \subseteq \Sigma^*$ be the set of generating words obtained at the end of the second **while** loop (Line 10).

Then by [41, Theorem 3.6],

$$ (\mathcal{G}^{\#}\mathcal{A}')(\triangleright W) \cong \text{Reach}(\mathcal{G}^{\#}\mathcal{A}')(\mathbf{st}) \to \mathcal{G}^{\#}(\mathcal{A}')(\mathbf{st}) $$

For a proof sketch of this, notice that at the end of this second **while** loop, for every $w \in W$ and $\sigma \in \Sigma$, $(\mathcal{G}^{\#}\mathcal{A}')(\triangleright W) \cong (\mathcal{G}^{\#}\mathcal{A}')(\triangleright (W \cup \{w\sigma\}))$. By [41, Lemma B.4], we deduce that, unsurprisingly $(\mathcal{G}^{\#}\mathcal{A}')(\triangleright W) \cong (\mathcal{G}^{\#}\mathcal{A}')(\triangleright (W \cup W\Sigma))$. It then follows by [41, Proposition B.3] that

$$ \begin{aligned} (\mathcal{G}^{\#}\mathcal{A}')(\triangleright W) &\cong (\mathcal{G}^{\#}\mathcal{A}')(\triangleright W\Sigma^{\le 1}) \\ &\cong (\mathcal{G}^{\#}\mathcal{A}')(\triangleright W\Sigma^{\le 2}) \\ &\cong \dots \\ &\cong (\mathcal{G}^{\#}\mathcal{A}')(\triangleright W\Sigma^{\le k}) \\ &\cong \dots \\ &\cong (\mathcal{G}^{\#}\mathcal{A}')(\triangleright \Sigma^*) \\ &\cong \text{Reach}(\mathcal{G}^{\#}\mathcal{A}')(\mathbf{st}) \end{aligned} $$

The second-to-last isomorphism relies on the fact that $W$ is prefix-closed, i.e. contains $\varepsilon$ and is such that if $w\sigma \in W$, then $w \in W$ as well.

Note here that the first **while** loop (lines 2 to 6) does not play a role in the correctness, and could be skipped. It is only there to ensure that Lemma 19 holds.

Write $l'_w: I \to O$ to be such that $\mathcal{L}(\triangleright w \triangleleft) = \mathcal{F}l'_w$ for every $w \in W$. We now show that $\text{Reach}(\mathcal{G}^{\#}\mathcal{A}')$ is in the image of $\eta_{*}$. By Lemma 47, this will entail that Algorithm 3 indeed computes $(\text{Min } \mathcal{L}')(\mathbf{st}) \cong (\text{Reach}(\mathcal{G}^{\#}\mathcal{A}'))(\mathbf{st})$.

Because $W$ is an I-generating family of $\mathcal{G}^{\#}\mathcal{A}'$, $(\text{Reach}(\mathcal{G}^{\#}\mathcal{A}'))(\mathbf{st})$ is obtained as the factorization

$$ \coprod_{W} I \to (\text{Reach}(\mathcal{G}^{\#}\mathcal{A}'))(\mathbf{st}) \to \mathcal{G}^{\#}(\mathcal{A}')(\mathbf{st}) $$

In particular, by [41, Theorem 3.6], $(\text{Reach}(\mathcal{G}^{\#}\mathcal{A}'))(\triangleleft)$ is obtained as the composite of the right cell in the diagram below:

<figure><img src="image_16.png" /></figure>

Because the whole diagram commutes, it follows that the left cell of this same diagram also commutes.

By assumption, for all $w \in W$ we have $\mathcal{L}(\triangleright w \triangleleft)^{\#} = \mathcal{G}\mathcal{F}l'_w \circ \eta_I = \eta_O \circ l'_w$. This left cell can be rewritten as the following commuting square:

<figure><img src="image_17.png" /></figure>

Since $\eta_O$ is in $\mathcal{M}_C$ by Assumption 12-3, we can use the diagonal fill-in property to deduce that $(\text{Reach} \mathcal{G}^{\#}\mathcal{A}')(\triangleleft)$ factors through some $\mathcal{C}$-morphism $(\text{Reach}(\mathcal{G}^{\#}\mathcal{A}'))(\mathbf{st}) \to O$: this means precisely that $\text{Reach}(\mathcal{G}^{\#}\mathcal{A}')$ is in the image of $\eta_{*}$. $\square$
**Theorem 18.** Algorithm 3 is correct$^3$ and reduces the problem of learning minimal (C, I, O)-automata to that of learning minimal (D, FI, FO)-automata.

*Proof.* We proved the correctness of Algorithm 3 in Lemma 48. We now argue that it is indeed the required reduction – the proof is very similar to the explanation given in Section IV for Z-weighted automata.

We reduce the problem of active learning (C, I, O)-automata to that of learning (D, FI, FO)-automata. Suppose thus given an oracle ORACLE_C able to answer value and equivalence queries for a (C, I, O)-language $\mathcal{L}$.

One can first implement an oracle ORACLE_D able to answer value and equivalence queries for the (D, FI, FO)-language $\mathcal{F} \circ \mathcal{L}$:

* for a value query for the word $w \in \Sigma^*$, ask ORACLE_C for $\mathcal{L}(\triangleright w \triangleleft)$ and apply $\mathcal{F}$;

* for an equivalence query for a (D, FI, FO)-automaton $\mathcal{A}$, apply Algorithm 3 to $\mathcal{A}$: the output is either a counterexample word such that $\mathcal{A}(\triangleright w \triangleleft) \notin \mathcal{F}[\mathcal{C}(I, O)]$ and hence $\mathcal{A}(\triangleright w \triangleleft) \neq \mathcal{L}(\triangleright w \triangleleft)$; or a (C, I, O)-automaton computing $\mathcal{L}$, which can then be given for an equivalence query to ORACLE_C.

One may now learn a (D, FI, FO)-automaton $\mathcal{A}$ recognizing $\mathcal{F} \circ \mathcal{L}$ using the aforementioned ORACLE_D, and then use Algorithm 3 on $\mathcal{A}$ to construct a (C, I, O)-automaton recognizing $\mathcal{L}$. $\square$

**Lemma 19.** Let $W_i \subseteq W_{i+1} \subseteq \Sigma^*$ be any two consecutive values of W during Algorithm 3's second while loop (lines 7 to 10), and write $m_i: \mathcal{G}^\#(\mathcal{A}')(\triangleright W_i) \to \mathcal{G}^\#(\mathcal{A}')(\triangleright W_{i+1})$ for the $M_C$-morphism between the corresponding $(\mathcal{E}_C, M_C)$-images. Then, $\mathcal{F}m_i$ is an isomorphism in D.

*Proof.* Recall that $m_i$ is obtained as the diagonal fill-in of the following diagram

<figure><img src="image_18.png" /></figure>

Applying $\mathcal{F}$, which sends $\mathcal{E}_C$-morphisms to $\mathcal{E}_D$-ones and $M_C$-morphisms to $M_D$-ones, and post-composing by the $M_C$-morphism $\varepsilon_{\mathcal{A}'(\mathcal{S}t)}: \mathcal{F}\mathcal{G}\mathcal{A}'(\mathcal{S}t) \to \mathcal{A}'(\mathcal{S}t)$, we get that $\mathcal{F}m_i$ is the diagonal fill-in of the diagram

<figure><img src="image_19.png" /></figure>

and in particular $\mathcal{F}(\mathcal{G}^\#(\mathcal{A}')(\triangleright W_i)) \cong \mathcal{A}'(\triangleright W_i)$. Because the first while loop has stopped, $\mathcal{A}'(\triangleright W_0) \cong \mathcal{A}'(\triangleright (W_0 \cup \{w\sigma\}))$ for every $w \in W$ and $\sigma \in \Sigma$, and so in particular $\mathcal{F}m_0$ is an isomorphism ($W_1$ is obtained from $W_0$ by adding a single word). By [41, Lemma B.4], because every $W_i$ contains $W_0$, we also get for every $i$ that $\mathcal{A}'(\triangleright W_i) \cong \mathcal{A}'(\triangleright (W_i \cup \{w\sigma\}))$ for every $w \in W$ and $\sigma \in \Sigma$, and so similarly $\mathcal{F}m_i$ is also an isomorphism. $\square$

# APPENDIX G

## ALGORITHMIC FRAMEWORK FOR NUMBER RINGS

We first recall the Hermite Normal Form of integer matrices, which is key in computing with ideals in number rings.

### A. Hermite Normal Form of Integer Matrices

The Hermite Normal Form (HNF for short) of integer matrices is analogous to the (column) Echelon Form for rational matrices. Similarly, the HNF has applications in solving linear systems of equations over integers. Furthermore, it plays a key role in algorithmic algebraic number theory, particularly in ideals computation, module theory, and linear algebra over integers and number rings.

An $n \times m$ integer matrix in the (column) HNF can be decomposed as an $n \times r$ zero matrix on the left, concatenated by an $n \times (m-r)$ integer matrix $H$ on the right as $(\mathbf{0}_{n \times r} | H_{n \times (m-r)})$, where for $H = [h_{i,j}]$, there is a strictly increasing map $f: \{1, \dots, m-r\} \to \{1, \dots, n\}$ which assigns each column $j$ of $H$ to a row index $f(j)$, such that

* $h_{i,j} = 0$ for all $i > f(j)$,
• $h_{f(j),j} \ge 1$,

• $0 \le h_{f(i),j} < h_{f(i),i}$ for all $i < j$.

We note in passing that if the matrix $A$ has rank $n$ over $\mathbb{Q}$, then $H$ will be an $n \times n$ upper triangular matrix with all diagonal entries equal to 1; in other words, $f$ will be the identity map. In the general setting, since $f$ is strictly increasing necessarily $m - r \le n$ holds. By [45, Theorem 2.4.3], for all $n \times m$ integer matrices $A$, there exists a unique $n \times m$ matrix $B$ in HNF such that $B = AU$, where $U$ is an invertible $m \times m$ matrix with $\det(U) = \pm 1$. The matrix $H$, formed by the non-zero columns of $B$ as described above, is called the HNF of $A$. The HNF computation of integer matrices can be done in polynomial time, in the dimension of the matrix and the bit length of matrix entries written in binary [50].

**Applications of HNFs.** Let $M \subseteq \mathbb{Z}^n$ be a $\mathbb{Z}$-module, and let $A$ be a $n \times m$ matrix whose columns generates $M$. The columns of the HNF of $A$ form a unique $\mathbb{Z}$-basis of $M$ such that the associated matrix (of the basis) is in HNF. Denote by $\det$ the matrix determinant.

**Lemma 49.** Let $M \subseteq \mathbb{Z}^n$ be a full-rank $\mathbb{Z}$-module, and $A$ an integer matrix whose columns generate $M$. Then $|\mathbb{Z}^n/M| = \det(A)$.

*Proof.* Denote by $H = [h_{i,j}]_{1 \le i,j \le n}$ the HNF of $A$. Since $H$ provides a $\mathbb{Z}$-basis for $M$, the image of $\mathbb{Z}^n$ under $H$, denoted by $\mathbb{Z}^n H$, is $M$. The cosets of $\mathbb{Z}^n H$ in $\mathbb{Z}^n$ are $v + \mathbb{Z}^n H$ where the $i$-th component of $v \in \mathbb{Z}^n$ is in $\{0, \dots, h_{i,i} - 1\}$. Hence $|\mathbb{Z}^n/M| = \det(H) = \det(A)$. $\square$

The uniqueness of the HNF basis of modules allows to test whether two input $\mathbb{Z}$-submodules of $\mathbb{Z}^n$ are equivalent. Given the linear system $Ax = b$ of equations where $A$ and $b$ have integer entries, clearly, the variables $x$ can be chosen integer if the $\mathbb{Z}$-modules generated by columns of $A$ and by columns of $[A|b]$ are equivalent. If so, the HNF of $A$ combined with a simple backward substitution will give a simple way to compute the integer solutions $x$.

## B. Computing in number rings

The symbolic representation of an algebraic number $\alpha$ consists of its minimal polynomial $m_\alpha \in \mathbb{Q}[x]$ combined with a triple $(a, b, R) \in \mathbb{Q}^3$ such that $\alpha$ is the unique root of $m_\alpha$ that lies within the $R$-radius circle centered at $(a, b)$ in the complex plane [45, Section 4.2.1]. The size of the symbolic representation of $\alpha$ is the sum of the degree of its minimal polynomial and the bit length of all these numbers written in binary (where rational numbers are expressed as pairs of integers).

We analyze the complexity of our algorithms for a number field $K$ with degree $d$ over $\mathbb{Q}$. Recall that an integral basis of $O_K$ is a $\mathbb{Z}$-basis $\{\omega_1, \dots, \omega_d\}$ of $O_K$ as a $\mathbb{Z}$-module (that is, $O_K = \mathbb{Z}\omega_1 \oplus \dots \oplus \mathbb{Z}\omega_d$) and of $K$ as a $\mathbb{Q}$-vector space (that is, $K = \mathbb{Q}\omega_1 \oplus \dots \oplus \mathbb{Q}\omega_d$). In our algorithms, we assume that an integral basis $\Omega := \{\omega_1, \dots, \omega_d\}$ of the ring of integer $O_K$, with $\omega_1 = 1$ and the $\omega_i$ represented symbolically, is provided a priori. For each $\omega_i$, we also assume that its regular representation, the $d \times d$-matrix $M_i$ corresponding to the multiplication map by $\omega_i$ in the integral basis $\Omega$, is given. There are classical algorithms for the computation of integral bases for ring of integers from the primitive element of the field [45, Chapter 6].

Let $\theta$ be a primitive element of $K$, that is, $K = \mathbb{Q}(\theta)$. Recall that $[K:\mathbb{Q}] = d$. Then there are exactly $d$ distinct $\mathbb{Q}$-linear embedding $\sigma_i: K \to \mathbb{C}$ with $i \in \{1, \dots, d\}$. Moreover, the elements $\sigma_i(\theta)$ are precisely the $d$ distinct zeros of the minimum polynomial $m_\theta$ of $\theta$. Given the integral basis $\Omega := \{\omega_1, \dots, \omega_d\}$, the discriminant of $K$ is defined as

$$ \Delta_K := \det \begin{pmatrix} \sigma_1(\omega_1) & \sigma_1(\omega_2) & \cdots & \sigma_1(\omega_d) \\ \vdots & \vdots & \ddots & \vdots \\ \sigma_d(\omega_1) & \sigma_d(\omega_2) & \cdots & \sigma_d(\omega_d) \end{pmatrix}^2 . $$

The discriminant $\Delta_K$ is independent of the choice of $\Omega$ and depends only on the number field $K$. Define $C_K := d^4(\log d + \log \Delta_K)$ to be the complexity measure of $K$, where $\log$ is in based 2.

Since we use the main procedure in [42] for the computation of the HNF over $O_K$, we closely follow the algorithmic framework introduced therein. In particular, as required in [42], we will need a primitive element $\theta \in O_K$ to be given a priori, where its minimal polynomial $m_\theta = x^d + \sum_{i=0}^{d-1} a_i x^i$ satisfies that

• $\log(|\mathrm{disc}(m_\theta)|) \le C_K$, where

$$ \mathrm{disc}(m_\theta) := \prod_{1 \le i \le j \le d} |\sigma_i(\theta) - \sigma_j(\theta)|^2, $$

• the bit length of $a_i$ is bounded by $C_K$.

By a variant of the primitive element theorem [51], there exist $c_1, \dots, c_d \in \{0, 1\}$ such that $\sum_{i=1}^d c_i \omega_i$, with $\omega_i \in \Omega$, is a primitive element of $K$. It is shown in [42] that among such primitive elements there exists one that satisfies the required condition.
**Algorithm 5** Computing generators of the forward module or a counterexample.

**Input:** a K-weighted automaton $\mathcal{A} = (Q, \mathcal{A}(\triangleright), (\mathcal{A}(\sigma))_{\sigma \in \Sigma}, \mathcal{A}(\triangle))$ with $m$ states

1: $W = \{\varepsilon\}$ // Finding words that increase the rank

2: **while** there is $(w, \sigma) \in W_B \times \Sigma$ such that $\mathcal{A}(\triangleright w\sigma) \notin \langle \mathcal{A}(\triangleright u) | u \in W_B \rangle_K$ **do**

3: $W := W \cup \{w\sigma\}$ // alternatively, check whether $\mathcal{A}(\triangleright w\sigma) \notin \mathcal{O}_K^m$

4: **if** $\mathcal{A}(\triangleright w\sigma\triangle) \notin \mathcal{O}_K$ **then**

5: **return** $w\sigma$

6: **end if**

7: **end while** // Finding words that augment the module

8: **while** there is $(w, \sigma) \in W_B \times \Sigma$ such that $\mathcal{A}(\triangleright w\sigma) \notin \langle \mathcal{A}(\triangleright u) | u \in W_B \rangle_K$ **do**

9: $W := W \cup \{w\sigma\}$ // alternatively, check whether $\mathcal{A}(\triangleright w\sigma) \notin \mathcal{O}_K^m$

10: **if** $\mathcal{A}(\triangleright w\sigma\triangle) \notin \mathcal{O}_K$ **then**

11: **return** $w\sigma$

12: **end if**

13: **end while**

14: **return** $W$

Given the integral basis $\Omega$, an algebraic number $\alpha$ can be written uniquely as $\alpha := \sum_{1 \le i < d} c_i \omega_i$; we call the vector of coefficients $[c_1, \dots, c_d] \in \mathbb{Q}^d$ the vector representation of $\alpha$. The size of the vector representation of $\alpha$, denoted by $S(\alpha)$, is the sum of the bit length of the $c_i$'s. Clearly, if $\alpha \in \mathcal{O}_K$ its vector representation is in $\mathbb{Z}^d$. In our algorithms we work with vector representations of algebraic numbers. The complexity measure $C_K$ of is defined such that

$$ \log(|\mathcal{N}(\alpha)|) \le d(\log(C_K) + S(\alpha)) \quad (3) $$

for all $\alpha \in \mathcal{O}_K$; see [42, Inequalities (1-3) on Page 9] for more details.

Given the vector representation of algebraic numbers in $K$ with respect to $\Omega$, we adapt [42, Proposition 4] to show that for all $\alpha, \beta \in K$ and $m \in \mathbb{Z}$, the following holds

1) $S(m\alpha) = d\log(m) + S(\alpha)$,

2) $S(\alpha\beta) = S(\alpha) + S(\beta) + C$

3) $S(\frac{1}{\alpha}) = dS(\alpha) + C$,

4) $S(\alpha + \beta) \le \max(S(\alpha), S(\beta)) + d$, if $\alpha + \beta \in \mathcal{O}_K$,

where $C_K$ is the complexity measure of $K$. We note in passing that the constant $C_K$ accounts for the effect of $\Omega$ in the computation. These operations on algebraic numbers can be performed in polynomial time in the complexity measure $C_K$.

Following [42] the fractional ideals $\mathfrak{a}$ of $K$, as free $\mathbb{Z}$-modules of rank $d$, are represented by a $\mathbb{Z}$-basis matrix $N_{\mathfrak{a}} \in \mathbb{Q}^{d \times d}$. For algorithmic purposes, the matrix $N_{\mathfrak{a}}$ is assumed to be in HNF. The size of $\mathfrak{a}$ is the sum of the bit length of all coefficients in $N_{\mathfrak{a}}$ (plus the overhead due to symbolic representation of the integral basis). The sum of two fractional ideals $\mathfrak{a}$ and $\mathfrak{b}$ is defined as $\mathfrak{a} + \mathfrak{b} := \{a+b | a \in \mathfrak{a}, b \in \mathfrak{b}\}$. It can be computed as the sum of $\mathbb{Z}$-modules, whose HNF representation is obtained by the computation of the HNF of the matrix $[N_{\mathfrak{a}} | N_{\mathfrak{b}}]$. For integral ideals, the ideal $\mathfrak{a} + \mathfrak{b}$ can be seen as the greatest common divisor of $\mathfrak{a}$ and $\mathfrak{b}$. The product $\mathfrak{ab} := \{ab | a \in \mathfrak{a}, b \in \mathfrak{b}\}$ can similarly be computed through the HNF representation of the $\mathbb{Z}$-modules of $\mathfrak{a}$ and $\mathfrak{b}$. The above ideal operations in $\mathcal{O}_K$ can be performed in polynomial time in the complexity measure $C_K$.

The norm of an integral ideal $\mathfrak{a}$, denoted by $\mathcal{N}(\mathfrak{a})$, is defined as $|\mathcal{O}_K/\mathfrak{a}|$; it can be computed in polynomial time as the absolute value of $\det(N_{\mathfrak{a}})$, where $\det$ denotes the determinant of the input matrix. Since the norm is multiplicative, the norm of $\mathfrak{a}^{-1}$ is $\mathcal{N}(\mathfrak{a})^{-1}$. Since all fractional ideals can be written as $\mathfrak{a}\mathfrak{b}^{-1}$, where $\mathfrak{a}$ and $\mathfrak{b}$ are integral, their norm can be computed in polynomial time as well.

# APPENDIX H
PROOFS FOR SECTION VI

**Lemma 21** ([43, Lemma 1.2.20]). If $\mathfrak{a}$ and $\mathfrak{b}$ are fractional ideals of $\mathcal{O}_K^n$, there is an isomorphism of $\mathcal{O}_K$-modules such that $\mathfrak{a} \oplus \mathfrak{b} \simeq \mathcal{O}_K \oplus \mathfrak{a}\mathfrak{b}$.

*Sketch of the proof of Lemma 21.* Since for all fractional ideals $\mathfrak{a}$ there exists an integer $r \in \mathbb{Z}$ such that $r\mathfrak{a}$ is integral, without loss of generality, we can assume that $\mathfrak{a}$ and $\mathfrak{b}$ are integral. Recall that two ideals are coprime if their sum is the whole ring. By [43, Corollary 1.2.11] there exists a non-zero $\alpha \in K$ such that $\alpha\mathfrak{a}$ is integral and coprime to $\mathfrak{b}$. Again, without loss of generality, we can assume that $\mathfrak{a}$ and $\mathfrak{b}$ are coprime, meaning that $\mathfrak{a} + \mathfrak{b} = \mathcal{O}_K$. By [43, Proposition 1.3.12] we can find elements

$$ a \in \mathfrak{a} \quad b \in \mathfrak{b} \quad c \in \mathfrak{b}^{-1} \quad d \in \mathfrak{a}^{-1} $$
**Algorithm 6 Computing an (almost) minimal generating set from a pseudo-basis**

**Input:** A pseudo-basis $\{(a_i, v_i) | 1 \le i \le \ell\}$ defining an $\mathcal{O}_K$-module $M$

// Iteratively apply a constructive version of Lemma 21 relying on ideals factor refinement
and the Chinese Remainder Theorem

1. compute a pseudo-generating set for $M$ in the form

$$ \{(\mathcal{O}_K, y_i)|1 \le i \le \ell-1\} \cup \left\{ \left( \prod_{i=1}^{\ell} a_i, z \right) \right\} $$

for some $z \in \mathcal{O}_K^n$.

// By ideal factor refinement

2. find two elements $x_1$ and $x_2$ such that $\prod_{i=1}^{\ell} a_i = x_1 \mathcal{O}_K + x_2 \mathcal{O}_K$.

3. **return** the generating set $\{y_i | 1 \le i \le \ell+1\}$ where

$$ y_{\ell} := x_1 z \quad \text{and} \quad y_{\ell+1} := x_2 z $$

such that $ad - bc = 1$. The proof follows by observing that

$$ (\mathcal{O}_K \quad (ab)^{-1}) = (a^{-1} \quad b^{-1}) \begin{pmatrix} a & c \\ b & d \end{pmatrix}. $$

<figure><img src="image_20.png" /></figure>

**Lemma 23.** Let $\{(a_i, v_i) | 1 \le i \le n\}$ be a pseudo-basis for an $\mathcal{O}_K$-module $M \subseteq \mathcal{O}_K^n$. Given a full representation of $\mathcal{O}_K$, a generating set of cardinality at most $n+1$ is computable within polynomial time in the size of the input pseudo-basis.

**Proof.** To achieve this complexity bound, we use the ideal factor refinement algorithms, introduced for integers in [52] and generalized to number fields in [47]. The factor refinement of integers computes, for inputs $a_1, \dots, a_k \in \mathbb{Z}$, a set of pairwise-coprime factors $m_1, \dots, m_\ell \in \mathbb{Z}$ of the $a_i$'s such that each $a_i$ can be written as a product of these factors, that is, $a_i = \prod_{j=1}^\ell m_j^{e_j}$ with the $e_j \in \mathbb{N}$. Denoting by $a = \text{lcm}(a_1, \dots, a_k)$, the factor refinement algorithm runs in time $\mathcal{O}(\log^2(a))$; see [52] and [53, Lemma 3.1]. The ideal factor refinement [47, Algorithm 5.6] is a generalization, which, given input ideals $\mathcal{J}_1, \dots, \mathcal{J}_k \subseteq \mathcal{O}_K$, computes pairwise-coprime ideals $m_1, \dots, m_\ell \subseteq \mathcal{O}_K$ such that each $\mathcal{J}_i$ can be written as a product of these ideal factors, that is, $\mathcal{J}_i = \prod_{j=1}^\ell m_j^{e_j}$ with the $e_j \in \mathbb{N}$. This algorithm runs in polynomial time in the size of the input ideals in their HNF representation, and in the complexity measure of $K$ [47, Proposition 5.7]. We refer the reader to [47, Section 5] and [54] for more details$^4$.

The steps required to carry out the task at hand – computing a generating set for $M$ of cardinality at most $n+1$ – are shown in Algorithm 6. First, on Line 1, to compute a pseudo-generating set in the form

$$ \{(\mathcal{O}_K, y_i)|1 \le i \le n-1\} \cup \left\{ \left( \prod_{i=1}^{n} a_i, z \right) \right\}, $$

we inductively apply the linear transformation constructed in the proof of Lemma 21. That is, given fractional ideals $a$ and $b$ we find elements

$$ a \in a \qquad b \in b \qquad c \in b^{-1} \qquad d \in a^{-1} \qquad (4) $$

such that $ad - bc = 1$. Then $ax + by = \mathcal{O}_K x' + aby'$ where

$$ (x' \quad y') = (x \quad y) \begin{pmatrix} a & c \\ b & d \end{pmatrix}, $$

see [43, Corollary 1.3.6] for more details. The crucial argument in the complexity analysis of this transformation is to show that the elements $a, b, c$ and $d$ satisfying the required conditions can be found in polynomial time. Write $d$ for a common denominator of the generators of $a$, and define $a' := da$. Observe that $a'$ is integral. Repeat this for $b$ and define the integral ideal $b'$, analogously. Next, we adapt [48, Lemma 5.2.2] to find $a \in a'$ such that $aa'^{-1}$ is integral and coprime to $b'$, but through ideal factor refinement rather than the prime ideal factorization used in the proof therein. More precisely, by [47,

<footnote>$^4$Algorithm 5.6 in [47] is stated for orders of $\mathcal{O}_K$: it computes a factor refinement of input ideals of an order $\mathcal{O}$ into a larger order $\mathcal{O}' \subseteq \mathcal{O}_K$.</footnote>
Algorithm 5.6], we compute pairwise-coprime ideals $m_1, \dots, m_\ell \subseteq \mathcal{O}_K$ such that $a'$ and $b'$ can be written as products of these ideals. We assume without loss of generality that all factors of $b'$ appear among $m_1, \dots, m_r$ for some $r \le \ell$, that is,

$$ a' := \prod_{1 \le i \le \ell} m_i^{e_i} \quad \text{and} \quad b' := \prod_{1 \le i \le r} m_i^{g_i}, $$

with the $e_i, g_i \in \mathbb{N}$. For all $i \in \{1, \dots, r\}$, let $a_i$ be an element such that $a_i \in m_i^{e_i} \setminus m_i^{e_i+1}$. By the generalized Chinese Remainder Theorem [48, Theorem 5.1.4], there exists an element $a \in \mathcal{O}_K$ such that

$$ \begin{align*} a &\equiv a_1 \pmod{m_1^{e_1+1}} \\ &\vdots \\ a &\equiv a_r \pmod{m_r^{e_r+1}} \\ a &\equiv 0 \pmod{\prod_{r \le i \le \ell} m_i^{e_i}} \end{align*} $$

Following an identical reasoning to [48, Lemma 5.2.2], $aa'^{-1}$ is integral and coprime to $b'$. The procedure of finding $a$ can be done within polynomial time through the HNF representation of ideals $m_1^{e_1}$ and $m_1^{e_1+1}$. Moreover, given the coprime ideals $aa'^{-1}$ and $b'$, we can find $e \in aa'$ and $b \in b'$ such that $e+b=1$. Clearly, $c=-1$ and $d=e/a$ satisfy (4) and $ad-bc=1$.

**Second**, on Line 2, we find two elements $x_1$ and $x_2$ such that $\prod_{i=1}^n a_i = x_1 \mathcal{O}_K + x_2 \mathcal{O}_K$. For this task, a randomized polynomial-time procedure in [43, Alg. 1.3.15] is given. To perform this task in polynomial time, we follow [48, Proposition 5.2.3] and again rely on ideal factor refinement. Given an element $x_1$ of $\prod_{i=1}^n a_i$, we find $x_2 \in I$ such that $x_2(\prod_{i=1}^n a_i)^{-1}$ is integral and coprime to $x_1 \mathcal{O}_K$ (we follow the detailed procedure explained above for Line 1). Clearly, the equality $\prod_{i=1}^n a_i = x_1 \mathcal{O}_K + x_2 \mathcal{O}_K$ holds.

□

**Lemma 24.** Let $\{(a_i, v_i) | 1 \le i \le m\}$ be a pseudo-generating set for a full-rank $\mathcal{O}_K$-module $M \subseteq \mathcal{O}_K^n$. Let $A$ be the $n \times m$ matrix whose $i$-th column is $v_i$. Let $\mathfrak{d}$ be the sum of all $n \times n$ minor ideals of $A$ and of the $a_i$'s. Then all strictly increasing chains of $\mathcal{O}_K$-modules $M = M_1 \subset M_2 \subset \dots \subset M_{k-1} \subset M_k \subseteq \mathcal{O}_K^n$ have length at most $\log(\mathcal{N}(\mathfrak{d}))$.

*Proof.* By the properties of the pseudo-HNF of $A$ and of ideals $a_i$, the ideal $\mathfrak{d}$ is integral. Below, we argue that $|\mathcal{O}_K^n/M| = |\mathcal{O}_K/\mathfrak{d}|$. Having shown this, the definition of ideal norm gives that $|\mathcal{O}_K^n/M| = \mathcal{N}(\mathfrak{d})$. Since $\mathbb{Z}^n$ is commutative, all its subgroups are normal, and we may in particular consider the group quotients $\mathcal{O}_K^n/M_i$. By the third isomorphism theorem, each $\mathcal{O}_K^n/M_i$ is a subgroup of $\mathcal{O}_K^n/M_{i+1}$. By Lagrange's Theorem, the order of a subgroup of a finite group is always a divisor of the order of the group, so that $|\mathcal{O}_K^n/M|$ strictly divides $|\mathcal{O}_K^n/M_2|$, which strictly divides in turn $|\mathcal{O}_K^n/M_3|$, etc. all the way up to $|\mathcal{O}_K^n/M_k|$ (the divisibility is strict because the inclusions are strict). It follows that $|\mathcal{O}_K^n/M| \ge 2^k$, and the claimed bound follows.

It remains to prove that $|\mathcal{O}_K^n/M| = |\mathcal{O}_K/\mathfrak{d}|$. Using the pseudo-HNF, there exists $U$ and fractional ideals $c_1, \dots, c_n$ such that $AU = H$ and $M = c_1h_1 \oplus \dots \oplus c_nh_n$ where the $h_i$ is the $i$-th column of $H$. Furthermore, $\prod_{i=1}^n c_i = \mathfrak{d}$ (recall [43, Definition 1.4.8 and Theorem 1.4.9]). Recall from the proof of Lemma 21 that, for all fractional ideals $a$ and $b$, there are elements

$$ a \in \mathfrak{a} \quad b \in \mathfrak{b} \quad c \in \mathfrak{b}^{-1} \quad d \in \mathfrak{a}^{-1} $$

such that $ad - bc = 1$. Then $ax + by = \mathcal{O}_K x' + aby'$ where

$$ (x' \quad y') = (x \quad y) \begin{pmatrix} a & c \\ b & d \end{pmatrix}, $$

see [43, Corollary 1.3.6] for more details. In particular, extending this inductively, there are vectors $\{w_i | 1 \le i \le n\}$ such that the module $M$ can be written as $\mathcal{O}_K w_1 \oplus \dots \oplus \mathcal{O}_K w_{n-1} \oplus \mathfrak{d} w_n$ and hence $|\mathcal{O}_K^n/M| = |\mathcal{O}_K/\mathfrak{d}|$ indeed. □

**Lemma 25.** Given a full representation of $\mathcal{O}_K$, Algorithms 4 and 5 run within polynomial time in the size of the input automaton, the degree of $K$ and the logarithm of its discriminant.

*Proof.* Let $\mathcal{A} = (Q, \mathcal{A}(\triangleright), (\mathcal{A}(\sigma))_{\sigma \in \Sigma}, \mathcal{A}(\prec))$ be the input automaton to these algorithms. We analyze the complexity of the algorithms under the assumption that the entries of $\mathcal{A}(\triangleright)$, $\mathcal{A}(\prec)$ and $\mathcal{A}(\sigma)$ for $\sigma \in \Sigma$ are given in their vector representations with respect to the fixed integral basis $\Omega = \{w_1 = 1, \dots, w_d\}$ of $\mathcal{O}_K$. Write all fractions in these vector representations over a common dominator. Consider the max of the numerators and the denominator of the resulting fractions, and denote by $B_{\mathcal{A}}$ its bit length, which is polynomially bounded in the size (of the vector representation) of $\mathcal{A}$.
Recall that we can assume that the forward-module of the automaton $\mathcal{A}$ is full-rank inside $\mathcal{A}(\text{st})$, because minimization is a polynomial-time procedure. This is important because it then allows us to restrict to the use of full-rank pseudo-HNFs: the non-full-rank pseudo-HNFs are not proven to be computable in polynomial-time in [42], they are only claimed so.

**Complexity Analysis of Algorithm 5:** Recall that we write $m$ for the numbers of states of $\mathcal{A}$. We consider the entries of $\mathcal{A}(\triangleright)$ and the $\mathcal{A}(w)$'s, where $w$ ranges over all words in $\Sigma^*$, as integers in $\mathcal{O}_K$ divided by a common rational integer in $\mathbb{Z}$. By a simple induction on the length of the words, for $\mathcal{A}(\triangleright w) = \frac{1}{q}[a_1 \cdots a_n]$,

* the bit length of the common denominator $q \in \mathbb{Z}$ is bounded by $B_{\mathcal{A}}(|w| + 1)$, and

* $S(a_i) \le (|w| + 1)(B_{\mathcal{A}} + C_K + md)$ for all $i \in \{1, \dots, n\}$,

where $C_K$ is the complexity measure of $K$.

Let $W$ be the set of words found in the first **while** loop on Lines 2 to 7, so that $\{\mathcal{A}(\triangleright w)|w \in W\}$ is a basis for the forward $K$-vector space of $\mathcal{A}$. Clearly, the dimension of the forward $K$-vector space is at most $m$ and thus the first **while** loop iterates at most $m$ times. Moreover, every word in $W$ has length at most $m-1$. At the end of the loop (if it wasn't interrupted) the entries of $\mathcal{A}(\triangleright w)$ for $w \in W$ are in $\mathcal{O}_K$. As computed above, $S((\mathcal{A}(\triangleright w)_i)$ is bounded by $m(B_{\mathcal{A}} + C_K + md)$.

Let $W = \{w_1 = \varepsilon, \dots, w_\ell\}$ for some $\ell \le m$. Define $M := \mathcal{O}_K \mathcal{A}(\triangleright w_1) \oplus \dots \oplus \mathcal{O}_K \mathcal{A}(\triangleright w_\ell)$. Let $A$ be the $\ell \times m$ matrix whose $i$-th column is $\mathcal{A}(\triangleright w_i)$. Let $g$ be the sum of all $\ell \times \ell$ minor ideals of $A$. By Lemma 24, all strictly increasing chains of $\mathcal{O}_K$-modules $M_1 \subset M_2 \subset \dots \subset M_k$ with $M = M_1$ have length $k$ bounded by the number of prime divisors of $N(g)$. The entries $a_{i,j}$ of $A$ are in $\mathcal{O}_K$, and $S(a_{i,j})$ is bounded by $m(B_{\mathcal{A}} + C_K + md)$, as computed above. Given an $\ell \times \ell$ matrix with such entries the determinant $D$ can be computed as a summation of $\ell$ terms, each being a product of $\ell$ distinct matrix entries. To avoid bit-explosion, we perform the $\ell!$ summation in a binary-tree approach: first, summations are done in pairs; then, the sums of these pairs are recursively summed to form the parent nodes. This process continues until a single summation (the determinant) is computed. Then

$$S(D) \le d\ell \log \ell + \ell^2(B_A + C_K + \ell d) + \ell C \le d\ell^2(B_A + 2C_K + 2\ell d).$$

The greatest common divisor $g$ of all $\ell \times \ell$ minors of $A$ also satisfies $S(g) \le d\ell^2(B_A + 2C_K + 2\ell d)$. By inequality (3),

$$\log(|\mathcal{N}(g)|) \le d(\log(C_K) + S(g))$$

which is polynomial in the complexity measure $C_K$ of the number field, the number of states $m$ of the input automaton, and the bit length $B_A$ obtained from the vector representation of entries in $\mathcal{A}(\triangleright)$, $\mathcal{A}(\triangleright \mathbf{d})$ and the $\mathcal{A}(\sigma)$ over a common dominator. Hence, the second **while** loop at Line 11 iterates polynomial many times in our input size.

The manipulation of the algebraic numbers throughout the algorithms is in polynomial time in $C_K$, $B_A$ and $m$. It remains to analyze the complexity of the test whether $\mathcal{A}(\triangleright w\sigma) \notin \langle \mathcal{A}(\triangleright u) | u \in W \rangle_{\mathcal{O}_K}$ at Line 11. For this, we test whether two modules

$$M := \bigoplus_{u \in W} \mathcal{O}_K \mathcal{A}(\triangleright u) \quad \text{and} \quad N := M + \mathcal{O}_K \mathcal{A}(\triangleright w\sigma)$$

are equivalent. This test can be performed through a pseudo-HNF computation. Indeed, if $M \subsetneq N$ then $|\mathcal{O}_K^m/M|$ is strictly larger than $|\mathcal{O}_K^m/N|$. Now, on the one hand, the forward module of $\mathcal{A}'$ is full-rank (inside $\mathcal{A}'(\text{st}) \cong \mathcal{O}_K^m$), and, on the other hand, the rank of the module spanned by the vectors corresponding to words in $W$ at the end of the first **while** loop is full-rank (inside the forward module of $\mathcal{A}'$). It follows that the two modules $M$ and $N$ above are full-rank, and that we can use a full-rank pseudo-HNF to check this: this is thus a polynomial-time operation, as proved in the main Theorem of [42]. This concludes the complexity analysis of Algorithm 5.

**Complexity Analysis of Algorithm 4:** Let $n$ be the number of states of the input $\mathcal{A}$. The manipulation of the algebraic numbers throughout the algorithms is in polynomial time in $C_K$, $B_A$ and $n$. The computation of the pseudo-basis on Line 8 can be done through a full-rank pseudo-HNF computation (because the pseudo-basis is that of the full-rank forward module of $\mathcal{A}'$), which was placed in polynomial time in the main Theorem of [42]. By Lemma 23 a generating family of cardinality of at most $n+1$ can be constructed from the pseudo-basis in polynomial time. The claimed complexity bound for Algorithm 4 follows. $\square$

**Proposition 26.** Deciding whether an $\mathcal{O}_K$-WA is state-minimal is PIP-hard.

Recall that for an integral domain $R$ and two $R$-modules $M \subseteq N$, $M$'s saturation into $N$, written $\text{sat}_N M$, is the intersection $R^{-1}M \cap N$ (within $R^{-1}N$). $M$ is saturated into $N$ when $\text{sat}_N M = M$, or, in other words, when for every $n \in N$ such that $\lambda n \in M$ for some non-zero $\lambda \in R$, then $n \in M$ as well.