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

HAL
open science

# Functorial approach to minimizing and learning deterministic transducers with outputs in arbitrary monoids

Quentin Aristote

► To cite this version:

Quentin Aristote. Functorial approach to minimizing and learning deterministic transducers with outputs in arbitrary monoids. 2024. hal-04172251v3

HAL Id: hal-04172251

https://ens.hal.science/hal-04172251v3

Preprint submitted on 22 Apr 2024

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Functorial approach to minimizing and learning deterministic transducers with outputs in arbitrary monoids

Quentin Aristote

We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out. We use the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile to recover the notion of minimal transducer recognizing a language, and give necessary and sufficient conditions on the output monoid for this minimal transducer to exist and be unique (up to isomorphism). The categorical framework then provides an abstract algorithm for learning it using membership and equivalence queries, and we discuss practical aspects of this algorithm's implementation. We also extend the framework with a categorical algorithm for minimizing transition systems, whose instantiation retrieves the algorithm for minimizing monoidal transducers but also extends the class of output monoids for which this algorithm is valid.

**Acknowledgments.** The author is thankful to Daniela Petrişan and Thomas Colcombet for fruitful discussions.

## 1. Introduction

*Transducers* are (possibly infinite) transition systems that take input words over an input alphabet and translate them to some output words over an output alphabet. They are numerous ways to implement them, but here we focus on *subsequential transducers*, i.e deterministic automata whose transitions also produce an output (see Figure 1 for an example). They are used in diverse fields such as compilers [16], linguistics [19], or natural language processing [20].

Two sequential transducers are considered equivalent when they *recognize* the same *subsequential function*, that is if, given the same input, they always produce the same output. A natural question is thus whether there is a (unique) minimal transducer recognizing a given function (a transducer with a minimal number of states and
# Functorial approach to minimizing and learning deterministic transducers with outputs in arbitrary monoids

Quentin Aristote

We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out. We use the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile to recover the notion of minimal transducer recognizing a language, and give necessary and sufficient conditions on the output monoid for this minimal transducer to exist and be unique (up to isomorphism). The categorical framework then provides an abstract algorithm for learning it using membership and equivalence queries, and we discuss practical aspects of this algorithm's implementation. We also extend the framework with a categorical algorithm for minimizing transition systems, whose instantiation retrieves the algorithm for minimizing monoidal transducers but also extends the class of output monoids for which this algorithm is valid.

**Acknowledgments.** The author is thankful to Daniela Petrişan and Thomas Colcombet for fruitful discussions.

## 1. Introduction

*Transducers* are (possibly infinite) transition systems that take input words over an input alphabet and translate them to some output words over an output alphabet. They are numerous ways to implement them, but here we focus on *subsequential transducers*, i.e deterministic automata whose transitions also produce an output (see Figure 1 for an example). They are used in diverse fields such as compilers [16], linguistics [19], or natural language processing [20].

Two sequential transducers are considered equivalent when they *recognize* the same *subsequential function*, that is if, given the same input, they always produce the same output. A natural question is thus whether there is a (unique) minimal transducer recognizing a given function (a transducer with a minimal number of states and
which produces its output as early as possible), and whether this minimal transducer is
computable. The answer to both these questions is positive when there exists a finite
subsequential transducer recognizing the function: the minimal transducer can then for
example be computed through minimization [9].

**Active learning of transducers.** Another method for computing a minimal transducer is to learn it through Vilar's algorithm [29], a generalization to transducers of Angluin's L\*-algorithm, which learns the minimal deterministic automaton recognizing a language [1]. Vilar's algorithm thus relies on the existence of an oracle which may answer two types of queries, namely:

* *membership queries:* when queried with an input word, the oracle answers with the corresponding expected output word;

* *equivalence queries:* when queried with a *hypothesis transducer*, the oracle answers whether this transducer recognizes the target function, and, if not, provides a counter-example input word for which this transducer is wrong.

The basic idea of the algorithm is to use the membership queries to infer partial knowledge of the target function on a finite subset of input words, and, when some *closure* and *consistency* conditions are fulfilled, use this partial knowledge to build a hypothesis transducer to submit to the oracle through an equivalence query: the oracle then either confirms this transducer is the right one, or provides a counter-example input word on which more knowledge of the target function should be inferred.

<figure><img src="image_1.png" /><figcaption>Figure 1: Two transducers: unlike automata, the transitions are also labelled with output words.</figcaption></figure>

Consider for instance the partial function recognized by the minimal transducer $\mathcal{A}$ of Figure 1a over the input alphabet $A = \{a, b\}$ and output alphabet $\Sigma = \{\alpha, \beta, \gamma\}$. We write this function $\mathcal{L}(\vdash - \Delta) : A^* \to \Sigma^* \cup \{\bot\}$ and let $e \in A^*$ and $\epsilon \in \Sigma^*$ stand for the respective empty words over these two alphabets. To learn $\mathcal{A}$, the algorithm maintains two subsets $Q, T \subset A^*$ of prefixes and suffixes of input words, and keeps track of the restriction of $\mathcal{L}(\vdash - \Delta)$ to words in $QT \cup QAT$. The prefixes in $Q$ will be made into states of the hypothesis transducer, and they will be distinguished according to the output
which produces its output as early as possible), and whether this minimal transducer is
computable. The answer to both these questions is positive when there exists a finite
subsequential transducer recognizing the function: the minimal transducer can then for
example be computed through minimization [9].

**Active learning of transducers.** Another method for computing a minimal transducer is to learn it through Vilar's algorithm [29], a generalization to transducers of Angluin's L\*-algorithm, which learns the minimal deterministic automaton recognizing a language [1]. Vilar's algorithm thus relies on the existence of an oracle which may answer two types of queries, namely:

* *membership queries:* when queried with an input word, the oracle answers with the corresponding expected output word;

* *equivalence queries:* when queried with a *hypothesis transducer*, the oracle answers whether this transducer recognizes the target function, and, if not, provides a counter-example input word for which this transducer is wrong.

The basic idea of the algorithm is to use the membership queries to infer partial knowledge of the target function on a finite subset of input words, and, when some *closure* and *consistency* conditions are fulfilled, use this partial knowledge to build a hypothesis transducer to submit to the oracle through an equivalence query: the oracle then either confirms this transducer is the right one, or provides a counter-example input word on which more knowledge of the target function should be inferred.

<figure><img src="image_3.png" /><figcaption>Figure 1: Two transducers: unlike automata, the transitions are also labelled with output words.</figcaption></figure>

Consider for instance the partial function recognized by the minimal transducer $\mathcal{A}$ of Figure 1a over the input alphabet $A = \{a, b\}$ and output alphabet $\Sigma = \{\alpha, \beta, \gamma\}$. We write this function $\mathcal{L}(\Delta \to \Delta) : A^* \to \Sigma^* \cup \{\bot\}$ and let $e \in A^*$ and $\epsilon \in \Sigma^*$ stand for the respective empty words over these two alphabets. To learn $\mathcal{A}$, the algorithm maintains two subsets $Q, T \subset A^*$ of prefixes and suffixes of input words, and keeps track of the restriction of $\mathcal{L}(\Delta \to \Delta)$ to words in $QT \cup QAT$. The prefixes in $Q$ will be made into states of the hypothesis transducer, and they will be distinguished according to the output
words that should be produced when starting from these states and reading a suffix in
$T$. Informally, closure then holds when for any state $q \in Q$ and input letter $a \in A$ there
is a candidate state $q' \in A$ that we can choose to build an $a$-transition from $q$ to $q'$;
consistency holds when for any $q \in Q$ and $a \in A$ all the states that can be chosen in
such a way can be merged, and when the newly-built $a$-transition can be equipped with
an output word. The execution of the learning algorithm for the function recognized by
$\mathcal{A}$ would thus look like the following.

The algorithm starts with $Q = T = \{e\}$ only consisting of the empty input word.
In a hypothesis transducer, we would want $e \in Q$ to correspond to the initial state, and
the output value produced by the initial transition to be the longest common prefix $\Lambda(e)$
of each $\mathcal{L}(\triangleright et\triangleleft)$ for $t \in T$, here $\Lambda(e) = \alpha$. But the longest common prefix $\Lambda(a)$ of each
$\mathcal{L}(\triangleright at\triangleleft)$ for $t \in T$ is $\gamma\alpha\beta\alpha$, of which $\Lambda(e)$ is not a prefix: it is not possible to make
the output of the first $a$-transition so that following the initial transition and then the
$a$-transition produces a prefix of $\Lambda(a)!$ This is a first kind of consistency issue, which we
solve by adding $a$ to $T$, turning $\Lambda(e)$ into the empty output word $\epsilon$ and $\Lambda(a)$ into $\gamma\alpha\beta$.

Now $Q = \{e\}$ and $T = \{e, a\}$. The initial transition should go into the state
corresponding to $e$ and output $\Lambda(e) = \epsilon$, the final transition from this state should
output $\Lambda(e)^{-1}\mathcal{L}(\triangleright e\triangleleft) = \alpha$, the $a$-transition from this state should output $\Lambda(e)^{-1}\Lambda(a) =
\gamma\alpha\beta$, and this $a$-transition followed by a final transition should output $\Lambda(e)^{-1}\mathcal{L}(\triangleright a\triangleleft) =
\gamma\alpha\beta\alpha$. This $a$-transition should moreover lead to a state from which another $a$-transition
followed by a final transition outputs $\Lambda(a)^{-1}\mathcal{L}(\triangleright aa\triangleleft) = \gamma\beta\alpha^2$: in particular, it cannot
lead back to the state corresponding to $e$, because $\gamma\beta\alpha^2 \neq \gamma\alpha\beta\alpha$. But this state is
the only state accounted for by $Q$, so now we have no candidate for its successor when
following the $a$-transition! This is a closure issue, which we solve by adding $a$ to $Q$, the
corresponding new state then being the candidate successor we were looking for.

Once $Q = T = \{e, a\}$, there are no closure nor consistency issues and we may thus
build the hypothesis transducer given by Figure 1b: it coincides with $\mathcal{A}$ on $QT \cup QAT$.
Submitting it to the oracle we learn that this transducer is not the one we were looking
for, and we get as counter-example the input word $bb$, which indeed satisfies $\mathcal{L}(\triangleright bb\triangleleft) = \bot$
and yet for which our hypothesis transducer produced the output word $\alpha^3$.

With $Q = \{e, a, b, bb\}$ and $T = \{e, a\}$ there is another kind of consistency issue,
because the states corresponding to $e$ and $b$ are not distinguished by $T$ ($\Lambda(e)^{-1}\mathcal{L}(\triangleright et\triangleleft) =
\Lambda(b)^{-1}\mathcal{L}(\triangleright bt\triangleleft)$ for all $t \in T$) and should thus be merged in the hypothesis transducer, yet
this is not the case of their candidate successors when following an additional $b$-transition
($\mathcal{L}(\triangleright ebe\triangleleft) = \alpha$ yet $\mathcal{L}(\triangleright bbe\triangleleft) = \bot$ is undefined)! This issue is solved by adding $b$ to $T$,
after which there are again no closure nor consistency issues and we may thus build $\mathcal{A}$ as
our new hypothesis transducer. The algorithm finally stops as the oracle confirms that
we found the right transducer.

**Transducers with outputs in arbitrary monoids.** In the example above we assumed
that the output of the transducer consisted of words over the output alphabet $\Sigma =
\{\alpha, \beta, \gamma\}$, that is of elements of the free monoid $\Sigma^*$. But in some contexts it may be
relevant to assume that certain output words can be swapped or can cancel out. In
words that should be produced when starting from these states and reading a suffix in
$T$. Informally, closure then holds when for any state $q \in Q$ and input letter $a \in A$ there
is a candidate state $q' \in A$ that we can choose to build an $a$-transition from $q$ to $q'$;
consistency holds when for any $q \in Q$ and $a \in A$ all the states that can be chosen in
such a way can be merged, and when the newly-built $a$-transition can be equipped with
an output word. The execution of the learning algorithm for the function recognized by
$\mathcal{A}$ would thus look like the following.

The algorithm starts with $Q = T = \{e\}$ only consisting of the empty input word.
In a hypothesis transducer, we would want $e \in Q$ to correspond to the initial state, and
the output value produced by the initial transition to be the longest common prefix $\Lambda(e)$
of each $\mathcal{L}(\triangleright et\triangleleft)$ for $t \in T$, here $\Lambda(e) = \alpha$. But the longest common prefix $\Lambda(a)$ of each
$\mathcal{L}(\triangleright at\triangleleft)$ for $t \in T$ is $\gamma\alpha\beta\alpha$, of which $\Lambda(e)$ is not a prefix: it is not possible to make
the output of the first $a$-transition so that following the initial transition and then the
$a$-transition produces a prefix of $\Lambda(a)!$ This is a first kind of consistency issue, which we
solve by adding $a$ to $T$, turning $\Lambda(e)$ into the empty output word $\epsilon$ and $\Lambda(a)$ into $\gamma\alpha\beta$.

Now $Q = \{e\}$ and $T = \{e, a\}$. The initial transition should go into the state
corresponding to $e$ and output $\Lambda(e) = \epsilon$, the final transition from this state should
output $\Lambda(e)^{-1}\mathcal{L}(\triangleright e\triangleleft) = \alpha$, the $a$-transition from this state should output $\Lambda(e)^{-1}\Lambda(a) =
\gamma\alpha\beta$, and this $a$-transition followed by a final transition should output $\Lambda(e)^{-1}\mathcal{L}(\triangleright a\triangleleft) =
\gamma\alpha\beta\alpha$. This $a$-transition should moreover lead to a state from which another $a$-transition
followed by a final transition outputs $\Lambda(a)^{-1}\mathcal{L}(\triangleright aa\triangleleft) = \gamma\beta\alpha^2$: in particular, it cannot
lead back to the state corresponding to $e$, because $\gamma\beta\alpha^2 \neq \gamma\alpha\beta\alpha$. But this state is
the only state accounted for by $Q$, so now we have no candidate for its successor when
following the $a$-transition! This is a closure issue, which we solve by adding $a$ to $Q$, the
corresponding new state then being the candidate successor we were looking for.

Once $Q = T = \{e, a\}$, there are no closure nor consistency issues and we may thus
build the hypothesis transducer given by Figure 1b: it coincides with $\mathcal{A}$ on $QT \cup QAT$.
Submitting it to the oracle we learn that this transducer is not the one we were looking
for, and we get as counter-example the input word $bb$, which indeed satisfies $\mathcal{L}(\triangleright bb\triangleleft) = \bot$
and yet for which our hypothesis transducer produced the output word $\alpha^3$.

With $Q = \{e, a, b, bb\}$ and $T = \{e, a\}$ there is another kind of consistency issue,
because the states corresponding to $e$ and $b$ are not distinguished by $T$ ($\Lambda(e)^{-1}\mathcal{L}(\triangleright et\triangleleft) =
\Lambda(b)^{-1}\mathcal{L}(\triangleright bt\triangleleft)$ for all $t \in T$) and should thus be merged in the hypothesis transducer, yet
this is not the case of their candidate successors when following an additional $b$-transition
($\mathcal{L}(\triangleright ebe\triangleleft) = \alpha$ yet $\mathcal{L}(\triangleright bbe\triangleleft) = \bot$ is undefined)! This issue is solved by adding $b$ to $T$,
after which there are again no closure nor consistency issues and we may thus build $\mathcal{A}$ as
our new hypothesis transducer. The algorithm finally stops as the oracle confirms that
we found the right transducer.

**Transducers with outputs in arbitrary monoids.** In the example above we assumed
that the output of the transducer consisted of words over the output alphabet $\Sigma =
\{\alpha, \beta, \gamma\}$, that is of elements of the free monoid $\Sigma^*$. But in some contexts it may be
relevant to assume that certain output words can be swapped or can cancel out. In
other words, transducers may be considered to be *monoidal* and have output not in a free monoid, but in a quotient of a free monoid. An example of a non-trivial family of monoids that should be interesting to use as the output of a transducer is the family of trace monoids, that are used in concurrency theory to model sequences of executions where some jobs are independent of one another and may thus be run asynchronously: transducers with outputs in trace monoids could be used to programatically schedule some jobs. Algebraically, trace monoids are just free monoids where some pairs of letters are allowed to commute. For instance, the transducers of Figure 1 could be considered under the assumption that $\alpha\beta = \beta\alpha$, in which case the states 1 and 2 would have the same behavior.

This raises the question of the existence and computability of a minimal monoidal transducer recognizing a function with output in an arbitrary monoid. In [17], Gerdjikov gave some conditions on the output monoid for minimal monoidal transducers to exist and be unique up to isomorphism, along with a minimization algorithm that generalizes the one for (non-monoidal) transducers. This question had also been addressed in [15], although in a less satisfying way as the minimization algorithm relied on the existence of stronger oracles. Yet, to the best of the author's knowledge, no work has addressed the problem of learning minimal monoidal transducers through membership and equivalence queries.

As all monoids are quotients of free monoids, a first solution would of course be to consider the target function to have output in a free monoid, learn the minimal (non-monoidal) transducer recognizing this function using Vilar's algorithm, and only then consider the resulting transducer to have output in a non-free monoid and minimize it using Gerdjikov's minimization algorithm. But this solution is unsatisfactory as, during the learning phase, it may introduce states that will be optimized away during the minimization phase. For instance, learning the function recognized by the transducer $\mathcal{A}$ of Figure 1a with the assumption that $\alpha\beta = \beta\alpha$ would first produce $\mathcal{A}$ itself before having its states 1 and 2 merged during the minimization phase. Worse still, it is possible to find a partial function with output in a finitely generated quotient monoid $\Sigma^*/\sim$ and recognized by a finite monoidal transducer, and yet so that, when this function is considered to have output in $\Sigma^*$, Vilar's algorithm may not even terminate if, when answering membership queries, the oracle does not carefully choose the representatives in $\Sigma^*$ of each equivalence class in $\Sigma^*/\sim$ (the idea of finding such an example was suggested by an anonymous reviewer whom the author thanks):

**Lemma 1.1.** Let $A = \{a\}$, $\Sigma = \{\alpha, \beta, \gamma\}$, let $\Sigma/\sim$ be the monoid $\Sigma^*$ with the additional assumption that $\alpha\beta = \beta\alpha$ and let $\pi : \Sigma^* \to \Sigma/\sim$ be the corresponding quotient. Consider the function $f : A^* \to \Sigma/\sim$ that maps $a^n$ to $\alpha^n\beta^n\gamma = (\alpha\beta)^n\gamma$.

$f$ is recognized by a finite transducer with outputs in $\Sigma/\sim$, yet learning a transducer that recognizes any function $f' : A^* \to \Sigma^*$ such that $f = f' \circ \pi$ with Vilar's algorithm will never terminate if the oracle replies to the membership query for $a^n$ with $\alpha^n\beta^n\gamma \in \Sigma^*$ (which differs from $(\alpha\beta)^n\gamma$ in $\Sigma^*$ but not in $\Sigma/\sim$).

A more satisfactory solution would hence do away with the minimization phase and instead use the assumptions on the output monoid during the learning phase to directly
other words, transducers may be considered to be *monoidal* and have output not in a free monoid, but in a quotient of a free monoid. An example of a non-trivial family of monoids that should be interesting to use as the output of a transducer is the family of trace monoids, that are used in concurrency theory to model sequences of executions where some jobs are independent of one another and may thus be run asynchronously: transducers with outputs in trace monoids could be used to programatically schedule some jobs. Algebraically, trace monoids are just free monoids where some pairs of letters are allowed to commute. For instance, the transducers of Figure 1 could be considered under the assumption that $\alpha\beta = \beta\alpha$, in which case the states 1 and 2 would have the same behavior.

This raises the question of the existence and computability of a minimal monoidal transducer recognizing a function with output in an arbitrary monoid. In [17], Gerdjikov gave some conditions on the output monoid for minimal monoidal transducers to exist and be unique up to isomorphism, along with a minimization algorithm that generalizes the one for (non-monoidal) transducers. This question had also been addressed in [15], although in a less satisfying way as the minimization algorithm relied on the existence of stronger oracles. Yet, to the best of the author's knowledge, no work has addressed the problem of learning minimal monoidal transducers through membership and equivalence queries.

As all monoids are quotients of free monoids, a first solution would of course be to consider the target function to have output in a free monoid, learn the minimal (non-monoidal) transducer recognizing this function using Vilar's algorithm, and only then consider the resulting transducer to have output in a non-free monoid and minimize it using Gerdjikov's minimization algorithm. But this solution is unsatisfactory as, during the learning phase, it may introduce states that will be optimized away during the minimization phase. For instance, learning the function recognized by the transducer $\mathcal{A}$ of Figure 1a with the assumption that $\alpha\beta = \beta\alpha$ would first produce $\mathcal{A}$ itself before having its states 1 and 2 merged during the minimization phase. Worse still, it is possible to find a partial function with output in a finitely generated quotient monoid $\Sigma^*/\sim$ and recognized by a finite monoidal transducer, and yet so that, when this function is considered to have output in $\Sigma^*$, Vilar's algorithm may not even terminate if, when answering membership queries, the oracle does not carefully choose the representatives in $\Sigma^*$ of each equivalence class in $\Sigma^*/\sim$ (the idea of finding such an example was suggested by an anonymous reviewer whom the author thanks):

**Lemma 1.1.** Let $A = \{a\}$, $\Sigma = \{\alpha, \beta, \gamma\}$, let $\Sigma/\sim$ be the monoid $\Sigma^*$ with the additional assumption that $\alpha\beta = \beta\alpha$ and let $\pi: \Sigma^* \to \Sigma/\sim$ be the corresponding quotient. Consider the function $f: A^* \to \Sigma/\sim$ that maps $a^n$ to $\alpha^n\beta^n\gamma = (\alpha\beta)^n\gamma$.

$f$ is recognized by a finite transducer with outputs in $\Sigma/\sim$, yet learning a transducer that recognizes any function $f': A^* \to \Sigma^*$ such that $f = f' \circ \pi$ with Vilar's algorithm will never terminate if the oracle replies to the membership query for $a^n$ with $\alpha^n\beta^n\gamma \in \Sigma^*$ (which differs from $(\alpha\beta)^n\gamma$ in $\Sigma^*$ but not in $\Sigma/\sim$).

A more satisfactory solution would hence do away with the minimization phase and instead use the assumptions on the output monoid during the learning phase to directly
produce the minimal monoidal transducer.

**Structure, related work and contributions.** In this work we thus study the problem of generalizing Vilar's algorithm to monoidal transducers.

To this aim, we first recall in Section 2 the categorical framework of Colcombet, Petrişan and Stabile for learning minimal transition systems [10]. This framework encompasses both Angluin's and Vilar's algorithms, as well as a similar algorithm for weighted automata [5, 6]. We use this specific framework because, while others exist, they either do not encompass transducers or require stronger assumptions [3, 27, 28].

In Section 3 we extend this framework with an abstract minimization algorithm. This is not the first categorical account of minimization nor the one that instantiates to the most efficient algorithms [14, 30], but it is the only one that matches the functorial framework of Colcombet, Petrişan and Stabile.

In Section 4 we then instantiate this framework to retrieve monoidal transducers as transition systems whose state-spaces live in a certain category (Section 4.2). Studying the existence of specific structures in this category — namely, powers of the terminal object (Section 4.3) and factorization systems (Section 4.4) — we then give conditions for the framework to apply and hence for the minimal monoidal transducers to exist and be computable.

This paper's contributions are thus the following:

* the framework of Colcombet, Petrişan and Stabile is extended with a categorical minimization algorithm;

* necessary and sufficient conditions on the output monoid for this framework to apply to monoidal transducers are given;

* these conditions mostly overlap those of Gerdjikov, but are nonetheless not equivalent: in particular, they extend the class of output monoids for which minimization is known to be possible, although without ensuring a similar complexity;

* practical details on the implementation of the abstract monoidal transducer-learning algorithm that results from the categorical framework are given;

* additional structure on the category in which the framework is instantiated provides a neat categorical explanation to both the different kinds of consistency issues that arise in the learning algorithm and the main steps that are taken in every transducer minimization algorithm.

## 2. Categorical approach to automata minimization and learning

In this section we recall (and extend) the definitions and results of Colcombet, Petrişan and Stabile [11, 23]. We assume basic knowledge of category theory [21], but we also focus on the example of deterministic complete automata, on the counter-example of non-deterministic automata, and mention the examples of weighted automata and (classical) transducers, the latter being detailed and generalized in Section 4.
produce the minimal monoidal transducer.

**Structure, related work and contributions.** In this work we thus study the problem of generalizing Vilar's algorithm to monoidal transducers.

To this aim, we first recall in Section 2 the categorical framework of Colcombet, Petrişan and Stabile for learning minimal transition systems [10]. This framework encompasses both Angluin's and Vilar's algorithms, as well as a similar algorithm for weighted automata [5, 6]. We use this specific framework because, while others exist, they either do not encompass transducers or require stronger assumptions [3, 27, 28].

In Section 3 we extend this framework with an abstract minimization algorithm. This is not the first categorical account of minimization nor the one that instantiates to the most efficient algorithms [14, 30], but it is the only one that matches the functorial framework of Colcombet, Petrişan and Stabile.

In Section 4 we then instantiate this framework to retrieve monoidal transducers as transition systems whose state-spaces live in a certain category (Section 4.2). Studying the existence of specific structures in this category — namely, powers of the terminal object (Section 4.3) and factorization systems (Section 4.4) — we then give conditions for the framework to apply and hence for the minimal monoidal transducers to exist and be computable.

This paper's contributions are thus the following:

* the framework of Colcombet, Petrişan and Stabile is extended with a categorical minimization algorithm;

* necessary and sufficient conditions on the output monoid for this framework to apply to monoidal transducers are given;

* these conditions mostly overlap those of Gerdjikov, but are nonetheless not equivalent: in particular, they extend the class of output monoids for which minimization is known to be possible, although without ensuring a similar complexity;

* practical details on the implementation of the abstract monoidal transducer-learning algorithm that results from the categorical framework are given;

* additional structure on the category in which the framework is instantiated provides a neat categorical explanation to both the different kinds of consistency issues that arise in the learning algorithm and the main steps that are taken in every transducer minimization algorithm.

## 2. Categorical approach to automata minimization and learning

In this section we recall (and extend) the definitions and results of Colcombet, Petrişan and Stabile [11, 23]. We assume basic knowledge of category theory [21], but we also focus on the example of deterministic complete automata, on the counter-example of non-deterministic automata, and mention the examples of weighted automata and (classical) transducers, the latter being detailed and generalized in Section 4.
## 2.1. Automata and languages as functors

**Definition 2.1** ((C, X, Y)-automaton). An automaton is seen as a functor from the input category *I* to an output category *C*. The input category is the one freely generated by the diagram below, where *a* ranges in the input alphabet *A*: its objects are the vertices of the diagram and its morphisms are the paths between two vertices.

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

We then say that a functor $\mathcal{A} : \mathcal{I} \to \mathcal{C}$ is a $(\mathcal{C}, X, Y)$-automaton when $\mathcal{A}(\mathbf{in}) = X$ and $\mathcal{A}(\mathbf{out}) = Y$.

The input category represents the basic structure of automata as transition systems: $\mathbf{st}$ represents the state-space, $\triangleright$ the initial configuration, $a$ the transitions along the corresponding letters, and $\triangleleft$ the output values associated to each state.

**Example 2.2** (automata and transducers). If $1 = \{\ast\}$ and $2 = \{\bot, \top\}$, a (Set, 1, 2)-automaton $\mathcal{A}$ is a (possibly infinite) deterministic complete automaton: it is given by a state-set $S = \mathcal{A}(\mathbf{st})$, transition functions $\mathcal{A}(a) : S \to S$ for each $a \in A$, an initial state $s_0 = \mathcal{A}(\triangleright)(\ast) \in S$ and a set of accepting states $F = \{s \in S \mid \mathcal{A}(\triangleleft)(s) = \top\} \subseteq S$.

Similarly, a (Rel, 1, 1)-automaton (where Rel is the category of sets and relations between them) is a (possibly infinite) non-deterministic automaton: it is given by a state-set $S = \mathcal{A}(\mathbf{st})$, transition relations $\mathcal{A}(a) \subseteq S \times S$, a set of initial states $\mathcal{A}(\triangleright) \subseteq 1 \times S \cong S$ and a set of accepting states $\mathcal{A}(\triangleleft) \subseteq S \times 1 \cong S$.

If $\mathbb{K}$ is a field we may see $\mathbb{K}$-weighted automata as functors $\mathcal{A}$ from $\mathcal{I}$ to the category of $\mathbb{K}$-vector-spaces, $\mathbb{K}Vec$, such that $\mathcal{A}(\mathbf{in}) = \mathcal{A}(\mathbf{out}) = \mathbb{K}$, and if $B$ is an output alphabet, we may see deterministic transducers as functors from $\mathcal{I}$ to the Kleisli category of free algebras for the monad $\mathcal{T}_{B^*} \times X = B^* \times X + 1$, $\mathbb{KI}(\mathcal{T}_{B^*})$, such that $\mathcal{A}(\mathbf{in}) = \mathcal{A}(\mathbf{out}) = 1$. This last example will be detailed and generalized in Definition 4.9.

**Definition 2.3** ((C, X, Y)-language). In the same way, we define a language to be a functor $\mathcal{L} : \mathcal{O} \to \mathcal{C}$, where $\mathcal{O}$, the category of observable inputs, is the full subcategory of $\mathcal{I}$ on in and out. In other words, a language is the data of two objects $X = \mathcal{L}(\mathbf{in})$ and $Y = \mathcal{L}(\mathbf{out})$ in $\mathcal{C}$ (in which case we speak of a (C, X, Y)-language), and, for each word $w \in A^*$, of a morphism $\mathcal{L}(\triangleright w \triangleleft) : X \to Y$. In particular, composing an automaton $\mathcal{A} : \mathcal{I} \to \mathcal{C}$ with the embedding $\iota : \mathcal{O} \hookrightarrow \mathcal{I}$, we get the language $\mathcal{L}_{\mathcal{A}} = \mathcal{A} \circ \iota$ recognized by $\mathcal{A}$.

**Example 2.4** (languages for classical automata). The language recognized by a (Set, 1, 2)-automaton $\mathcal{A}$ is the language recognized by the corresponding complete deterministic automaton: for a given $w \in A^*$, $\mathcal{L}_{\mathcal{A}}(\triangleright w \triangleleft)(\ast) = \top$ if and only if $w$ belongs to the language, and the equality $\mathcal{L}_{\mathcal{A}}(\triangleright w \triangleleft) = \mathcal{A}(\triangleright w \triangleleft) = \mathcal{A}(\triangleright)\mathcal{A}(w)\mathcal{A}(\triangleleft)$ means that we can decide whether $w$ is in the language by checking whether the state we get in by following $w$ from the initial state is accepting.
## 2.1. Automata and languages as functors

**Definition 2.1** ((C, X, Y)-automaton). An automaton is seen as a functor from the input category *I* to an output category *C*. The input category is the one freely generated by the diagram below, where *a* ranges in the input alphabet *A*: its objects are the vertices of the diagram and its morphisms are the paths between two vertices.

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

We then say that a functor $\mathcal{A} : \mathcal{I} \to \mathcal{C}$ is a $(\mathcal{C}, X, Y)$-automaton when $\mathcal{A}(\mathbf{in}) = X$ and $\mathcal{A}(\mathbf{out}) = Y$.

The input category represents the basic structure of automata as transition systems: $\mathbf{st}$ represents the state-space, $\triangleright$ the initial configuration, $a$ the transitions along the corresponding letters, and $\triangleleft$ the output values associated to each state.

**Example 2.2** (automata and transducers). If $1 = \{\ast\}$ and $2 = \{\bot, \top\}$, a (Set, 1, 2)-automaton $\mathcal{A}$ is a (possibly infinite) deterministic complete automaton: it is given by a state-set $S = \mathcal{A}(\mathbf{st})$, transition functions $\mathcal{A}(a) : S \to S$ for each $a \in A$, an initial state $s_0 = \mathcal{A}(\triangleright)(\ast) \in S$ and a set of accepting states $F = \{s \in S \mid \mathcal{A}(\triangleleft)(s) = \top\} \subseteq S$.

Similarly, a (Rel, 1, 1)-automaton (where Rel is the category of sets and relations between them) is a (possibly infinite) non-deterministic automaton: it is given by a state-set $S = \mathcal{A}(\mathbf{st})$, transition relations $\mathcal{A}(a) \subseteq S \times S$, a set of initial states $\mathcal{A}(\triangleright) \subseteq 1 \times S \cong S$ and a set of accepting states $\mathcal{A}(\triangleleft) \subseteq S \times 1 \cong S$.

If $\mathbb{K}$ is a field we may see $\mathbb{K}$-weighted automata as functors $\mathcal{A}$ from $\mathcal{I}$ to the category of $\mathbb{K}$-vector-spaces, $\mathbb{K}Vec$, such that $\mathcal{A}(\mathbf{in}) = \mathcal{A}(\mathbf{out}) = \mathbb{K}$, and if $B$ is an output alphabet, we may see deterministic transducers as functors from $\mathcal{I}$ to the Kleisli category of free algebras for the monad $\mathcal{T}_{B^*} \times X = B^* \times X + 1$, $\mathbb{KI}(\mathcal{T}_{B^*})$, such that $\mathcal{A}(\mathbf{in}) = \mathcal{A}(\mathbf{out}) = 1$. This last example will be detailed and generalized in Definition 4.9.

**Definition 2.3** ((C, X, Y)-language). In the same way, we define a language to be a functor $\mathcal{L} : \mathcal{O} \to \mathcal{C}$, where $\mathcal{O}$, the category of observable inputs, is the full subcategory of $\mathcal{I}$ on in and out. In other words, a language is the data of two objects $X = \mathcal{L}(\mathbf{in})$ and $Y = \mathcal{L}(\mathbf{out})$ in $\mathcal{C}$ (in which case we speak of a (C, X, Y)-language), and, for each word $w \in A^*$, of a morphism $\mathcal{L}(\triangleright w \triangleleft) : X \to Y$. In particular, composing an automaton $\mathcal{A} : \mathcal{I} \to \mathcal{C}$ with the embedding $\iota : \mathcal{O} \hookrightarrow \mathcal{I}$, we get the language $\mathcal{L}_{\mathcal{A}} = \mathcal{A} \circ \iota$ recognized by $\mathcal{A}$.

**Example 2.4** (languages for classical automata). The language recognized by a (Set, 1, 2)-automaton $\mathcal{A}$ is the language recognized by the corresponding complete deterministic automaton: for a given $w \in A^*$, $\mathcal{L}_{\mathcal{A}}(\triangleright w \triangleleft)(\ast) = \top$ if and only if $w$ belongs to the language, and the equality $\mathcal{L}_{\mathcal{A}}(\triangleright w \triangleleft) = \mathcal{A}(\triangleright w \triangleleft) = \mathcal{A}(\triangleright)\mathcal{A}(w)\mathcal{A}(\triangleleft)$ means that we can decide whether $w$ is in the language by checking whether the state we get in by following $w$ from the initial state is accepting.
Such a language could also be seen as a set of relations $\mathcal{L}(\triangleright w \triangleleft) \subseteq 1 \times 1$, where $*$ is related to itself if and only if $w$ belongs to $\mathcal{L}$. The language recognized by a (Rel, 1, 1)-automaton is thus the language recognized by the corresponding non-deterministic automaton.

Similarly, when $\mathcal{C}$ is $\mathbb{K}Vec$ or $\mathbb{KI}(B^* \times -+1)$ the corresponding notions of languages are those respectively recognized by weighted automata and transducers.

**Definition 2.5** (category of automata recognizing a language). Given a category $\mathcal{C}$ and a language $\mathcal{L} : \mathcal{O} \to \mathcal{C}$, we define the category $\mathbf{Auto}(\mathcal{L})$ whose objects are $(\mathcal{C}, \mathcal{L}(\mathbf{in}), \mathcal{L}(\mathbf{out}))$-automata $\mathcal{A}$ recognizing $\mathcal{L}$, and whose morphisms $\mathcal{A} \to \mathcal{A}'$ are natural transformations whose components on $\mathcal{L}(\mathbf{in})$ and $\mathcal{L}(\mathbf{out})$ are the identity. In other words, a morphism of automata is given by a morphism $f : \mathcal{A}(\mathbf{st}) \to \mathcal{A}'(\mathbf{st})$ in $\mathcal{C}$ such that $\mathcal{A}'(\triangleright) = f \circ \mathcal{A}(\triangleright)$ (it preserves the initial configuration), $\mathcal{A}'(a) \circ f = f \circ \mathcal{A}(a)$ (it commutes with the transitions), and $\mathcal{A}'(\triangleleft) \circ f = \mathcal{A}(\triangleleft)$ (it preserves the output values).

## 2.2. Factorization systems and the minimal automaton recognizing a language

**Definition 2.6** (factorization system). In a category $\mathcal{C}$, a factorization system $(\mathcal{E}, \mathcal{M})$ is the data of a class of $\mathcal{E}$-morphisms (represented with $\Rightarrow$) and a class of $\mathcal{M}$-morphisms (represented with $\mapsto$) $\mathcal{M}$ such that every arrow $f$ in $\mathcal{C}$ may be factored as $f = m \circ e$ with $m \in \mathcal{M}$ and $e \in \mathcal{E}$, $\mathcal{E} \cap \mathcal{M}$ is exactly the class Iso of isomorphisms of $\mathcal{C}$, $\mathcal{E}$ and $\mathcal{M}$ are both stable under composition, and for every commuting diagram

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

where $m \in \mathcal{M}$ and $e \in \mathcal{E}$ there is a unique $d : Y_1 \to Y_2$ such that $u = d \circ e$ and $v = m \circ d$.

**Example 2.7.** (some factorization systems) In Set and $\mathbb{K}Vec$, surjective and injective functions and linear transformations form factorization systems (Surj, Inj) such that a map $f : X \to Y$ factors through its image $f(X) \subseteq Y$. In the Kleisli category for the monad $X \mapsto B^* \times X + 1$, we may define similarly a notion of surjection and injection that gives a meaningful factorization system. Again, this last example will be detailed and generalized in Section 4.4.

Finally, in Rel a factorization system is given by $\mathcal{E}$-morphisms those relations $r : X \to Y$ such that every $y \in Y$ is related to some $x \in X$ by $r$, and $\mathcal{M}$-morphisms the graphs of injective functions (i.e. $m \in \mathcal{M}$ if and only if there is an injective function $f$ such that $(x, y) \in m \iff y = f(x)$). A relation $r : X \to Y$ then factors through the subset $\{y \in Y \mid \exists x \in X, (x, y) \in R\} \subseteq Y$. We write this factorization system (Surj, Det $\cap$ Inj) (for surjections and deterministic injections).

**Lemma 2.8** (factorization system on $\mathbf{Auto}(\mathcal{L})$ [23, Lemma 2.8]). Given $\mathcal{L} : \mathcal{I} \to \mathcal{C}$ and $(\mathcal{E}, \mathcal{M})$ a factorization system on $\mathcal{C}$, $\mathbf{Auto}(\mathcal{L})$ has a factorization given by those natural transformations whose components are respectively $\mathcal{E}$- and $\mathcal{M}$-morphisms.
Such a language could also be seen as a set of relations $\mathcal{L}(\triangleright w \triangleleft) \subseteq 1 \times 1$, where $*$ is related to itself if and only if $w$ belongs to $\mathcal{L}$. The language recognized by a (Rel, 1, 1)-automaton is thus the language recognized by the corresponding non-deterministic automaton.

Similarly, when $\mathcal{C}$ is $\mathbb{K}Vec$ or $\mathbb{KI}(B^* \times -+1)$ the corresponding notions of languages are those respectively recognized by weighted automata and transducers.

**Definition 2.5** (category of automata recognizing a language). Given a category $\mathcal{C}$ and a language $\mathcal{L} : \mathcal{O} \to \mathcal{C}$, we define the category $\mathbf{Auto}(\mathcal{L})$ whose objects are $(\mathcal{C}, \mathcal{L}(\mathbf{in}), \mathcal{L}(\mathbf{out}))$-automata $\mathcal{A}$ recognizing $\mathcal{L}$, and whose morphisms $\mathcal{A} \to \mathcal{A}'$ are natural transformations whose components on $\mathcal{L}(\mathbf{in})$ and $\mathcal{L}(\mathbf{out})$ are the identity. In other words, a morphism of automata is given by a morphism $f : \mathcal{A}(\mathbf{st}) \to \mathcal{A}'(\mathbf{st})$ in $\mathcal{C}$ such that $\mathcal{A}'(\triangleright) = f \circ \mathcal{A}(\triangleright)$ (it preserves the initial configuration), $\mathcal{A}'(a) \circ f = f \circ \mathcal{A}(a)$ (it commutes with the transitions), and $\mathcal{A}'(\triangleleft) \circ f = \mathcal{A}(\triangleleft)$ (it preserves the output values).

## 2.2. Factorization systems and the minimal automaton recognizing a language

**Definition 2.6** (factorization system). In a category $\mathcal{C}$, a factorization system $(\mathcal{E}, \mathcal{M})$ is the data of a class of $\mathcal{E}$-morphisms (represented with $\Rightarrow$) and a class of $\mathcal{M}$-morphisms (represented with $\mapsto$) $\mathcal{M}$ such that every arrow $f$ in $\mathcal{C}$ may be factored as $f = m \circ e$ with $m \in \mathcal{M}$ and $e \in \mathcal{E}$, $\mathcal{E} \cap \mathcal{M}$ is exactly the class Iso of isomorphisms of $\mathcal{C}$, $\mathcal{E}$ and $\mathcal{M}$ are both stable under composition, and for every commuting diagram

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

where $m \in \mathcal{M}$ and $e \in \mathcal{E}$ there is a unique $d : Y_1 \to Y_2$ such that $u = d \circ e$ and $v = m \circ d$.

**Example 2.7.** (some factorization systems) In Set and $\mathbb{K}Vec$, surjective and injective functions and linear transformations form factorization systems (Surj, Inj) such that a map $f : X \to Y$ factors through its image $f(X) \subseteq Y$. In the Kleisli category for the monad $X \mapsto B^* \times X + 1$, we may define similarly a notion of surjection and injection that gives a meaningful factorization system. Again, this last example will be detailed and generalized in Section 4.4.

Finally, in Rel a factorization system is given by $\mathcal{E}$-morphisms those relations $r : X \to Y$ such that every $y \in Y$ is related to some $x \in X$ by $r$, and $\mathcal{M}$-morphisms the graphs of injective functions (i.e. $m \in \mathcal{M}$ if and only if there is an injective function $f$ such that $(x, y) \in m \iff y = f(x)$). A relation $r : X \to Y$ then factors through the subset $\{y \in Y \mid \exists x \in X, (x, y) \in R\} \subseteq Y$. We write this factorization system (Surj, Det $\cap$ Inj) (for surjections and deterministic injections).

**Lemma 2.8** (factorization system on $\mathbf{Auto}(\mathcal{L})$ [23, Lemma 2.8]). Given $\mathcal{L} : \mathcal{I} \to \mathcal{C}$ and $(\mathcal{E}, \mathcal{M})$ a factorization system on $\mathcal{C}$, $\mathbf{Auto}(\mathcal{L})$ has a factorization given by those natural transformations whose components are respectively $\mathcal{E}$- and $\mathcal{M}$-morphisms.
Because of this last result, we use $(\mathcal{E}, \mathcal{M})$ to refer both to a factorization on $\mathcal{C}$ and to its extensions to categories of automata.

**Definition 2.9 (minimal object).** When a category $\mathcal{C}$, equipped with a factorization system $(\mathcal{E}, \mathcal{M})$, has both an initial object $I$ and a final object $F$ (for every object $X$ there is exactly one morphism $I \to X$ and one morphism $X \to F$), we define its $(\mathcal{E}, \mathcal{M})$-minimal object $\text{Min}$ to be the one that $(\mathcal{E}, \mathcal{M})$-factors the unique arrow $I \to F$ as $I \twoheadrightarrow \text{Min} \twoheadrightarrow F$. For every object $X$ we also define $\text{Reach} X$ and $\text{Obs} X$ by the $(\mathcal{E}, \mathcal{M})$-factorizations $I \twoheadrightarrow \text{Reach} X \twoheadrightarrow X$ and $X \twoheadrightarrow \text{Obs} X \twoheadrightarrow F$; when the morphism $I \to X$ is in $\mathcal{E}$ we say $X$ is *reachable* and when the morphism $X \to F$ we say it is *observable*.

**Proposition 2.10** (($\mathcal{E}, \mathcal{M}$)-minimality [23, Lemma 2.3]). The minimal object of a category $\mathcal{C}$ is unique up to isomorphism, and is $(\mathcal{E}, \mathcal{M})$-minimal in the sense that it $(\mathcal{E}, \mathcal{M})$-divides every other object $X$, meaning we have commuting diagrams

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

In particular, $\text{Min} \cong \text{Obs}(\text{Reach} X) \cong \text{Reach}(\text{Obs} X)$.

**Example 2.11** (initial, final and minimal automata and transducers [23, Example 3.1]). Since **Set** is complete and cocomplete, the category of (**Set**, 1, 2)-automata recognizing a language $\mathcal{L} : I_{A^*} \to \text{Set}$ has an initial, a final and a minimal object. The initial automaton has state-set $A^*$, initial state $\epsilon \in A^*$, transition functions $\delta_a(w) = wa$ and accepting states the $w \in A^*$ such that $w$ is in $\mathcal{L}$. Similarly, the final automaton has state-set $2^{A^*}$, initial state $\mathcal{L}$, transition functions $\delta_a(\mathcal{L}) = a^{-1}\mathcal{L}$ and accepting states the $\mathcal{L} \in 2^{A^*}$ such that $\epsilon$ is in $\mathcal{L}$. The minimal automaton for the factorization system of Example 2.7 thus has the Myhill-Nerode equivalence classes for its states. It is unique up to isomorphism and its $(\mathcal{E}, \mathcal{M})$-minimality ensures that it is the complete deterministic automaton with the smallest state-set that recognizes $\mathcal{L}$: it is in particular finite as soon as $\mathcal{L}$ is recognized by a finite automaton.

For the same reason, the category of $(\mathbb{K}\text{Vec}, \mathbb{K}, \mathbb{K})$-automata recognizing a language $\mathcal{L} : \mathcal{I} \to \mathbb{K}\text{Vec}$ also has a minimal object that corresponds to the minimal $\mathbb{K}$-weighted automaton recognizing $\mathcal{L}$ [25]. The example of transducers seen as automata over the Kleisli category for the monad $X \mapsto B^* \times X + 1$ is more involved: this category has all coproducts, but not necessarily products. Yet, it happens that 1 does have countable powers, and hence minimization is still possible for $(\mathbb{K}\text{I}(\mathcal{T}), 1, 1)$-automata : with the right factorization system, we retrieve Choffrut's minimal transducer [9].

On the contrary, there is no good notion of a unique minimal non-deterministic automaton recognizing a regular ((**Rel**, 1, 1)-)language $\mathcal{L}$. **Auto(\mathcal{L})$ does have an initial and a final object: the initial automaton is the initial deterministic automaton recognizing $\mathcal{L}$, and the final automaton is the (non-deterministic) transpose of this initial
Because of this last result, we use $(\mathcal{E}, \mathcal{M})$ to refer both to a factorization on $\mathcal{C}$ and to its extensions to categories of automata.

**Definition 2.9 (minimal object).** When a category $\mathcal{C}$, equipped with a factorization system $(\mathcal{E}, \mathcal{M})$, has both an initial object $I$ and a final object $F$ (for every object $X$ there is exactly one morphism $I \to X$ and one morphism $X \to F$), we define its $(\mathcal{E}, \mathcal{M})$-minimal object $\text{Min}$ to be the one that $(\mathcal{E}, \mathcal{M})$-factors the unique arrow $I \to F$ as $I \twoheadrightarrow \text{Min} \twoheadrightarrow F$. For every object $X$ we also define $\text{Reach} X$ and $\text{Obs} X$ by the $(\mathcal{E}, \mathcal{M})$-factorizations $I \twoheadrightarrow \text{Reach} X \twoheadrightarrow X$ and $X \twoheadrightarrow \text{Obs} X \twoheadrightarrow F$; when the morphism $I \to X$ is in $\mathcal{E}$ we say $X$ is *reachable* and when the morphism $X \to F$ we say it is *observable*.

**Proposition 2.10** (($\mathcal{E}, \mathcal{M}$)-minimality [23, Lemma 2.3]). The minimal object of a category $\mathcal{C}$ is unique up to isomorphism, and is $(\mathcal{E}, \mathcal{M})$-minimal in the sense that it $(\mathcal{E}, \mathcal{M})$-divides every other object $X$, meaning we have commuting diagrams

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

In particular, $\text{Min} \cong \text{Obs}(\text{Reach} X) \cong \text{Reach}(\text{Obs} X)$.

**Example 2.11** (initial, final and minimal automata and transducers [23, Example 3.1]). Since **Set** is complete and cocomplete, the category of (**Set**, 1, 2)-automata recognizing a language $\mathcal{L} : I_{A^*} \to \text{Set}$ has an initial, a final and a minimal object. The initial automaton has state-set $A^*$, initial state $\epsilon \in A^*$, transition functions $\delta_a(w) = wa$ and accepting states the $w \in A^*$ such that $w$ is in $\mathcal{L}$. Similarly, the final automaton has state-set $2^{A^*}$, initial state $\mathcal{L}$, transition functions $\delta_a(\mathcal{L}) = a^{-1}\mathcal{L}$ and accepting states the $\mathcal{L} \in 2^{A^*}$ such that $\epsilon$ is in $\mathcal{L}$. The minimal automaton for the factorization system of Example 2.7 thus has the Myhill-Nerode equivalence classes for its states. It is unique up to isomorphism and its $(\mathcal{E}, \mathcal{M})$-minimality ensures that it is the complete deterministic automaton with the smallest state-set that recognizes $\mathcal{L}$: it is in particular finite as soon as $\mathcal{L}$ is recognized by a finite automaton.

For the same reason, the category of $(\mathbb{K}\text{Vec}, \mathbb{K}, \mathbb{K})$-automata recognizing a language $\mathcal{L} : \mathcal{I} \to \mathbb{K}\text{Vec}$ also has a minimal object that corresponds to the minimal $\mathbb{K}$-weighted automaton recognizing $\mathcal{L}$ [25]. The example of transducers seen as automata over the Kleisli category for the monad $X \mapsto B^* \times X + 1$ is more involved: this category has all coproducts, but not necessarily products. Yet, it happens that 1 does have countable powers, and hence minimization is still possible for $(\mathbb{K}\text{I}(\mathcal{T}), 1, 1)$-automata : with the right factorization system, we retrieve Choffrut's minimal transducer [9].

On the contrary, there is no good notion of a unique minimal non-deterministic automaton recognizing a regular ((**Rel**, 1, 1)-)language $\mathcal{L}$. **Auto(\mathcal{L})$ does have an initial and a final object: the initial automaton is the initial deterministic automaton recognizing $\mathcal{L}$, and the final automaton is the (non-deterministic) transpose of this initial
automaton. But there is no factorization system that gives rise to a meaningful minimal object: for instance, the minimal object for the factorization system described in Example 2.7 has for state-set the set of suffixes of words in $\mathcal{L}$.

Notice how in Example 2.11 the initial and final (Set, 1, 2)-automata have for respective state-sets $A^*$, the disjoint union of $|A^*|$ copies of 1, and $2^{2^{A^*}}$, the cartesian product of $|A^*|$ copies of 2. A similar result holds for weighted automata and transducers, and generalizes as Theorem 2.12.

**Theorem 2.12** ([23, Lemma 3.2]). Given a language $\mathcal{L} : \mathcal{I} \to \mathcal{C}$ with $\mathcal{A}$ countable,

* if $\mathcal{C}$ has all countable copowers of $\mathcal{L}(\mathbf{in})$ then $\mathbf{Auto}(\mathcal{L})$ has an initial object $\mathcal{A}^{\text{init}}(\mathcal{L})$ with $\mathcal{A}^{\text{init}}(\mathcal{L})(\mathbf{st}) = \coprod_{A^*} \mathcal{L}(\mathbf{in})$;

* dually if $\mathcal{C}$ has all countable powers of $\mathcal{L}(\mathbf{out})$ then $\mathbf{Auto}(\mathcal{L})$ has a final object $\mathcal{A}^{\text{final}}(\mathcal{L})$ with $\mathcal{A}^{\text{final}}(\mathcal{L})(\mathbf{st}) = \prod_{A^*} \mathcal{L}(\mathbf{out})$;

* hence when both of the previous items hold and $\mathcal{C}$ is equipped with a factorization system $(\mathcal{E}, \mathcal{M})$, $\mathbf{Auto}(\mathcal{L})$ has an $(\mathcal{E}, \mathcal{M})$-minimal object $\text{Min}\,\mathcal{L}$.

This is summarized by the diagram below, where $\kappa$ and $\pi$ are the canonical inclusion and projections.

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

We now have all the ingredients to define algorithms for computing the minimal automaton recognizing a language. But since we will also want to prove the termination of these algorithms, we need an additional notion of finiteness.

**Definition 2.13** $(\mathcal{E}$-artinian and $\mathcal{M}$-noetherian objects [10, Definition 24]). In a category $\mathcal{C}$ equipped with a factorization system $(\mathcal{E}, \mathcal{M})$, an object $X$ is said to be $\mathcal{M}$-noetherian if every strict chain of $\mathcal{M}$-subobjects is finite: if $(x_n : X_n \to X)_{n \in \mathbb{N}}$ and $(m_n : X_n \to X_{n+1})$ form the commutative diagram

<figure><img src="image_6.png" /></figure>
automaton. But there is no factorization system that gives rise to a meaningful minimal object: for instance, the minimal object for the factorization system described in Example 2.7 has for state-set the set of suffixes of words in $\mathcal{L}$.

Notice how in Example 2.11 the initial and final (**Set**, 1, 2)-automata have for respective state-sets $A^*$, the disjoint union of $|A^*|$ copies of 1, and $2^{2^{A^*}}$, the cartesian product of $|A^*|$ copies of 2. A similar result holds for weighted automata and transducers, and generalizes as **Theorem 2.12**.

**Theorem 2.12** ([23, Lemma 3.2]). Given a language $\mathcal{L} : \mathcal{I} \to \mathcal{C}$ with $\mathcal{A}$ countable,

* if $\mathcal{C}$ has all countable copowers of $\mathcal{L}(\mathbf{in})$ then $\mathbf{Auto}(\mathcal{L})$ has an initial object $\mathcal{A}^{\text{init}}(\mathcal{L})$ with $\mathcal{A}^{\text{init}}(\mathcal{L})(\mathbf{st}) = \coprod_{A^*} \mathcal{L}(\mathbf{in})$;

* dually if $\mathcal{C}$ has all countable powers of $\mathcal{L}(\mathbf{out})$ then $\mathbf{Auto}(\mathcal{L})$ has a final object $\mathcal{A}^{\text{final}}(\mathcal{L})$ with $\mathcal{A}^{\text{final}}(\mathcal{L})(\mathbf{st}) = \prod_{A^*} \mathcal{L}(\mathbf{out})$;

* hence when both of the previous items hold and $\mathcal{C}$ is equipped with a factorization system $(\mathcal{E}, \mathcal{M})$, $\mathbf{Auto}(\mathcal{L})$ has an $(\mathcal{E}, \mathcal{M})$-minimal object $\text{Min} \, \mathcal{L}$.

This is summarized by the diagram below, where $\kappa$ and $\pi$ are the canonical inclusion and projections.

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

We now have all the ingredients to define algorithms for computing the minimal automaton recognizing a language. But since we will also want to prove the termination of these algorithms, we need an additional notion of finiteness.

**Definition 2.13** $(\mathcal{E}$-artinian and $\mathcal{M}$-noetherian objects [10, Definition 24]). In a category $\mathcal{C}$ equipped with a factorization system $(\mathcal{E}, \mathcal{M})$, an object $X$ is said to be $\mathcal{M}$-noetherian if every strict chain of $\mathcal{M}$-subobjects is finite: if $(x_n : X_n \to X)_{n \in \mathbb{N}}$ and $(m_n : X_n \to X_{n+1})$ form the commutative diagram

<figure><img src="image_8.png" /></figure>
then only finitely many of the $m_n$'s may not be isomorphisms. Dually, $X$ is $\mathcal{E}$-artinian if $X^{\text{op}}$ is $\mathcal{E}^{\text{op}}$-noetherian in $\mathcal{C}^{\text{op}}$, that is if every strict cochain of $\mathcal{E}$-quotients of $X$ is finite.

While Colcombet, Petrişan and Stabile do not give complexity results for their algorithm, it is straightforward to do so, hence we extend their definition so that it also measures the size of an object in $\mathcal{C}$.

**Definition 2.14 (co-$\mathcal{E}$- and $\mathcal{M}$-length).** For a fixed $x_0 : X_0 \to X$, we call $\mathcal{M}$-length of $x_0$, written length$_{\mathcal{M}} x_0$, the (possibly infinite) supremum of the length (the number of pairs of consecutive subobjects) of strict chains of $\mathcal{M}$-subobjects of $X$ that start with $x_0$. Dually, we call co-$\mathcal{E}$-length of an $\mathcal{E}$-quotient $x_0 : X \to X_0$ the (possibly infinite) quantity colength$_{\mathcal{E}} x_0 = \text{length}_{\mathcal{E}^{\text{op}}} x_0^{\text{op}}$.

**Example 2.15.** In Set, $X$ is finite if and only if it is Inj-noetherian iff it is Surj-artinian, and in that case for $Y \subseteq X$ we have colength$_{\text{Surj}}(X \to Y) = \text{length}_{\text{Inj}}(Y \to X) = |X - Y|$. Similarly, in $\mathbb{K}\text{Vec } X$ has finite dimension if and only if it is Inj-noetherian iff it is Surj-artinian, and in that case for $Y \subseteq X$ we have colength$_{\text{Surj}}(X \to Y) = \text{length}_{\text{Inj}}(Y \to X) = \dim X - \dim Y$.

Note that the co-$\mathcal{E}$- and $\mathcal{M}$-lengths need not be equal: see for instance the factorization system we define for monoidal transducers in Section 4.4, for which the co-$\mathcal{E}$- and $\mathcal{M}$-length are computed in Lemmas 5.1 and 5.2.

## 2.3. Learning

In this section, we fix a language $\mathcal{L} : \mathcal{O} \to \mathcal{C}$ and a factorization system $(\mathcal{E}, \mathcal{M})$ of $\mathcal{C}$ that extends to Auto($\mathcal{L}$), and we assume that $\mathcal{C}$ has countable copowers of $\mathcal{L}(\text{in})$ and countable powers of $\mathcal{L}(\text{out})$ so that Theorem 2.12 applies.

Our goal is to compute Min $\mathcal{L}$ with the help of two oracles: EVAL$_{\mathcal{L}}$, when queried with a word $w \in A^*$, outputs $\mathcal{L}(\vdash w \triangleleft)$; while EQUIV$_{\mathcal{L}}$, when queried with a $(\mathcal{C}, \mathcal{L}(\text{in}), \mathcal{L}(\text{out}))$-automaton $\mathcal{A}$, decides whether $\mathcal{A}$ recognizes $\mathcal{L}$, and, if not, outputs a counter-example $w \in A^*$ such that $\mathcal{L}(\vdash w \triangleleft) \neq (\mathcal{A} \circ \iota)(\vdash w \triangleleft)$.

For (Set, 1, 2)-automata, if the language is regular this problem is solved using Angluin's L\* algorithm [1]. It works by maintaining a set of prefixes $Q$ and of suffixes $T$ and, using EVAL$_{\mathcal{L}}$, incrementally building a table $L : Q \times (A \cup \{\epsilon\}) \times T \to 2$ that represents partial knowledge of $\mathcal{L}$ until it can be made into a (minimal) automaton. This automaton is then submitted to EQUIV$_{\mathcal{L}}$: if it is accepted it must be Min $\mathcal{L}$, otherwise the counter-example is added to $Q$ and the algorithm loops over. The FUNL\* algorithm (Algorithm 1) generalizes this to arbitrary $(\mathcal{C}, \mathcal{L}(\text{in}), \mathcal{L}(\text{out}))$, and in particular also encompasses Vilar's algorithm for learning (non-monoidal) transducers which was described in Section 1 [10].

Instead of maintaining a table, it maintains a biautomaton: if $Q \subseteq A^*$ is prefix-closed ($wa \in Q \Rightarrow w \in Q$) and $T \subseteq A^*$ is suffix-closed ($aw \in T \Rightarrow w \in T$), a $(Q, T)$-biautomaton is, similarly to an automaton, a functor $\mathcal{A} : \mathcal{I}_{Q,T} \to \mathcal{C}$, where $\mathcal{I}_{Q,T}$ is now the category freely generated by the diagram

$$ \text{in} \xrightarrow{\Delta q} \text{st}_1 \xrightarrow[\epsilon]{a} \text{st}_2 \xrightarrow{t \triangleleft} \text{out} $$
then only finitely many of the $m_n$'s may not be isomorphisms. Dually, $X$ is $\mathcal{E}$-artinian if $X^{\text{op}}$ is $\mathcal{E}^{\text{op}}$-noetherian in $\mathcal{C}^{\text{op}}$, that is if every strict cochain of $\mathcal{E}$-quotients of $X$ is finite.

While Colcombet, Petrişan and Stabile do not give complexity results for their algorithm, it is straightforward to do so, hence we extend their definition so that it also measures the size of an object in $\mathcal{C}$.

**Definition 2.14 (co-$\mathcal{E}$- and $\mathcal{M}$-length).** For a fixed $x_0 : X_0 \to X$, we call $\mathcal{M}$-length of $x_0$, written length$_{\mathcal{M}} x_0$, the (possibly infinite) supremum of the length (the number of pairs of consecutive subobjects) of strict chains of $\mathcal{M}$-subobjects of $X$ that start with $x_0$. Dually, we call co-$\mathcal{E}$-length of an $\mathcal{E}$-quotient $x_0 : X \to X_0$ the (possibly infinite) quantity colength$_{\mathcal{E}} x_0 = \text{length}_{\mathcal{E}^{\text{op}}} x_0^{\text{op}}$.

**Example 2.15.** In Set, $X$ is finite if and only if it is Inj-noetherian iff it is Surj-artinian, and in that case for $Y \subseteq X$ we have colength$_{\text{Surj}}(X \to Y) = \text{length}_{\text{Inj}}(Y \to X) = |X - Y|$. Similarly, in $\mathbb{K}\text{Vec } X$ has finite dimension if and only if it is Inj-noetherian iff it is Surj-artinian, and in that case for $Y \subseteq X$ we have colength$_{\text{Surj}}(X \to Y) = \text{length}_{\text{Inj}}(Y \to X) = \dim X - \dim Y$.

Note that the co-$\mathcal{E}$- and $\mathcal{M}$-lengths need not be equal: see for instance the factorization system we define for monoidal transducers in Section 4.4, for which the co-$\mathcal{E}$- and $\mathcal{M}$-length are computed in Lemmas 5.1 and 5.2.

## 2.3. Learning

In this section, we fix a language $\mathcal{L} : \mathcal{O} \to \mathcal{C}$ and a factorization system $(\mathcal{E}, \mathcal{M})$ of $\mathcal{C}$ that extends to Auto($\mathcal{L}$), and we assume that $\mathcal{C}$ has countable copowers of $\mathcal{L}(\text{in})$ and countable powers of $\mathcal{L}(\text{out})$ so that Theorem 2.12 applies.

Our goal is to compute Min $\mathcal{L}$ with the help of two oracles: EVAL$_{\mathcal{L}}$, when queried with a word $w \in A^*$, outputs $\mathcal{L}(\vdash w \triangleleft)$; while EQUIV$_{\mathcal{L}}$, when queried with a $(\mathcal{C}, \mathcal{L}(\text{in}), \mathcal{L}(\text{out}))$-automaton $\mathcal{A}$, decides whether $\mathcal{A}$ recognizes $\mathcal{L}$, and, if not, outputs a counter-example $w \in A^*$ such that $\mathcal{L}(\vdash w \triangleleft) \neq (\mathcal{A} \circ \iota)(\vdash w \triangleleft)$.

For (Set, 1, 2)-automata, if the language is regular this problem is solved using Angluin's L\* algorithm [1]. It works by maintaining a set of prefixes $Q$ and of suffixes $T$ and, using EVAL$_{\mathcal{L}}$, incrementally building a table $L : Q \times (A \cup \{\epsilon\}) \times T \to 2$ that represents partial knowledge of $\mathcal{L}$ until it can be made into a (minimal) automaton. This automaton is then submitted to EQUIV$_{\mathcal{L}}$: if it is accepted it must be Min $\mathcal{L}$, otherwise the counter-example is added to $Q$ and the algorithm loops over. The FUNL\* algorithm (Algorithm 1) generalizes this to arbitrary $(\mathcal{C}, \mathcal{L}(\text{in}), \mathcal{L}(\text{out}))$, and in particular also encompasses Vilar's algorithm for learning (non-monoidal) transducers which was described in Section 1 [10].

Instead of maintaining a table, it maintains a biautomaton: if $Q \subseteq A^*$ is prefix-closed ($wa \in Q \Rightarrow w \in Q$) and $T \subseteq A^*$ is suffix-closed ($aw \in T \Rightarrow w \in T$), a $(Q, T)$-biautomaton is, similarly to an automaton, a functor $\mathcal{A} : \mathcal{I}_{Q,T} \to \mathcal{C}$, where $\mathcal{I}_{Q,T}$ is now the category freely generated by the diagram

$$ \text{in} \xrightarrow{\Delta q} \text{st}_1 \xrightarrow[\epsilon]{a} \text{st}_2 \xrightarrow{t \triangleleft} \text{out} $$
where $a, q$ and $t$ respectively range in $A$, $Q$ and $T$, and where we also require the diagrams below to commute, the left one whenever $qa \in QA$ and the right one whenever $at \in AT$.

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

A $(Q, T)$-biautomaton may thus process a prefix in $Q$ and get in a state in $\mathcal{A}(\mathbf{st}_1)$, follow a transition along $A \cup \{\epsilon\}$ to go in $\mathcal{A}(\mathbf{st}_2)$, and output a value for each suffix in $T$. The category of biautomata recognizing $\mathcal{L}_{Q,T}$ ($\mathcal{L}$ restricted to words in $QT \cup QAT$) is written $\mathbf{Auto}_{Q,T}(\mathcal{L})$. A result similar to Theorem 2.12 also holds for biautomata [10, Lemma 18], and the initial and final biautomata are then made of finite copowers of $\mathcal{L}(\mathbf{in})$ and finite powers of $\mathcal{L}(\mathbf{out})$ (when these exist). Writing $Q/T$ for the $(\mathcal{E}, \mathcal{M})$-factorization of the canonical morphism $\langle [\mathcal{L}(\triangleright qt\triangle)]_{q \in Q} \rangle_{t \in T} : \coprod_Q \mathcal{L}(\mathbf{in}) \to \coprod_T \mathcal{L}(\mathbf{out})$, the minimal biautomaton recognizing $\mathcal{L}_{Q,T}$ then has state-spaces $(\mathrm{Min} \, \mathcal{L}_{Q,T})(\mathbf{st}_1) = Q/(T \cup AT)$ and $(\mathrm{Min} \, \mathcal{L}_{Q,T})(\mathbf{st}_2) = (Q \cup QA)/T$. The table, represented by the morphism $\langle [\mathcal{L}(\triangleright qt\triangle)]_{q \in Q} \rangle_{t \in T}$, may be fully computed using $\mathrm{EVAL}_{\mathcal{L}}$, and hence so can be the minimal $(Q, T)$-biautomaton.

A biautomaton $\mathcal{B}$ can then be merged into a hypothesis $(\mathcal{C}, \mathcal{L}(\mathbf{in}), \mathcal{L}(\mathbf{out}))$-automaton precisely when $\mathcal{B}(\epsilon)$ is an isomorphism, i.e. both an $\mathcal{E}$- and an $\mathcal{M}$-morphism: this encompasses respectively the closure and consistency conditions that need to hold in the $L^*$-algorithm and its variants for the table that is maintained to be merged into a hypothesis automaton.

**Theorem 2.16** ([10, Theorem 26]). *Algorithm 1 is correct. If $(\mathrm{Min} \, \mathcal{L})(\mathbf{st})$ is $\mathcal{M}$-noetherian and $\mathcal{E}$-artinian, the algorithm also terminates.*

While Colcombet, Petrişan and Stabile do not give a bound on the actual running time of their algorithm, it would be straightforward to extend their proof to show that the number of updates to $Q$ and $T$ (hence in particular of calls to $\mathrm{EQUIV}_{\mathcal{L}}$) is linear in the size of $(\mathrm{Min} \, \mathcal{L})(\mathbf{st})$ (itself defined through Definition 2.14).

### 3. An algorithm for minimizing $(C, X, Y)$-automata

We now fix a $(C, X, Y)$-language $\mathcal{L}$ and a factorization system $(\mathcal{E}, \mathcal{M})$ of $C$, and assume that $C$ has all the countable powers of $\mathcal{L}(\mathbf{in})$ and all the countable powers of $\mathcal{L}(\mathbf{out})$ so that Theorem 2.12 applies and $\mathbf{Auto}(\mathcal{L})$ has initial and final objects $\mathcal{A}^{\mathrm{init}}$ and $\mathcal{A}^{\mathrm{final}}$.

While Colcombet, Petrişan and Stabile's framework provide a generic algorithm for learning $\mathrm{Min} \, \mathcal{L}$ (which we recalled in Section 2.3), it does not give a minimization algorithm, that is a way to compute $\mathrm{Min} \, \mathcal{L}$ given another automaton $\mathcal{A}$ recognizing $\mathcal{L}$: Proposition 2.10 only hints that $\mathrm{Min} \, \mathcal{L}$ can be computed in two steps, by first computing Reach and then Obs (or conversely).
where $a, q$ and $t$ respectively range in $A, Q$ and $T$, and where we also require the diagrams below to commute, the left one whenever $qa \in QA$ and the right one whenever $at \in AT$.

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

A $(Q, T)$-biautomaton may thus process a prefix in $Q$ and get in a state in $\mathcal{A}(\mathbf{st}_1)$, follow a transition along $A \cup \{\epsilon\}$ to go in $\mathcal{A}(\mathbf{st}_2)$, and output a value for each suffix in $T$. The category of biautomata recognizing $\mathcal{L}_{Q,T}$ ($\mathcal{L}$ restricted to words in $QT \cup QAT$) is written $\mathbf{Auto}_{Q,T}(\mathcal{L})$. A result similar to Theorem 2.12 also holds for biautomata [10, Lemma 18], and the initial and final biautomata are then made of finite copowers of $\mathcal{L}(\mathbf{in})$ and finite powers of $\mathcal{L}(\mathbf{out})$ (when these exist). Writing $Q/T$ for the $(\mathcal{E}, \mathcal{M})$-factorization of the canonical morphism $\langle[\mathcal{L}(\triangleright qt\triangle)]_{q \in Q}\rangle_{t \in T} : \coprod_Q \mathcal{L}(\mathbf{in}) \to \coprod_T \mathcal{L}(\mathbf{out})$, the minimal biautomaton recognizing $\mathcal{L}_{Q,T}$ then has state-spaces $(\mathrm{Min} \, \mathcal{L}_{Q,T})(\mathbf{st}_1) = Q/(T \cup AT)$ and $(\mathrm{Min} \, \mathcal{L}_{Q,T})(\mathbf{st}_2) = (Q \cup QA)/T$. The table, represented by the morphism $\langle[\mathcal{L}(\triangleright qt\triangle)]_{q \in Q}\rangle_{t \in T}$, may be fully computed using $\mathrm{EVAL}_{\mathcal{L}}$, and hence so can be the minimal $(Q, T)$-biautomaton.

A biautomaton $\mathcal{B}$ can then be merged into a hypothesis $(\mathcal{C}, \mathcal{L}(\mathbf{in}), \mathcal{L}(\mathbf{out}))$-automaton precisely when $\mathcal{B}(\epsilon)$ is an isomorphism, i.e. both an $\mathcal{E}$- and an $\mathcal{M}$-morphism: this encompasses respectively the closure and consistency conditions that need to hold in the $L^*$-algorithm and its variants for the table that is maintained to be merged into a hypothesis automaton.

**Theorem 2.16** ([10, Theorem 26]). *Algorithm 1 is correct. If $(\mathrm{Min} \, \mathcal{L})(\mathbf{st})$ is $\mathcal{M}$-noetherian and $\mathcal{E}$-artinian, the algorithm also terminates.*

While Colcombet, Petrişan and Stabile do not give a bound on the actual running time of their algorithm, it would be straightforward to extend their proof to show that the number of updates to $Q$ and $T$ (hence in particular of calls to $\mathrm{EQUIV}_{\mathcal{L}}$) is linear in the size of $(\mathrm{Min} \, \mathcal{L})(\mathbf{st})$ (itself defined through Definition 2.14).

### 3. An algorithm for minimizing $(C, X, Y)$-automata

We now fix a $(C, X, Y)$-language $\mathcal{L}$ and a factorization system $(\mathcal{E}, \mathcal{M})$ of $C$, and assume that $C$ has all the countable powers of $\mathcal{L}(\mathbf{in})$ and all the countable powers of $\mathcal{L}(\mathbf{out})$ so that Theorem 2.12 applies and $\mathbf{Auto}(\mathcal{L})$ has initial and final objects $\mathcal{A}^{\mathrm{init}}$ and $\mathcal{A}^{\mathrm{final}}$.

While Colcombet, Petrişan and Stabile's framework provide a generic algorithm for learning $\mathrm{Min} \, \mathcal{L}$ (which we recalled in Section 2.3), it does not give a minimization algorithm, that is a way to compute $\mathrm{Min} \, \mathcal{L}$ given another automaton $\mathcal{A}$ recognizing $\mathcal{L}$: Proposition 2.10 only hints that $\mathrm{Min} \, \mathcal{L}$ can be computed in two steps, by first computing Reach and then Obs (or conversely).
**Algorithm 1** The FUNL*-algorithm

**Input:** EVAL<sub>L</sub> and EQUIV<sub>L</sub>

**Output:** Min(<sub>L</sub>)

1: $Q = T = \{\epsilon\}$

2: loop

3: while $\epsilon_{Q,T}^{min}$ is not an isomorphism do

4: if $\epsilon_{Q,T}^{min}$ is not an $\mathcal{E}$-morphism then

5: find $qa \in QA$ such that $Q/T \to (Q \cup \{qa\})/T$ is not an $\mathcal{E}$-morphism

6: add $qa$ to $Q$

7: else if $\epsilon_{Q,T}^{min}$ is not an $\mathcal{M}$-morphism then

8: find $at \in AT$ such that $Q/(T \cup \{at\}) \to Q/T$ is not an $\mathcal{M}$-morphism

9: add $at$ to $T$

10: end if

11: end while

12: merge Min $\mathcal{L}_{Q,T}$ into $\mathcal{H}_{Q,T}\mathcal{L}$

13: if EQUIV<sub>L</sub>($\mathcal{H}_{Q,T}\mathcal{L}$) outputs some counter-example $w$ then

14: add $w$ and its prefixes to $Q$

15: else

16: return $\mathcal{H}_{Q,T}\mathcal{L}$

17: end if

18: end loop

In this section we thus describe such an algorithm, and reuse the notations and arguments they used for their learning algorithm, making some of their key lemmas more explicit in our proofs. In Section 3.1 we give a basic version of the algorithm that does not require any more assumptions than those of the framework of Section 2. In Section 3.2 we show how it can be further detailed given some additional assumptions on the output category and the factorization system. Finally, in Section 3.3 we show how our algorithm precisely encompasses several well-known algorithms for minimizing different kinds of automata.

## 3.1. The basic algorithm

Let thus $\mathcal{A}$ be a $(C, X, Y)$-automaton recognizing $\mathcal{L}$. Since $\mathcal{I}$ is self-dual, this automaton is entirely described by the dual $(C^{\text{op}}, X^{\text{op}}, Y^{\text{op}})$-automaton $\mathcal{A}^{\text{op}} : \mathcal{I} \to \mathcal{C}^{\text{op}}$. But $(\mathcal{M}^{\text{op}}, \mathcal{E}^{\text{op}})$ is a factorization system in $\mathcal{C}^{\text{op}}$ and the dual of the initial object in $\mathcal{C}$ is the final object in $\mathcal{C}^{\text{op}}$, hence

**Lemma 3.1** ([23, Remark 2.5]). The dual of the $(\mathcal{E}, \mathcal{M})$-factorization Obs $\mathcal{A}$ in Auto($\mathcal{L}$) is the $(\mathcal{M}^{\text{op}}, \mathcal{E}^{\text{op}})$-factorization Reach $\mathcal{A}^{\text{op}}$ in Auto($\mathcal{L}^{\text{op}}$).

**Remark 3.2.** Note that Lemma 3.1 does not mean that, for a fixed category $\mathcal{C}$ along with a factorization system $(\mathcal{E}, \mathcal{M})$ and the two objects $X$ and $Y$, having an algorithm that computes the $(\mathcal{E}, \mathcal{M})$-factorization Reach for $(\mathcal{C}, X, Y)$-automata is equivalent to
**Algorithm 1** The FUNL*-algorithm

**Input:** EVAL<sub>L</sub> and EQUIV<sub>L</sub>

**Output:** Min(<sub>L</sub>)

1: $Q = T = \{\epsilon\}$

2: loop

3: while $\epsilon_{Q,T}^{min}$ is not an isomorphism **do**

4: if $\epsilon_{Q,T}^{min}$ is not an $\mathcal{E}$-morphism **then**

5: find $qa \in QA$ such that $Q/T \to (Q \cup \{qa\})/T$ is not an $\mathcal{E}$-morphism

6: add $qa$ to $Q$

7: else if $\epsilon_{Q,T}^{min}$ is not an $\mathcal{M}$-morphism **then**

8: find $at \in AT$ such that $Q/(T \cup \{at\}) \to Q/T$ is not an $\mathcal{M}$-morphism

9: add $at$ to $T$

10: end if

11: end while

12: merge Min $\mathcal{L}_{Q,T}$ into $\mathcal{H}_{Q,T}\mathcal{L}$

13: if EQUIV<sub>L</sub>(*H*<sub>Q,T</sub>*L*) outputs some counter-example *w* then

14: add *w* and its prefixes to *Q*

15: else

16: return $\mathcal{H}_{Q,T}\mathcal{L}$

17: end if

18: end loop

In this section we thus describe such an algorithm, and reuse the notations and arguments they used for their learning algorithm, making some of their key lemmas more explicit in our proofs. In Section 3.1 we give a basic version of the algorithm that does not require any more assumptions than those of the framework of Section 2. In Section 3.2 we show how it can be further detailed given some additional assumptions on the output category and the factorization system. Finally, in Section 3.3 we show how our algorithm precisely encompasses several well-known algorithms for minimizing different kinds of automata.

**3.1. The basic algorithm**

Let thus $\mathcal{A}$ be a ($\mathcal{C}$, $X$, $Y$)-automaton recognizing $\mathcal{L}$. Since $\mathcal{I}$ is self-dual, this automaton is entirely described by the dual ($\mathcal{C}^{\text{op}}$, $X^{\text{op}}$, $Y^{\text{op}}$)-automaton $\mathcal{A}^{\text{op}}: \mathcal{I} \to \mathcal{C}^{\text{op}}$. But ($\mathcal{M}^{\text{op}}$, $\mathcal{E}^{\text{op}}$) is a factorization system in $\mathcal{C}^{\text{op}}$ and the dual of the initial object in $\mathcal{C}$ is the final object in $\mathcal{C}^{\text{op}}$, hence

**Lemma 3.1** ([23, Remark 2.5]). The dual of the ($\mathcal{E}$, $\mathcal{M}$)-factorization Obs $\mathcal{A}$ in Auto($\mathcal{L}$) is the ($\mathcal{M}^{\text{op}}$, $\mathcal{E}^{\text{op}}$)-factorization Reach $\mathcal{A}^{\text{op}}$ in Auto($\mathcal{L}^{\text{op}}$).

*Remark 3.2.* Note that Lemma 3.1 does not mean that, for a fixed category $\mathcal{C}$ along with a factorization system ($\mathcal{E}$, $\mathcal{M}$) and the two objects $X$ and $Y$, having an algorithm that computes the ($\mathcal{E}$, $\mathcal{M}$)-factorization Reach for ($\mathcal{C}$, $X$, $Y$)-automata is equivalent to
having one that computes the ($\mathcal{E}$, $\mathcal{M}$)-factorization Obs for ($\mathcal{C}$, $X$, $Y$)-automata as well. Indeed, $\mathcal{C}^{\text{op}}$ and $\mathcal{C}$ itself may differ greatly, and even if $\mathcal{C}$ were self-dual (hence $\mathcal{C} = \mathcal{C}^{\text{op}}$), $\mathcal{E}$ and $\mathcal{M}^{\text{op}}$ or $X$ and $Y^{\text{op}}$ could still differ, meaning that computing the ($\mathcal{E}$, $\mathcal{M}$)- and ($\mathcal{M}^{\text{op}}$, $\mathcal{E}^{\text{op}}$)-factorizations would not necessarily be equivalent. For instance, **Rel** is self-dual but, as Example 3.13 shows, Reach $\mathcal{A}$ may be computed for automata $\mathcal{A}: \mathcal{I} \to \mathbf{Rel}$ while Obs $\mathcal{A}$ may not.

What this result says however is that getting a *generic* algorithm that computes Obs (one that is parametric in $\mathcal{C}$) is thus equivalent to getting one that computes Reach: we focus on the latter.

**Definition 3.3.** Given a set $Q \subseteq A^*$, write $e_Q: \coprod_Q \mathcal{L}(\mathbf{in}) \to Q/\mathcal{A}(\mathbf{st})$ and $m_Q: Q/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ for the factorization of the arrow $[\mathcal{A}(\triangleright q)]_{q \in Q}: \coprod_Q \mathcal{L}(\mathbf{in}) \to \mathcal{A}(\mathbf{st})$ in $\mathcal{C}$.

Notice how for $Q = A^*$ we get by Theorem 2.12 that $A^*/\mathcal{A}(\mathbf{st}) = (\text{Reach } \mathcal{A})(\mathbf{st})$, which is exactly the object we want to compute (along with its embedding into $\mathcal{A}(\mathbf{st})$, given by $m_{A^*}$). But we also want to compute the transition arrows on this object:

**Lemma 3.4.** (similar to [10, Lemma 31]) For any $w \in A^*$ and $Q' \subseteq A^*$ such that $Qw = \{qw \mid q \in Q\} \subseteq Q'$, there is a unique morphism $\kappa_{Q'w}^{Q'}/\mathcal{A}(w) : Q/\mathcal{A}(\mathbf{st}) \to Q'/\mathcal{A}(\mathbf{st})$ making the two squares in the diagram below commute. Moreover, if $uv = w$ and $Qw \subseteq Q'v \subseteq Q''$, then $\kappa_{Q'v}^{Q''}/\mathcal{A}(v) \circ \kappa_{Q'u}^{Q'}/\mathcal{A}(u) = \kappa_{Q'w}^{Q''}/\mathcal{A}(w)$.

$$ \begin{array}{ccc} \coprod_{Q'} \mathcal{L}(\mathbf{in}) & \xrightarrow{e_{Q'}} & Q'/\mathcal{A}(\mathbf{st}) \xrightarrow{m_{Q'}} \mathcal{A}(\mathbf{st}) \\ \kappa_{Q'w}^{Q'} = \coprod_{q \in Q} \kappa_q w & \xrightarrow{\kappa_{Q'w}^{Q'}/\mathcal{A}(w)} & \mathcal{A}(w) \\ \coprod_Q \mathcal{L}(\mathbf{in}) & \xrightarrow{e_Q} & Q/\mathcal{A}(\mathbf{st}) \xrightarrow{m_Q} \mathcal{A}(\mathbf{st}) \end{array} $$

We fix the notation $\kappa_{Q'w}^{Q'}/\mathcal{A}(w)$ for the canonical morphisms of Lemma 3.4, and simply write $\kappa_Q^{Q'}/\mathcal{A}(\mathbf{st}) = \kappa_{Q'\epsilon}^{Q'}/\mathcal{A}(\epsilon)$ when $w$ is the empty word. In particular, we have that $(\text{Reach } \mathcal{A})(a) = \kappa_{A^*\cdot a}^{A^*}/\mathcal{A}(a)$.

Of course, we can't just compute $A^*/\mathcal{A}(\mathbf{st})$ and its associated morphisms as a factorization of the morphism from $\coprod_{A^*} \mathcal{A}(\mathbf{in})$, as this coproduct is infinite: in **Set** with $\mathcal{A}(\mathbf{in}) = 1$, it corresponds to the set $A^*$ itself. Instead our strategy will be to find some finite subset $Q$ that describes Reach $\mathcal{A}$ entirely, i.e. such that we have an isomorphism $\kappa_Q^{A^*}/\mathcal{A}(\mathbf{st}) : Q/\mathcal{A}(\mathbf{st}) \cong A^*/\mathcal{A}(\mathbf{st})$: for classical automata this isomorphism means exactly that the $Q$-reachable states — those that are reachable from the initial state by following transitions corresponding to words in $Q$ — are precisely the reachable states.

Informally, to find such a subset we start with $Q = \emptyset$ and add words to it until the $\kappa_Q^{Q \cup \{qa\}}/\mathcal{A}(\mathbf{st})$ are isomorphisms for all $q \in Q$ and $a \in A$: in **Set** this means following the transitions until we cannot reach an unvisited state from a state we have previously
having one that computes the ($\mathcal{E}$, $\mathcal{M}$)-factorization Obs for ($\mathcal{C}$, $X$, $Y$)-automata as well. Indeed, $\mathcal{C}^{\text{op}}$ and $\mathcal{C}$ itself may differ greatly, and even if $\mathcal{C}$ were self-dual (hence $\mathcal{C} = \mathcal{C}^{\text{op}}$), $\mathcal{E}$ and $\mathcal{M}^{\text{op}}$ or $X$ and $Y^{\text{op}}$ could still differ, meaning that computing the ($\mathcal{E}$, $\mathcal{M}$)- and ($\mathcal{M}^{\text{op}}$, $\mathcal{E}^{\text{op}}$)-factorizations would not necessarily be equivalent. For instance, **Rel** is self-dual but, as Example 3.13 shows, Reach $\mathcal{A}$ may be computed for automata $\mathcal{A}: \mathcal{I} \to \mathbf{Rel}$ while Obs $\mathcal{A}$ may not.

What this result says however is that getting a *generic* algorithm that computes Obs (one that is parametric in $\mathcal{C}$) is thus equivalent to getting one that computes Reach: we focus on the latter.

**Definition 3.3.** Given a set $Q \subseteq A^*$, write $e_Q: \coprod_Q \mathcal{L}(\mathbf{in}) \to Q/\mathcal{A}(\mathbf{st})$ and $m_Q: Q/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ for the factorization of the arrow $[\mathcal{A}(\triangleright q)]_{q \in Q}: \coprod_Q \mathcal{L}(\mathbf{in}) \to \mathcal{A}(\mathbf{st})$ in $\mathcal{C}$.

Notice how for $Q = A^*$ we get by Theorem 2.12 that $A^*/\mathcal{A}(\mathbf{st}) = (\text{Reach } \mathcal{A})(\mathbf{st})$, which is exactly the object we want to compute (along with its embedding into $\mathcal{A}(\mathbf{st})$, given by $m_{A^*}$). But we also want to compute the transition arrows on this object:

**Lemma 3.4.** (similar to [10, Lemma 31]) For any $w \in A^*$ and $Q' \subseteq A^*$ such that $Qw = \{qw | q \in Q\} \subseteq Q'$, there is a unique morphism $\kappa_{Q'w}^{Q'}/\mathcal{A}(w) : Q/\mathcal{A}(\mathbf{st}) \to Q'/\mathcal{A}(\mathbf{st})$ making the two squares in the diagram below commute. Moreover, if $uv = w$ and $Qw \subseteq Q'v \subseteq Q''$, then $\kappa_{Q'v}^{Q''}/\mathcal{A}(v) \circ \kappa_{Q'u}^{Q'}/\mathcal{A}(u) = \kappa_{Q'w}^{Q''}/\mathcal{A}(w)$.

$$ \begin{array}{ccc} \coprod_{Q'} \mathcal{L}(\mathbf{in}) & \xrightarrow{e_{Q'}} & Q'/\mathcal{A}(\mathbf{st}) \xrightarrow{m_{Q'}} \mathcal{A}(\mathbf{st}) \\ \kappa_{Q'w}^{Q'} = \coprod_{q \in Q} \kappa_q w & \xrightarrow{\kappa_{Q'w}^{Q'}/\mathcal{A}(w)} & \mathcal{A}(w) \\ \coprod_Q \mathcal{L}(\mathbf{in}) & \xrightarrow{e_Q} & Q/\mathcal{A}(\mathbf{st}) \xrightarrow{m_Q} \mathcal{A}(\mathbf{st}) \end{array} $$

We fix the notation $\kappa_{Q'w}^{Q'}/\mathcal{A}(w)$ for the canonical morphisms of Lemma 3.4, and simply write $\kappa_Q^{Q'}/\mathcal{A}(\mathbf{st}) = \kappa_{Q'\epsilon}^{Q'}/\mathcal{A}(\epsilon)$ when $w$ is the empty word. In particular, we have that $(\text{Reach } \mathcal{A})(a) = \kappa_{A^*\cdot a}^{A^*}/\mathcal{A}(a)$.

Of course, we can't just compute $A^*/\mathcal{A}(\mathbf{st})$ and its associated morphisms as a factorization of the morphism from $\coprod_{A^*} \mathcal{A}(\mathbf{in})$, as this coproduct is infinite: in **Set** with $\mathcal{A}(\mathbf{in}) = 1$, it corresponds to the set $A^*$ itself. Instead our strategy will be to find some finite subset $Q$ that describes Reach $\mathcal{A}$ entirely, i.e. such that we have an isomorphism $\kappa_Q^{A^*}/\mathcal{A}(\mathbf{st}) : Q/\mathcal{A}(\mathbf{st}) \cong A^*/\mathcal{A}(\mathbf{st})$: for classical automata this isomorphism means exactly that the $Q$-reachable states — those that are reachable from the initial state by following transitions corresponding to words in $Q$ — are precisely the reachable states.

Informally, to find such a subset we start with $Q = \emptyset$ and add words to it until the $\kappa_Q^{Q \cup \{qa\}}/\mathcal{A}(\mathbf{st})$ are isomorphisms for all $q \in Q$ and $a \in A$: in **Set** this means following the transitions until we cannot reach an unvisited state from a state we have previously
visited. We show that if these morphisms are all isomorphisms then so is $\kappa_Q^{Q \cup QA} / \mathcal{A}(\mathbf{st})$ and then that so is $\kappa_Q^{A^*} / \mathcal{A}(\mathbf{st})$.

Finally, notice that if $Q \subseteq Q'$ then $\kappa_Q^{Q'} / \mathcal{A}(\mathbf{st})$ is already an $\mathcal{M}$-morphism (by [8, Proposition 14.9(1)], because $\mathcal{A}(\epsilon) = \text{id}$ is an $\mathcal{M}$-morphism): in **Set**, the $Q$-reachable states are in particular $Q'$-reachable. Hence to check that $\kappa_Q^{Q \cup \{qa\}} / \mathcal{A}(\mathbf{st})$ is an isomorphism we only really need to check that it is an $\mathcal{E}$-morphism (since $\mathcal{E} \cap \mathcal{M}$ is exactly the class of isomorphisms): in **Set**, that the set of $Q$-reachable states surjects onto the set of $(Q \cup \{qa\})$-reachable states, i.e. that the state reached when following $qa$ is $Q$-reachable and has already been visited.

In practice, this procedure leads to Algorithm 2 where the partition of $A$ on line 6 is always chosen to be the partition into singletons.

<caption>**Algorithm 2** A categorical algorithm for computing Reach</caption>

**Input:** an automaton $\mathcal{A} : \mathcal{I} \to \mathcal{C}$
**Output:** Reach $\mathcal{A}$
1: set $\mathbf{todo} \leftarrow \{\{\epsilon\}\}$
2: set $Q_{\mathbf{done}} \leftarrow \emptyset$
3: **while** there is a $Q \in \mathbf{todo}$
4: &nbsp;&nbsp;&nbsp;&nbsp;remove $Q$ from $\mathbf{todo}$
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\kappa_{Q_{\mathbf{done}}}^{Q_{\mathbf{done}} \cup Q} / \mathcal{A}(\mathbf{st}) : Q_{\mathbf{done}} / \mathcal{A}(\mathbf{st}) \to Q_{\mathbf{done}} \sqcup Q / \mathcal{A}(\mathbf{st})$ is not an $\mathcal{E}$-morphism
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;choose a partition $P$ of $\mathcal{A}$ and set $\mathbf{todo} \leftarrow \mathbf{todo} \sqcup \{Q\tilde{A} | \tilde{A} \in P\}$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;set $Q_{\mathbf{done}} \leftarrow Q_{\mathbf{done}} \sqcup Q$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
10: **end while**
**return** the automaton

*Remark 3.5.* Note that the order in which the elements of the to-do list are treated in Algorithm 2 does not have any impact on the correctness and complexity results. In practice, for some arbitrary $Q \subseteq A^*$ it may also be more efficient to compute $(Q_{\mathbf{done}} \cup Qa) / \mathcal{A}(\mathbf{st})$ in a batch instead of computing each $(Q_{\mathbf{done}} \cup \{qa\}) / \mathcal{A}(\mathbf{st})$ for $q \in Q$ separately: this happens for instance in Example 3.14. Hence why we allow choosing a partition of $A$ on line 6: splitting $A$ into anything coarser than singletons means filling the to-do list with sets of words that contain more than just one word.

**Theorem 3.6.** If $\mathcal{A}(\mathbf{st})$ is $\mathcal{M}$-noetherian, Algorithm 2 is correct, terminates, and the condition on line 5 is satisfied at most length$_{\mathcal{M}}$ $(m_\emptyset : \emptyset / \mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st}))$ times.
visited. We show that if these morphisms are all isomorphisms then so is $\kappa_Q^{Q \cup QA} / \mathcal{A}(\mathbf{st})$ and then that so is $\kappa_Q^{A^*} / \mathcal{A}(\mathbf{st})$.

Finally, notice that if $Q \subseteq Q'$ then $\kappa_Q^{Q'} / \mathcal{A}(\mathbf{st})$ is already an $\mathcal{M}$-morphism (by [8, Proposition 14.9(1)], because $\mathcal{A}(\epsilon) = \text{id}$ is an $\mathcal{M}$-morphism): in **Set**, the $Q$-reachable states are in particular $Q'$-reachable. Hence to check that $\kappa_Q^{Q \cup \{qa\}} / \mathcal{A}(\mathbf{st})$ is an isomorphism we only really need to check that it is an $\mathcal{E}$-morphism (since $\mathcal{E} \cap \mathcal{M}$ is exactly the class of isomorphisms): in **Set**, that the set of $Q$-reachable states surjects onto the set of $(Q \cup \{qa\})$-reachable states, i.e. that the state reached when following $qa$ is $Q$-reachable and has already been visited.

In practice, this procedure leads to Algorithm 2 where the partition of $A$ on line 6 is always chosen to be the partition into singletons.

<caption>**Algorithm 2** A categorical algorithm for computing Reach</caption>

**Input:** an automaton $\mathcal{A} : \mathcal{I} \to \mathcal{C}$
**Output:** Reach $\mathcal{A}$
1: set $\mathbf{todo} \leftarrow \{\{\epsilon\}\}$
2: set $Q_{\mathbf{done}} \leftarrow \emptyset$
3: **while** there is a $Q \in \mathbf{todo}$
4: &nbsp;&nbsp;&nbsp;&nbsp;remove $Q$ from $\mathbf{todo}$
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\kappa_{Q_{\mathbf{done}}}^{Q_{\mathbf{done}} \cup Q} / \mathcal{A}(\mathbf{st}) : Q_{\mathbf{done}} / \mathcal{A}(\mathbf{st}) \to Q_{\mathbf{done}} \sqcup Q / \mathcal{A}(\mathbf{st})$ is not an $\mathcal{E}$-morphism
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;choose a partition $P$ of $\mathcal{A}$ and set $\mathbf{todo} \leftarrow \mathbf{todo} \sqcup \{Q\tilde{A} | \tilde{A} \in P\}$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;set $Q_{\mathbf{done}} \leftarrow Q_{\mathbf{done}} \sqcup Q$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
10: **end while**
**return** the automaton

*Remark 3.5.* Note that the order in which the elements of the to-do list are treated in Algorithm 2 does not have any impact on the correctness and complexity results. In practice, for some arbitrary $Q \subseteq A^*$ it may also be more efficient to compute $(Q_{\mathbf{done}} \cup Qa) / \mathcal{A}(\mathbf{st})$ in a batch instead of computing each $(Q_{\mathbf{done}} \cup \{qa\}) / \mathcal{A}(\mathbf{st})$ for $q \in Q$ separately: this happens for instance in Example 3.14. Hence why we allow choosing a partition of $A$ on line 6: splitting $A$ into anything coarser than singletons means filling the to-do list with sets of words that contain more than just one word.

**Theorem 3.6.** If $\mathcal{A}(\mathbf{st})$ is $\mathcal{M}$-noetherian, Algorithm 2 is correct, terminates, and the condition on line 5 is satisfied at most length$_{\mathcal{M}}$ $(m_\emptyset : \emptyset / \mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st}))$ times.
## 3.2. Computing the factorizations incrementally

A shortcoming of Algorithm 2 is that it does not give us a generic way to compute the intermediate factorizations $Q/\mathcal{A}(\mathbf{st})$ incrementally: in Set, it does not tell us that the set of $(Q \cup \{qa\})$-reachable states can be computed by finding the state reached by following $q$, following an additional $a$-transition, and adding the resulting state to the set of $Q$-reachable states. Fortunately, this can also be expressed categorically, although with an additional assumption on the output category $\mathcal{C}$.

**Lemma 3.7.** For every $Q, Q' \subseteq A^*$, if the coproduct $Q/\mathcal{A}(\mathbf{st}) + Q'/\mathcal{A}(\mathbf{st})$ exists, $[m_Q, m_{Q'}] : Q/\mathcal{A}(\mathbf{st}) + Q'/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ $(\mathcal{E}, \mathcal{M})$-factors into

$$m_{Q \sqcup Q'} \circ \left[ \kappa_Q^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}) , \kappa_{Q'}^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}) \right] : Q/\mathcal{A}(\mathbf{st}) + Q'/\mathcal{A}(\mathbf{st}) \to (Q \sqcup Q')/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$$

**Lemma 3.8.** For every $Q \subseteq A^*$, $\mathcal{A}(a) \circ m_Q (\mathcal{E}, \mathcal{M})$-factors into $m_{Qa} \circ \kappa_{Qa}^{Qa} / \mathcal{A}(\mathbf{st}) : Q/\mathcal{A}(\mathbf{st}) \to Qa/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$.

When the binary coproducts of the $Q/\mathcal{A}(\mathbf{st})$ exist, Algorithm 2 may thus be detailed into Algorithm 3. Notice how instead a keeping track of a set of words we have already considered and a set of words that we have to consider next ($Q_{done}$ and $Q_{todo}$ in Algorithm 2), we now only directly keep track of the subobjects corresponding to these words: $m_{Q_{done}} : Q_{done}/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ is the already-visited subobject of $\mathcal{A}(\mathbf{st})$, while each $(m_Q, \tilde{A})$ in the to-do list corresponds to a subobject $m_Q$ of $\mathcal{A}(\mathbf{st})$ along with a subset of transitions from this subobject that we have to consider next. We also keep track of $e_{Q_{done}} \circ \kappa_\epsilon$, which represents the initial transition into the already-visited subobject $m_{Q_{done}}$.

**Corollary 3.9.** Assume that for every finite $Q, Q' \subseteq A^*$, the coproduct $Q/\mathcal{A}(\mathbf{st}) + Q'/\mathcal{A}(\mathbf{st})$ exists.

Then, if $\mathcal{A}(\mathbf{st})$ is $\mathcal{M}$-noetherian, Algorithm 3 is correct, terminates, and the condition on line 12 is satisfied at most length$_{\mathcal{M}}(m_\epsilon : \{\epsilon\} / \mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st}))$ times.

Algorithm 3 is already much closer than Algorithm 2 to the algorithm that computes the reachable states of a classical automata, but there is still a procedure that could be further detailed: on line 12, Algorithm 3 only asks us to check whether $\kappa_{Q_{done}}^{Q_{done} \sqcup Q \tilde{A}} / \mathcal{A}(\mathbf{st})$ is an $\mathcal{E}$-morphism, that is whether the set of $Q_{done}$-reachable states surjects onto that of $(Q_{done} \sqcup Q \tilde{A})$-reachable states, but it does not tell us that to check this it is enough to just check whether the $Q \tilde{A}$-reachable states had already been visited. Again, this can be expressed categorically with an additional assumption on the factorization system $(\mathcal{E}, \mathcal{M})$.

**Lemma 3.10.** If $\kappa_Q^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}) : Q/\mathcal{A}(\mathbf{st}) \to (Q \sqcup Q')/\mathcal{A}(\mathbf{st})$ is an isomorphism then

$$m_{Q'} = m_Q \circ (\kappa_Q^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}))^{-1} \circ (\kappa_{Q'}^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}))$$
## 3.2. Computing the factorizations incrementally

A shortcoming of Algorithm 2 is that it does not give us a generic way to compute the intermediate factorizations $Q/\mathcal{A}(\mathbf{st})$ incrementally: in Set, it does not tell us that the set of $(Q \cup \{qa\})$-reachable states can be computed by finding the state reached by following $q$, following an additional $a$-transition, and adding the resulting state to the set of $Q$-reachable states. Fortunately, this can also be expressed categorically, although with an additional assumption on the output category $\mathcal{C}$.

**Lemma 3.7.** For every $Q, Q' \subseteq A^*$, if the coproduct $Q/\mathcal{A}(\mathbf{st}) + Q'/\mathcal{A}(\mathbf{st})$ exists, $[m_Q, m_{Q'}] : Q/\mathcal{A}(\mathbf{st}) + Q'/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ $(\mathcal{E}, \mathcal{M})$-factors into

$$m_{Q \sqcup Q'} \circ \left[ \kappa_Q^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}) , \kappa_{Q'}^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}) \right] : Q/\mathcal{A}(\mathbf{st}) + Q'/\mathcal{A}(\mathbf{st}) \to (Q \sqcup Q')/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$$

**Lemma 3.8.** For every $Q \subseteq A^*$, $\mathcal{A}(a) \circ m_Q (\mathcal{E}, \mathcal{M})$-factors into $m_{Qa} \circ \kappa_{Qa}^{Qa} / \mathcal{A}(\mathbf{st}) : Q/\mathcal{A}(\mathbf{st}) \to Qa/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$.

When the binary coproducts of the $Q/\mathcal{A}(\mathbf{st})$ exist, Algorithm 2 may thus be detailed into Algorithm 3. Notice how instead a keeping track of a set of words we have already considered and a set of words that we have to consider next ($Q_{done}$ and $Q_{todo}$ in Algorithm 2), we now only directly keep track of the subobjects corresponding to these words: $m_{Q_{done}} : Q_{done}/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ is the already-visited subobject of $\mathcal{A}(\mathbf{st})$, while each $(m_Q, \tilde{A})$ in the to-do list corresponds to a subobject $m_Q$ of $\mathcal{A}(\mathbf{st})$ along with a subset of transitions from this subobject that we have to consider next. We also keep track of $e_{Q_{done}} \circ \kappa_\epsilon$, which represents the initial transition into the already-visited subobject $m_{Q_{done}}$.

**Corollary 3.9.** Assume that for every finite $Q, Q' \subseteq A^*$, the coproduct $Q/\mathcal{A}(\mathbf{st}) + Q'/\mathcal{A}(\mathbf{st})$ exists.

Then, if $\mathcal{A}(\mathbf{st})$ is $\mathcal{M}$-noetherian, Algorithm 3 is correct, terminates, and the condition on line 12 is satisfied at most length$_M(m_\epsilon : \{\epsilon\} / \mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st}))$ times.

Algorithm 3 is already much closer than Algorithm 2 to the algorithm that computes the reachable states of a classical automata, but there is still a procedure that could be further detailed: on line 12, Algorithm 3 only asks us to check whether $\kappa_{Q_{done}}^{Q_{done} \sqcup Q \tilde{A}} / \mathcal{A}(\mathbf{st})$ is an $\mathcal{E}$-morphism, that is whether the set of $Q_{done}$-reachable states surjects onto that of $(Q_{done} \sqcup Q \tilde{A})$-reachable states, but it does not tell us that to check this it is enough to just check whether the $Q \tilde{A}$-reachable states had already been visited. Again, this can be expressed categorically with an additional assumption on the factorization system $(\mathcal{E}, \mathcal{M})$.

**Lemma 3.10.** If $\kappa_Q^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}) : Q/\mathcal{A}(\mathbf{st}) \to (Q \sqcup Q')/\mathcal{A}(\mathbf{st})$ is an isomorphism then

$$m_{Q'} = m_Q \circ (\kappa_Q^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}))^{-1} \circ (\kappa_{Q'}^{Q \sqcup Q'} / \mathcal{A}(\mathbf{st}))$$
**Algorithm 3** A detailed version of Algorithm 2

**Input:** an automaton $\mathcal{A} : \mathcal{I} \to \mathcal{C}$

**Output:** Reach $\mathcal{A}$

1: compute $e_{\{\epsilon\}} : \mathcal{A}(\mathbf{in}) \to \{\epsilon\}/\mathcal{A}(\mathbf{st})$ and $m_{\{\epsilon\}} : \{\epsilon\}/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$

2: choose a partition $P$ of $\mathcal{A}$ and set $\mathbf{todo} \leftarrow \{(m_\epsilon, \tilde{A}) | \tilde{A} \in P\}$

3: set $m_{Q_{\mathbf{done}}} \leftarrow m_{\{\epsilon\}}$

4: set $e_{Q_{\mathbf{done}}} \circ \kappa_\epsilon \leftarrow e_{\{\epsilon\}}$

5: **while** there is a pair $(m_Q, \tilde{A}) \in \mathbf{todo}$ **do**

6: remove $(m_Q, \tilde{A})$ from $\mathbf{todo}$

7: **for** $a \in \tilde{A}$ **do**

8: compute $m_{Q_a} : Q_a/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ by factoring $\mathcal{A}(a) \circ m_Q$ as in Lemma 3.8

9: **end for**

10: compute $m_{Q\tilde{A}} : Q\tilde{A}/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ by factoring $[m_{Qa}]_{a \in \tilde{A}}$ as in Lemma 3.7

11: compute $\kappa_{Q_{\mathbf{done}}}^{Q_{\mathbf{done}} \sqcup Q\tilde{A}}/\mathcal{A}(\mathbf{st}) : Q_{\mathbf{done}}/\mathcal{A}(\mathbf{st}) \to (Q_{\mathbf{done}} \sqcup Q\tilde{A})/\mathcal{A}(\mathbf{st})$ and
$m_{Q_{\mathbf{done}} \sqcup Q\tilde{A}} : (Q_{\mathbf{done}} \sqcup Q\tilde{A})/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ by factoring $[m_{Q_{\mathbf{done}}}, m_{Q\tilde{A}}]$ as
in Lemma 3.7

12: **if** $\kappa_{Q_{\mathbf{done}}}^{Q_{\mathbf{done}} \sqcup Q\tilde{A}}/\mathcal{A}(\mathbf{st})$ is not an $\mathcal{E}$-morphism **then**

13: choose a partition $P$ of $\mathcal{A}$ and set $\mathbf{todo} \leftarrow \mathbf{todo} \sqcup \{(m_{Q\tilde{A}}, \tilde{A}') | \tilde{A}' \in P\}$

14: set $m_{Q_{\mathbf{done}}} \leftarrow m_{Q \sqcup Q\tilde{A}}$

15: set $e_{Q_{\mathbf{done}}} \circ \kappa_\epsilon \leftarrow \kappa_{Q_{\mathbf{done}}}^{Q_{\mathbf{done}} \sqcup Q\tilde{A}}/\mathcal{A}(\mathbf{st}) \circ e_{Q_{\mathbf{done}}} \circ \kappa_\epsilon : \mathcal{A}(\mathbf{in}) \to (Q \sqcup Q\tilde{A})/\mathcal{A}(\mathbf{st})$

16: **end if**

17: **end while**

18: **return** the automaton

$$ \left( \kappa_{Q_{\text{done}}}^{Q_{\text{done}} \sqcup Q_{\text{done}}^a} / \mathcal{A}(\text{st}) \right)^{-1} \circ \kappa_{Q_{\text{done}}^a}^{Q_{\text{done}} \sqcup Q_{\text{done}}^a} / \mathcal{A}(\text{st}) \circ \kappa_{Q_{\text{done}}^a}^{Q_{\text{done}}^a} / \mathcal{A}(a) \\ \xrightarrow{\bigcirc} \mathcal{A}(\text{in}) \xrightarrow{e_{Q_{\text{done}}} \circ \kappa_{\epsilon}} Q_{\text{done}} / \mathcal{A}(\text{st}) \xrightarrow{\mathcal{A}(\langle \cdot \rangle) \circ m_{Q_{\text{done}}}} \mathcal{A}(\text{out}) $$

with $\kappa_{Q_{\text{done}}^a}^{Q_{\text{done}}^a} / \mathcal{A}(a) : Q_{\text{done}} / \mathcal{A}(\text{st}) \to Q_{\text{done}} / \mathcal{A}(\text{st})$ computed by factoring $\mathcal{A}(a) \circ m_{Q_{\text{done}}}$ as in Lemma 3.8
**Algorithm 3** A detailed version of Algorithm 2

**Input:** an automaton $\mathcal{A} : \mathcal{I} \to \mathcal{C}$

**Output:** Reach $\mathcal{A}$

1: compute $e_{\{\epsilon\}} : \mathcal{A}(\mathbf{in}) \to \{\epsilon\}/\mathcal{A}(\mathbf{st})$ and $m_{\{\epsilon\}} : \{\epsilon\}/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$

2: choose a partition $P$ of $\mathcal{A}$ and set $\mathbf{todo} \leftarrow \{(m_\epsilon, \tilde{A}) | \tilde{A} \in P\}$

3: set $m_{Q_{\mathbf{done}}} \leftarrow m_{\{\epsilon\}}$

4: set $e_{Q_{\mathbf{done}}} \circ \kappa_\epsilon \leftarrow e_{\{\epsilon\}}$

5: **while** there is a pair $(m_Q, \tilde{A}) \in \mathbf{todo}$ **do**

6: remove $(m_Q, \tilde{A})$ from $\mathbf{todo}$

7: **for** $a \in \tilde{A}$ **do**

8: compute $m_{Q_a} : Q_a/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ by factoring $\mathcal{A}(a) \circ m_Q$ as in Lemma 3.8

9: **end for**

10: compute $m_{Q\tilde{A}} : Q\tilde{A}/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ by factoring $[m_{Qa}]_{a \in \tilde{A}}$ as in Lemma 3.7

11: compute $\kappa_{Q_{\mathbf{done}}}^{Q_{\mathbf{done}} \sqcup Q\tilde{A}}/\mathcal{A}(\mathbf{st}) : Q_{\mathbf{done}}/\mathcal{A}(\mathbf{st}) \to (Q_{\mathbf{done}} \sqcup Q\tilde{A})/\mathcal{A}(\mathbf{st})$ and
$m_{Q_{\mathbf{done}} \sqcup Q\tilde{A}} : (Q_{\mathbf{done}} \sqcup Q\tilde{A})/\mathcal{A}(\mathbf{st}) \to \mathcal{A}(\mathbf{st})$ by factoring $[m_{Q_{\mathbf{done}}}, m_{Q\tilde{A}}]$ as
in Lemma 3.7

12: **if** $\kappa_{Q_{\mathbf{done}}}^{Q_{\mathbf{done}} \sqcup Q\tilde{A}}/\mathcal{A}(\mathbf{st})$ is not an $\mathcal{E}$-morphism **then**

13: choose a partition $P$ of $\mathcal{A}$ and set $\mathbf{todo} \leftarrow \mathbf{todo} \sqcup \{(m_{Q\tilde{A}}, \tilde{A}') | \tilde{A}' \in P\}$

14: set $m_{Q_{\mathbf{done}}} \leftarrow m_{Q \sqcup Q\tilde{A}}$

15: set $e_{Q_{\mathbf{done}}} \circ \kappa_\epsilon \leftarrow \kappa_{Q_{\mathbf{done}}}^{Q_{\mathbf{done}} \sqcup Q\tilde{A}}/\mathcal{A}(\mathbf{st}) \circ e_{Q_{\mathbf{done}}} \circ \kappa_\epsilon : \mathcal{A}(\mathbf{in}) \to (Q \sqcup Q\tilde{A})/\mathcal{A}(\mathbf{st})$

16: **end if**

17: **end while**

18: **return** the automaton

$$ \left( \kappa_{Q_{\mathrm{done}}}^{Q_{\mathrm{done}} \sqcup Q_{\mathrm{done}}^a} / \mathcal{A}(\mathrm{st}) \right)^{-1} \circ \kappa_{Q_{\mathrm{done}}^a}^{Q_{\mathrm{done}} \sqcup Q_{\mathrm{done}}^a} / \mathcal{A}(\mathrm{st}) \circ \kappa_{Q_{\mathrm{done}}^a}^{Q_{\mathrm{done}}^a} / \mathcal{A}(a) \\ \xrightarrow{\bigcirc} \mathcal{A}(\mathrm{in}) \xrightarrow{e_{Q_{\mathrm{done}}} \circ \kappa_{\epsilon}} Q_{\mathrm{done}} / \mathcal{A}(\mathrm{st}) \xrightarrow{\mathcal{A}(\Delta) \circ m_{Q_{\mathrm{done}}}} \mathcal{A}(\mathrm{out}) $$

with $\kappa_{Q_{\mathrm{done}}^a}^{Q_{\mathrm{done}}^a} / \mathcal{A}(a) : Q_{\mathrm{done}} / \mathcal{A}(\mathrm{st}) \to Q_{\mathrm{done}} / \mathcal{A}(\mathrm{st})$ computed by factoring $\mathcal{A}(a) \circ m_{Q_{\mathrm{done}}}$ as in Lemma 3.8
Conversely, in the context of Lemma 3.7, assume also that all split epimorphisms are in $\mathcal{E}$ (if $e \circ s = \text{id}$ for some $e, s$ then $e \in \mathcal{E}$). If $m_{Q'}$ factors as $m_Q \circ f$ for some $f : Q/\mathcal{A}(\text{st}) \to (Q \sqcup Q')/\mathcal{A}(\text{st})$ then $\kappa_Q^{Q \sqcup Q'}/\mathcal{A}(\text{st})$ is an isomorphism.

**Corollary 3.11.** When $\mathcal{E}$ contains all split epimorphisms, it is enough to check on line 12 of Algorithm 3 that $m_{Q\tilde{A}} : Q\tilde{A}/\mathcal{A}(\text{st}) \to \mathcal{A}(\text{st})$ doesn't factor through $m_{Q_{\text{done}}} : Q_{\text{done}}/\mathcal{A}(\text{st}) \to \mathcal{A}(\text{st})$. In particular, line 11 can be moved inside the if statement on line 12.

### 3.3. Examples

**Example 3.12 (Graph traversal).** Fix a (Set, 1, 2)-automaton $\mathcal{A}$ with finite state-set. Since Set is cocomplete and $\mathcal{E} = \text{Surj}$ is exactly the class of split epimorphisms (surjections are exactly those functions that have a right-inverse), we may use Algorithm 3 (by Corollary 3.9) with the partitions of $\mathcal{A}$ chosen to be the partition into singletons, along with the optimization of Corollary 3.11: the condition on line 12 is then satisfied at most as many times as there are states in $\mathcal{A}$.

The resulting algorithm is exactly the standard graph traversal algorithm for computing the reachable states of an automaton, as described for instance in in [24, Exercise 1.18]: an $\mathcal{M}$-subobject $m_Q : Q/\mathcal{A}(\text{st}) \to \mathcal{A}(\text{st})$ is indeed a subset of the states of the automaton. The algorithm thus keeps track of a subset of already visited states, $m_{Q_{\text{done}}}$, and a to-do list of states and transitions to consider next (the factorization of a morphism $1 \to \mathcal{A}(\text{st})$ yields a singleton). The algorithm then goes through the to-do list: for a given pair of a state and a transition $(m_{\{q\}}, a)$ that needs to be considered, it computes the successor of the state along the transition (yielding $m_{\{qa\}}$). It then checks whether this new state already belongs to the subset of already visited states by checking whether $m_{\{qa\}}$ factors through $m_{Q_{\text{done}}}$: when this is not the case, $m_{\{qa\}}$ is added to the subset of already visited states as well as to the to-do list, once for every transition. $\kappa_{Q_{\text{done}}\{qa\}}/\mathcal{A}(\text{st})$ is the inclusion of the old subset of already visited states into the new one, and helps us keep track of which state was the initial state. Once the to-do list is empty, the algorithm returns the automaton with set of states the subset of states that were visited, and inherits its initial and final states as well as its transition functions from those of $\mathcal{A}$.

**Example 3.13 (Graph traversal for non-deterministic automata).** As explained in Example 2.11, the factorization system $(\text{Surj}, \text{Det} \cap \text{Inj})$ on Rel described in Example 2.7 does not produce an interesting notion of minimal automata. But while there is indeed no unique way to merge the non-distinguishable states of a non-deterministic automaton, it is still possible to compute its set of reachable states.

This is encompassed by this factorization system: given a (Rel, 1, 1)-automaton $\mathcal{A}$, $\text{Reach}_{(\text{Surj}, \text{Det} \cap \text{Inj})}$ $\mathcal{A}$ is the restriction of $\mathcal{A}$ to its reachable states. Since Rel has arbitrary coproducts, $\text{Reach}\mathcal{A}$ may be computed using Algorithm 3 (by Corollary 3.9) with the partitions of $\mathcal{A}$ chosen to be the partition into singletons, along with the optimization of Corollary 3.11 (as the split epimorphisms in Rel are exactly the graphs of the partial
Conversely, in the context of Lemma 3.7, assume also that all split epimorphisms are in $\mathcal{E}$ (if $e \circ s = \text{id}$ for some $e, s$ then $e \in \mathcal{E}$). If $m_{Q'}$ factors as $m_Q \circ f$ for some $f : Q/\mathcal{A}(\text{st}) \to (Q \sqcup Q')/\mathcal{A}(\text{st})$ then $\kappa_Q^{Q \sqcup Q'}/\mathcal{A}(\text{st})$ is an isomorphism.

**Corollary 3.11.** When $\mathcal{E}$ contains all split epimorphisms, it is enough to check on line 12 of Algorithm 3 that $m_{Q\tilde{A}} : Q\tilde{A}/\mathcal{A}(\text{st}) \to \mathcal{A}(\text{st})$ doesn't factor through $m_{Q_{\text{done}}} : Q_{\text{done}}/\mathcal{A}(\text{st}) \to \mathcal{A}(\text{st})$. In particular, line 11 can be moved inside the if statement on line 12.

### 3.3. Examples

**Example 3.12 (Graph traversal).** Fix a (Set, 1, 2)-automaton $\mathcal{A}$ with finite state-set. Since Set is cocomplete and $\mathcal{E} = \text{Surj}$ is exactly the class of split epimorphisms (surjections are exactly those functions that have a right-inverse), we may use Algorithm 3 (by Corollary 3.9) with the partitions of $\mathcal{A}$ chosen to be the partition into singletons, along with the optimization of Corollary 3.11: the condition on line 12 is then satisfied at most as many times as there are states in $\mathcal{A}$.

The resulting algorithm is exactly the standard graph traversal algorithm for computing the reachable states of an automaton, as described for instance in in [24, Exercise 1.18]: an $\mathcal{M}$-subobject $m_Q : Q/\mathcal{A}(\text{st}) \to \mathcal{A}(\text{st})$ is indeed a subset of the states of the automaton. The algorithm thus keeps track of a subset of already visited states, $m_{Q_{\text{done}}}$, and a to-do list of states and transitions to consider next (the factorization of a morphism $1 \to \mathcal{A}(\text{st})$ yields a singleton). The algorithm then goes through the to-do list: for a given pair of a state and a transition $(m_{\{q\}}, a)$ that needs to be considered, it computes the successor of the state along the transition (yielding $m_{\{qa\}}$). It then checks whether this new state already belongs to the subset of already visited states by checking whether $m_{\{qa\}}$ factors through $m_{Q_{\text{done}}}$: when this is not the case, $m_{\{qa\}}$ is added to the subset of already visited states as well as to the to-do list, once for every transition. $\kappa_{Q_{\text{done}}\{qa\}}/\mathcal{A}(\text{st})$ is the inclusion of the old subset of already visited states into the new one, and helps us keep track of which state was the initial state. Once the to-do list is empty, the algorithm returns the automaton with set of states the subset of states that were visited, and inherits its initial and final states as well as its transition functions from those of $\mathcal{A}$.

**Example 3.13 (Graph traversal for non-deterministic automata).** As explained in Example 2.11, the factorization system $(\text{Surj}, \text{Det} \cap \text{Inj})$ on Rel described in Example 2.7 does not produce an interesting notion of minimal automata. But while there is indeed no unique way to merge the non-distinguishable states of a non-deterministic automaton, it is still possible to compute its set of reachable states.

This is encompassed by this factorization system: given a (Rel, 1, 1)-automaton $\mathcal{A}$, $\text{Reach}_{(\text{Surj}, \text{Det} \cap \text{Inj})}$ $\mathcal{A}$ is the restriction of $\mathcal{A}$ to its reachable states. Since Rel has arbitrary coproducts, $\text{Reach}\mathcal{A}$ may be computed using Algorithm 3 (by Corollary 3.9) with the partitions of $\mathcal{A}$ chosen to be the partition into singletons, along with the optimization of Corollary 3.11 (as the split epimorphisms in Rel are exactly the graphs of the partial
surjective functions, i.e. relations $r \subseteq X \times Y$ for which there is a surjective function $f: X' \to Y$ with codomain some subset $X' \subseteq X$ such that $(x, y) \in r \iff y = f(x)$): the condition on line 12 would then be satisfied at most as many times as there are states in $\mathcal{A}$.

The resulting algorithm is very similar to the one of Example 3.12 for complete deterministic automata, which is also the standard algorithm for computing the reachable states of a non-deterministic automaton. The only difference is that the successors of a state along the transitions labeled by a specific letter are not added as separate subobjects in the to-do list, but only as part of the same subobject. Hence if one of these successors has not been visited yet, the whole subobject of these successors is considered not yet visited: this may bring a lot of redundancy if all the other successors had already been visited.

**Example 3.14 (Moore's algorithm).** Fix a (Set, 1, 2)-automaton $\mathcal{A}$ with finite state-set. Since **Set** is complete and $\mathcal{M} = \text{Inj}$ is exactly the class of split monomorphisms (injections are exactly those functions that have a right-inverse), we may use the dual of Algorithm 3 (by the dual of Corollary 3.9) with the partitions of $\mathcal{A}$ chosen to be the trivial partition $P = \{\mathcal{A}\}$, along with the optimization of Corollary 3.11: the dual of the condition on line 12 is then satisfied at most as many times as there are states in $\mathcal{A}$.

The resulting algorithm is similar to Moore's algorithm [22], a standard algorithm for merging the equivalent states of an automaton: an $\mathcal{E}$-quotient of $e_T : \mathcal{A}(\text{st}) \to T/\mathcal{A}(\text{st})$ is indeed exactly a partition of the states of the automaton into equivalence classes, two states being equivalent if they accept the same subset of words of $T$. The algorithm thus keeps track of two such a partitions $e_{A \le n}$ and $e_{A^n}$, starting with $n = 0$ which just means that the states are split depending on whether they are final or not. $e_{A \le n}$ is the tentative partition that gets refined as $n$ grows and more words are taken into account to distinguish the states, while $e_{A^n}$ is used to compute the next refinement of this tentative partition: computing $e_{aA^n}$ by factoring $e_{A^n} \circ \mathcal{A}(a)$ really means distinguish states when their transitions along the letter $a$ do not fall into the same partition of $e_{A^n}$. Merging the refinements in the tentative partition is then done by computing $e_{A \le n+1}$ through the factorization of $(e_{A \le n}, e_{A^{n+1}})$, which means computing the intersection of every two equivalence class of $e_{A \le n}$ and $e_{A^{n+1}}$ and only keeping those that are not empty. In particular, if $e_{A^{n+1}}$ factors through $e_{A \le n}$ then $e_{A \le n}$ is already a refinement of $e_{A^{n+1}}$ and the algorithm can stop, outputting the automaton with state-set the equivalence classes of $e_{A \le n}$ and initial and final states as well as transition functions inherited from those of $\mathcal{A}$.

Note that the usual presentation of Moore's algorithm would have the next refinement of the tentative partition be computed by pulling $e_{A \le n}$ instead of $e_{A^n}$ along transitions, but the resulting refinement would be the same. Still, this point of view could be probably be accomodated in our framework with a result similar to Lemma 3.7 but with pushouts instead of coproducts.

Hopcroft's algorithm [18], the other standard partition refinement algorithm for merging non-distinguishable states, could on the contrary probably not be accomodated in a very generic way, because it relies heavily on specificities of **Set**, namely that
surjective functions, i.e. relations $r \subseteq X \times Y$ for which there is a surjective function $f: X' \to Y$ with codomain some subset $X' \subseteq X$ such that $(x, y) \in r \iff y = f(x)$): the condition on line 12 would then be satisfied at most as many times as there are states in $\mathcal{A}$.

The resulting algorithm is very similar to the one of Example 3.12 for complete deterministic automata, which is also the standard algorithm for computing the reachable states of a non-deterministic automaton. The only difference is that the successors of a state along the transitions labeled by a specific letter are not added as separate subobjects in the to-do list, but only as part of the same subobject. Hence if one of these successors has not been visited yet, the whole subobject of these successors is considered not yet visited: this may bring a lot of redundancy if all the other successors had already been visited.

**Example 3.14** (Moore's algorithm). Fix a (Set, 1, 2)-automaton $\mathcal{A}$ with finite state-set. Since **Set** is complete and $\mathcal{M} = \text{Inj}$ is exactly the class of split monomorphisms (injections are exactly those functions that have a right-inverse), we may use the dual of Algorithm 3 (by the dual of Corollary 3.9) with the partitions of $\mathcal{A}$ chosen to be the trivial partition $P = \{\mathcal{A}\}$, along with the optimization of Corollary 3.11: the dual of the condition on line 12 is then satisfied at most as many times as there are states in $\mathcal{A}$.

The resulting algorithm is similar to Moore's algorithm [22], a standard algorithm for merging the equivalent states of an automaton: an $\mathcal{E}$-quotient of $e_T : \mathcal{A}(\text{st}) \to T/\mathcal{A}(\text{st})$ is indeed exactly a partition of the states of the automaton into equivalence classes, two states being equivalent if they accept the same subset of words of $T$. The algorithm thus keeps track of two such a partitions $e_{A \le n}$ and $e_{A^n}$, starting with $n = 0$ which just means that the states are split depending on whether they are final or not. $e_{A \le n}$ is the tentative partition that gets refined as $n$ grows and more words are taken into account to distinguish the states, while $e_{A^n}$ is used to compute the next refinement of this tentative partition: computing $e_{aA^n}$ by factoring $e_{A^n} \circ \mathcal{A}(a)$ really means distinguish states when their transitions along the letter $a$ do not fall into the same partition of $e_{A^n}$. Merging the refinements in the tentative partition is then done by computing $e_{A \le n+1}$ through the factorization of $(e_{A \le n}, e_{A^{n+1}})$, which means computing the intersection of every two equivalence class of $e_{A \le n}$ and $e_{A^{n+1}}$ and only keeping those that are not empty. In particular, if $e_{A^{n+1}}$ factors through $e_{A \le n}$ then $e_{A \le n}$ is already a refinement of $e_{A^{n+1}}$ and the algorithm can stop, outputting the automaton with state-set the equivalence classes of $e_{A \le n}$ and initial and final states as well as transition functions inherited from those of $\mathcal{A}$.

Note that the usual presentation of Moore's algorithm would have the next refinement of the tentative partition be computed by pulling $e_{A \le n}$ instead of $e_{A^n}$ along transitions, but the resulting refinement would be the same. Still, this point of view could be probably be accomodated in our framework with a result similar to Lemma 3.7 but with pushouts instead of coproducts.

Hopcroft's algorithm [18], the other standard partition refinement algorithm for merging non-distinguishable states, could on the contrary probably not be accomodated in a very generic way, because it relies heavily on specificities of **Set**, namely that
$\mathcal{A}(\mathit{out}) = 2$ and the possibility to compute cardinals of objects.

**Example 3.15** (Minimization of weighted automata). Given a field $\mathbb{K}$, fix a $(\mathbb{K}\mathit{Vec}, \mathbb{K}, \mathbb{K})$-automaton $\mathcal{A}$ with finite-dimensional state-space. Since $\mathbb{K}\mathit{Vec}$ is cocomplete and $\mathcal{E} = \mathit{Surj}$ is exactly the class of split epimorphisms (linear surjections are exactly those functions that have a right-inverse), we may use Algorithm 3 (by Corollary 3.9) along with the optimization of Corollary 3.11: the condition on line 12 is then satisfied at most dim $\mathcal{A}(\mathit{st})$ times.

The resulting algorithm computes $\mathit{Reach}\,\mathcal{A}$, i.e. an automaton whose configurations are exactly those that are reachable in $\mathcal{A}$: $v \in (\mathit{Reach}\,\mathcal{A})(\mathit{st})$ if and only if there are $\lambda_1, \dots, \lambda_k \in \mathbb{K}$ and $w_1, \dots, w_k \in \mathcal{A}^*$ such that $v = \sum_{i=1}^k \lambda_i \mathcal{A}(\triangleright w)$. An $\mathcal{M}$-subobject of $\mathcal{A}(\mathit{st})$ is a subvector space of $\mathcal{A}(\mathit{st})$ or equivalently a set of independent vectors of $\mathcal{A}(\mathit{st})$. The algorithm thus maintains $m_{Q_{\mathit{done}}} : \mathbb{Q}/\mathcal{A}(\mathit{st}) \to \mathcal{A}(\mathit{st})$, a set of independent vectors of $\mathcal{A}(\mathit{st})$ that form a basis of the vector space of configurations that have already been visited, as well as a to-do list of pairs of a vector $m_{\{q\}} : \{q\}/\mathcal{A}(\mathit{st}) \to \mathcal{A}(\mathit{st})$ (the factorization of a morphism $\mathbb{K} \to \mathcal{A}(\mathit{st})$ has dimension lesser or equal to 1) and a letter $a$ that are to be considered next. When considering $(m_{\{q\}}, a)$, the algorithm first computes the successor vector $m_{\{qa\}}$ along $a$ by applying the matrix $\mathcal{A}(a)$ and then checks whether $m_{\{qa\}}$ factors through $m_{Q_{\mathit{done}}}$ hence solves a linear system to check whether the vector $m_{\{qa\}}$ is a linear combination of those generating $m_{Q_{\mathit{done}}}$. If this is not the case, $(m_{\{qa\}}, a')$ is added to the to-do list for each $a' \in \mathcal{A}$ and $m_{\{qa\}}$ is added to the basis of $m_{Q_{\mathit{done}}}$ to form the basis of $m_{Q_{\mathit{done}} \sqcup \{qa\}}$. Once the to-do list is empty, the algorithm returns the automaton with state-space $Q_{\mathit{done}}/\mathcal{A}(\mathit{st})$ whose initial configuration, transition functions and final values are inherited from those of $\mathcal{A}$ through a change of basis.

Since the algorithm terminates, it only considers finite subsets $Q$ of $\mathcal{A}^*$ and thus only
manipulates finite-dimensional vector spaces. We may therefore as well consider that all
of its computations take place in the category of finite-dimensional vector spaces. But
the functor that sends a vector space to its dual and a linear map to its transpose is
an isomorphism between this category and its dual which sends $\mathbb{K}$ on itself and swaps
$\mathit{Surj}$ and $\mathit{Inj}$. We are thus in the very special case mentioned in Remark 3.2 where the
algorithm that computes the transpose of $\mathit{Obs}\,\mathcal{A}$ is exactly the one that computes $\mathit{Reach}$
as described above, but applied to the transpose of $\mathcal{A}$.

4. The category of monoidal transducers

We now study a specific family of transition systems, monoidal transducers, through the
lens of category theory, so as to be able to apply the framework of Section 2 as well as
the generic minimization algorithm we extended it with in Section 3. In Section 4.1,
we first rapidly recall the notion of monoid. We then define the category of monoidal
transducers recognizing a function in Section 4.2, and study how it fits into the framework
of Sections 2 and 3: the initial transducer is given in Corollary 4.11, conditions for the
existence of the final transducer are described in Section 4.3, and factorization systems
are tackled in Section 4.4.
$\mathcal{A}(\mathit{out}) = 2$ and the possibility to compute cardinals of objects.

**Example 3.15** (Minimization of weighted automata). Given a field $\mathbb{K}$, fix a $(\mathbb{K}\mathit{Vec}, \mathbb{K}, \mathbb{K})$-automaton $\mathcal{A}$ with finite-dimensional state-space. Since $\mathbb{K}\mathit{Vec}$ is cocomplete and $\mathcal{E} = \mathit{Surj}$ is exactly the class of split epimorphisms (linear surjections are exactly those functions that have a right-inverse), we may use Algorithm 3 (by Corollary 3.9) along with the optimization of Corollary 3.11: the condition on line 12 is then satisfied at most dim $\mathcal{A}(\mathit{st})$ times.

The resulting algorithm computes $\mathit{Reach}\,\mathcal{A}$, i.e. an automaton whose configurations are exactly those that are reachable in $\mathcal{A}$: $v \in (\mathit{Reach}\,\mathcal{A})(\mathit{st})$ if and only if there are $\lambda_1, \dots, \lambda_k \in \mathbb{K}$ and $w_1, \dots, w_k \in \mathcal{A}^*$ such that $v = \sum_{i=1}^k \lambda_i \mathcal{A}(\triangleright w)$. An $\mathcal{M}$-subobject of $\mathcal{A}(\mathit{st})$ is a subvector space of $\mathcal{A}(\mathit{st})$ or equivalently a set of independent vectors of $\mathcal{A}(\mathit{st})$. The algorithm thus maintains $m_{Q_{\mathit{done}}} : \mathbb{Q}/\mathcal{A}(\mathit{st}) \to \mathcal{A}(\mathit{st})$, a set of independent vectors of $\mathcal{A}(\mathit{st})$ that form a basis of the vector space of configurations that have already been visited, as well as a to-do list of pairs of a vector $m_{\{q\}} : \{q\}/\mathcal{A}(\mathit{st}) \to \mathcal{A}(\mathit{st})$ (the factorization of a morphism $\mathbb{K} \to \mathcal{A}(\mathit{st})$ has dimension lesser or equal to 1) and a letter $a$ that are to be considered next. When considering $(m_{\{q\}}, a)$, the algorithm first computes the successor vector $m_{\{qa\}}$ along $a$ by applying the matrix $\mathcal{A}(a)$ and then checks whether $m_{\{qa\}}$ factors through $m_{Q_{\mathit{done}}}$ hence solves a linear system to check whether the vector $m_{\{qa\}}$ is a linear combination of those generating $m_{Q_{\mathit{done}}}$. If this is not the case, $(m_{\{qa\}}, a')$ is added to the to-do list for each $a' \in \mathcal{A}$ and $m_{\{qa\}}$ is added to the basis of $m_{Q_{\mathit{done}}}$ to form the basis of $m_{Q_{\mathit{done}} \sqcup \{qa\}}$. Once the to-do list is empty, the algorithm returns the automaton with state-space $Q_{\mathit{done}}/\mathcal{A}(\mathit{st})$ whose initial configuration, transition functions and final values are inherited from those of $\mathcal{A}$ through a change of basis.

Since the algorithm terminates, it only considers finite subsets $Q$ of $\mathcal{A}^*$ and thus only
manipulates finite-dimensional vector spaces. We may therefore as well consider that all
of its computations take place in the category of finite-dimensional vector spaces. But
the functor that sends a vector space to its dual and a linear map to its transpose is
an isomorphism between this category and its dual which sends $\mathbb{K}$ on itself and swaps
$\mathit{Surj}$ and $\mathit{Inj}$. We are thus in the very special case mentioned in Remark 3.2 where the
algorithm that computes the transpose of $\mathit{Obs}\,\mathcal{A}$ is exactly the one that computes $\mathit{Reach}$
as described above, but applied to the transpose of $\mathcal{A}$.

4. The category of monoidal transducers

We now study a specific family of transition systems, monoidal transducers, through the
lens of category theory, so as to be able to apply the framework of Section 2 as well as
the generic minimization algorithm we extended it with in Section 3. In Section 4.1,
we first rapidly recall the notion of monoid. We then define the category of monoidal
transducers recognizing a function in Section 4.2, and study how it fits into the framework
of Sections 2 and 3: the initial transducer is given in Corollary 4.11, conditions for the
existence of the final transducer are described in Section 4.3, and factorization systems
are tackled in Section 4.4.
**4.1. Monoids**

Let us first recall definitions relating to monoids, and fix some notations. Most of these
are standard in the monoid literature, only coprime-cancellativity (Definition 4.4) and
noetherianity (Definition 4.5) are uncommon.

**Definition 4.1 (monoid).** A monoid $(M, \epsilon_M, \otimes_M)$ is a set $M$ equipped with a binary operation $\otimes_M$ (often called the *product*) that is associative $(\forall u, v, w \in M, u \otimes_M (v \otimes_M w) = (u \otimes_M v) \otimes_M w)$ and has $\epsilon_M$ as *unit element* $(\forall u \in M, u \otimes_M \epsilon_M = \epsilon_M \otimes_M u = u)$. When non-ambiguous, it is simply written $(M, \epsilon, \otimes)$ or even $M$, and the symbol for the binary operation may be omitted.

The dual of $(M, \epsilon, \otimes)$, written $(M^{\text{op}}, \epsilon^{\text{op}}, \otimes^{\text{op}})$, has underlying set $M^{\text{op}} = M$ and identity $\epsilon^{\text{op}} = \epsilon$, but symmetric binary operation : $\forall u, v \in M, u \otimes^{\text{op}} v = v \otimes u$.

The dual of a monoid is mainly used here for the sake of conciseness : whenever we define some “left-property”, the corresponding “right-property” is defined as the left-property but in the dual monoid. Note that when $M$ is commutative it is its own dual and the left- and right-properties coincide.

**Definition 4.2 (invertibility).** An element $x$ of a monoid $M$ is *right-invertible* when there is a $y \in M$ such that $xy = \epsilon$, and $y$ is then called the *right-inverse* of $x$. It is *left-invertible* when it is right-invertible in $M^{\text{op}}$, and the corresponding right-inverse is called its *left-inverse*. When $x$ is both right- and left-invertible, we say it is *invertible*. In that case its right- and left-inverse are equal: this defines its *inverse*, written $x^{-1}$. The set of invertible elements of $M$ is written $M^{\times}$.

Two families $(u_i)_{i \in I}$ and $(v_i)_{i \in I}$ indexed by some non-empty set $I$ are equal *up to invertibles on the left* when there is some invertible $x \in M$ such that $\forall i \in I, u_i = xv_i$.

**Definition 4.3 (divisibility).** An element $u$ of a monoid $M$ *left-divides* a family $w = (w_i)_{i \in I}$ of $M$ indexed by some set $I$ when there is a family $(v_i)_{i \in I}$ such that $\forall i \in I, uv_i = w_i$, and we say that $u$ is a *left-divisor* of $w$. It *right-divides* it when it left-divides it in $M^{\text{op}}$, and in that case $u$ is called a *right-divisor* of $w$.

A greatest common left-divisor (or left-gcd) of the family $w$ is a left-divisor of $w$ that is left-divided by all others left-divisors of $w$.

A family $w$ is said to be *left-coprime* when it has $\epsilon$ as a left-gcd, i.e. when all its left-divisors (or equivalently one of its left-gcds, if there is one) are right-invertible.

We speak of *greatest common left-divisors* because, while there may be many such
elements for a fixed family $\omega$, they all left-divide one another and are thus equivalent in
some sense.

**Definition 4.4 (cancellativity).** A monoid $M$ is said to be *left-cancellative* when for any families $(u_i)_{i \in I}$ and $(v_i)_{i \in I}$ of $M$ indexed by some set $I$ and for any $w \in M$, $u = v$ as soon as $wu_i = wv_i$ for all $i \in I$. If this only implies $u_i = xv_i$ for some $x \in M^\times$, we instead say that $M$ is *left-cancellative up to invertibles on the left*.

Similarly, $M$ is said to be *right-coprime-cancellative* when for any $u, v \in M$ and any
left-coprime family $(w_i)_{i \in I}$ indexed by some set $I$, $u = v$ as soon as $uw_i = vw_i$ for all
$i \in I$.
**4.1. Monoids**

Let us first recall definitions relating to monoids, and fix some notations. Most of these
are standard in the monoid literature, only coprime-cancellativity (Definition 4.4) and
noetherianity (Definition 4.5) are uncommon.

**Definition 4.1 (monoid).** A monoid $(M, \epsilon_M, \otimes_M)$ is a set $M$ equipped with a binary operation $\otimes_M$ (often called the *product*) that is associative $(\forall u, v, w \in M, u \otimes_M (v \otimes_M w) = (u \otimes_M v) \otimes_M w)$ and has $\epsilon_M$ as *unit element* $(\forall u \in M, u \otimes_M \epsilon_M = \epsilon_M \otimes_M u = u)$. When non-ambiguous, it is simply written $(M, \epsilon, \otimes)$ or even $M$, and the symbol for the binary operation may be omitted.

The dual of $(M, \epsilon, \otimes)$, written $(M^{\text{op}}, \epsilon^{\text{op}}, \otimes^{\text{op}})$, has underlying set $M^{\text{op}} = M$ and identity $\epsilon^{\text{op}} = \epsilon$, but symmetric binary operation : $\forall u, v \in M, u \otimes^{\text{op}} v = v \otimes u$.

The dual of a monoid is mainly used here for the sake of conciseness : whenever we define some “left-property”, the corresponding “right-property” is defined as the left-property but in the dual monoid. Note that when $M$ is commutative it is its own dual and the left- and right-properties coincide.

**Definition 4.2 (invertibility).** An element $x$ of a monoid $M$ is *right-invertible* when there is a $y \in M$ such that $xy = \epsilon$, and $y$ is then called the *right-inverse* of $x$. It is *left-invertible* when it is right-invertible in $M^{\text{op}}$, and the corresponding right-inverse is called its *left-inverse*. When $x$ is both right- and left-invertible, we say it is *invertible*. In that case its right- and left-inverse are equal: this defines its *inverse*, written $x^{-1}$. The set of invertible elements of $M$ is written $M^{\times}$.

Two families $(u_i)_{i \in I}$ and $(v_i)_{i \in I}$ indexed by some non-empty set $I$ are equal *up to invertibles on the left* when there is some invertible $x \in M$ such that $\forall i \in I, u_i = xv_i$.

**Definition 4.3 (divisibility).** An element $u$ of a monoid $M$ *left-divides* a family $w = (w_i)_{i \in I}$ of $M$ indexed by some set $I$ when there is a family $(v_i)_{i \in I}$ such that $\forall i \in I, uv_i = w_i$, and we say that $u$ is a *left-divisor* of $w$. It *right-divides* it when it left-divides it in $M^{\text{op}}$, and in that case $u$ is called a *right-divisor* of $w$.

A greatest common left-divisor (or left-gcd) of the family $w$ is a left-divisor of $w$ that is left-divided by all others left-divisors of $w$.

A family $w$ is said to be *left-coprime* when it has $\epsilon$ as a left-gcd, i.e. when all its left-divisors (or equivalently one of its left-gcds, if there is one) are right-invertible.

We speak of *greatest common left-divisors* because, while there may be many such
elements for a fixed family $\omega$, they all left-divide one another and are thus equivalent in
some sense.

**Definition 4.4 (cancellativity).** A monoid $M$ is said to be *left-cancellative* when for any families $(u_i)_{i \in I}$ and $(v_i)_{i \in I}$ of $M$ indexed by some set $I$ and for any $w \in M$, $u = v$ as soon as $wu_i = wv_i$ for all $i \in I$. If this only implies $u_i = xv_i$ for some $x \in M^\times$, we instead say that $M$ is *left-cancellative up to invertibles on the left*.

Similarly, $M$ is said to be *right-coprime-cancellative* when for any $u, v \in M$ and any
left-coprime family $(w_i)_{i \in I}$ indexed by some set $I$, $u = v$ as soon as $uw_i = vw_i$ for all
$i \in I$.
**Definition 4.5 (noetherianity).** A monoid $M$ is right-noetherian when for any sequences $(u_n)_{n \in \mathbb{N}}$ and $(v_n)_{n \in \mathbb{N}}$ of $M$ such that $v_n = v_{n+1}u_n$ for all $n \in \mathbb{N}$, there is some $n \in \mathbb{N}$ such that $u_n$ is invertible.

In this case, we write rk$v$ for the rank of $v$, the (possibly infinite) supremum of the numbers of non-invertibles in a sequence $(u_n)_{n \in \mathbb{N}}$ that satisfies $v_n = v_{n+1}u_n$ for a sequence $(v_n)_{n \in \mathbb{N}}$ with $v_0 = v$.

In other words, a monoid is right-noetherian when it has no strict infinite chains of right-divisors (in the definition above, each $u_n \cdots u_0$ right-divides $v_0$). Note that rk$(uv) \le$ rk$u + rk$v, and rk : $M \to \mathbb{N}$, and if this is an equality $M$ is said to be graded.

Noetherianity will be used to ensure that fixed-point algorithms terminate, hence we will often assume that the monoids we work with satisfy some noetherianity properties. We therefore state two additional lemmas making it easier to work with noetherian monoids. They both assume $M$ to be right-noetherian but the dual results also stand.

**Lemma 4.6.** *M is right-noetherian if and only if for any sequences $(u_n)_{n \in \mathbb{N}}$ and $(v_n)_{n \in \mathbb{N}}$ of M such that $v_n = v_{n+1}u_n$ for all $n \in \mathbb{N}$, there is some $n \in \mathbb{N}$ such that for all $i \ge n$, $u_i$ is invertible.*

**Lemma 4.7.** *If $M$ is right-noetherian then all its right- and left-invertibles are invertible.*

**Example 4.8.** The canonical example of a monoid is the free monoid $A^*$ over an alphabet $A$, whose elements are words with letters in $A$, whose product is the concatenation of words and whose unit is the empty word. Notice that the alphabet $A$ may be infinite. The left-divisibility relation is the prefix one, and the left-gcd is the longest common prefix.

The free commutative monoid $A^*$ over $A$ has elements the functions $A \to \mathbb{N}$ with finite support, product $(f \otimes g)(a) = f(a) + g(a)$ and unit the zero function $a \mapsto 0$. It is commutative $(f \otimes g = g \otimes f)$ hence is its own dual : the divisibility relation is the pointwise order inherited from $\mathbb{N}$ and the greatest common divisor is the pointwise infimum.

These two monoids are examples of *trace monoids* over some $A$, defined as quotients of $A^*$ by commutativity relations on letters (for $A^*$, all the pairs of letters are required to commute, and for $A^*$ none are). Trace monoids have no non-trivial right- or left-invertible elements, are all left-cancellative, right-coprime-cancellative and right-noetherian, and the rank of a word is simply its number of letters.

Another family of examples is that of *groups*, monoids where all elements are invertible. Again, all groups are left-cancellative, right-coprime-cancellative and right-noetherian.

A final monoid of interest is $(E, \vee, \bot)$ for $E$ any join-semilattice with a bottom element $\bot$. In this commutative monoid, the divisibility relation is the partial order on $E$, and the gcd, when it exists, is the infimum. This example shows that a monoid can be coprime-cancellative without being cancellative nor noetherian: this is for instance the case when $E = \mathbb{R}_+$ (this counter-example was pointed out to the author by Thomas Colcombet).
**Definition 4.5 (noetherianity).** A monoid $M$ is right-noetherian when for any sequences $(u_n)_{n \in \mathbb{N}}$ and $(v_n)_{n \in \mathbb{N}}$ of $M$ such that $v_n = v_{n+1}u_n$ for all $n \in \mathbb{N}$, there is some $n \in \mathbb{N}$ such that $u_n$ is invertible.

In this case, we write rk$v$ for the rank of $v$, the (possibly infinite) supremum of the numbers of non-invertibles in a sequence $(u_n)_{n \in \mathbb{N}}$ that satisfies $v_n = v_{n+1}u_n$ for a sequence $(v_n)_{n \in \mathbb{N}}$ with $v_0 = v$.

In other words, a monoid is right-noetherian when it has no strict infinite chains of right-divisors (in the definition above, each $u_n \cdots u_0$ right-divides $v_0$). Note that rk$(uv) \le$ rk$u + rkv$, and rk : $M \to \mathbb{N}$, and if this is an equality $M$ is said to be graded.

Noetherianity will be used to ensure that fixed-point algorithms terminate, hence we will often assume that the monoids we work with satisfy some noetherianity properties. We therefore state two additional lemmas making it easier to work with noetherian monoids. They both assume $M$ to be right-noetherian but the dual results also stand.

**Lemma 4.6.** *M is right-noetherian if and only if for any sequences $(u_n)_{n \in \mathbb{N}}$ and $(v_n)_{n \in \mathbb{N}}$ of M such that $v_n = v_{n+1}u_n$ for all $n \in \mathbb{N}$, there is some $n \in \mathbb{N}$ such that for all $i \ge n$, $u_i$ is invertible.*

**Lemma 4.7.** *If $M$ is right-noetherian then all its right- and left-invertibles are invertible.*

**Example 4.8.** The canonical example of a monoid is the free monoid $A^*$ over an alphabet $A$, whose elements are words with letters in $A$, whose product is the concatenation of words and whose unit is the empty word. Notice that the alphabet $A$ may be infinite. The left-divisibility relation is the prefix one, and the left-gcd is the longest common prefix.

The free commutative monoid $A^*$ over $A$ has elements the functions $A \to \mathbb{N}$ with finite support, product $(f \otimes g)(a) = f(a) + g(a)$ and unit the zero function $a \mapsto 0$. It is commutative $(f \otimes g = g \otimes f)$ hence is its own dual : the divisibility relation is the pointwise order inherited from $\mathbb{N}$ and the greatest common divisor is the pointwise infimum.

These two monoids are examples of *trace monoids* over some $A$, defined as quotients of $A^*$ by commutativity relations on letters (for $A^*$, all the pairs of letters are required to commute, and for $A^*$ none are). Trace monoids have no non-trivial right- or left-invertible elements, are all left-cancellative, right-coprime-cancellative and right-noetherian, and the rank of a word is simply its number of letters.

Another family of examples is that of *groups*, monoids where all elements are invertible. Again, all groups are left-cancellative, right-coprime-cancellative and right-noetherian.

A final monoid of interest is $(E, \vee, \bot)$ for $E$ any join-semilattice with a bottom element $\bot$. In this commutative monoid, the divisibility relation is the partial order on $E$, and the gcd, when it exists, is the infimum. This example shows that a monoid can be coprime-cancellative without being cancellative nor noetherian: this is for instance the case when $E = \mathbb{R}_+$ (this counter-example was pointed out to the author by Thomas Colcombet).
## 4.2. Monoidal transducers as functors

In the rest of this paper we fix a countable input alphabet $A$ and an output monoid $(M, \epsilon, \otimes)$. To differentiate between elements of $A^*$ and elements of $M$, we write the former with Latin letters $(a, b, c, \dots$ for letters and $u, v, w, \dots$ for words) and the latter with Greek letters $(\alpha, \beta, \gamma, \dots$ for generating elements and $\upsilon, \nu, \omega, \dots$ for general elements). In particular the empty word over $A$ is denoted $e$ while the unit of $M$ is still written $\epsilon$.

We write $\mathcal{T}_M$ for the monad on Set given by $\mathcal{T}_M X = M \times X + 1 = (M \times X) \sqcup \{\perp\}$ (in Haskell, this monad is the composite of the Maybe monad and a Writer monad). Its unit $\eta: \text{Id} \Rightarrow \mathcal{T}_M$ is given by $\eta_X(x) = (\epsilon, x)$ and its multiplication $\mu: \mathcal{T}_M^2 \Rightarrow \mathcal{T}_M$ is given by $\mu_X((\upsilon, (\nu, x))) = (\nu\upsilon, x)$, $\mu_X((\upsilon, \perp)) = \perp$ and $\mu_X(\perp) = \perp$. Recall that the Kleisli category KI$(\mathcal{T}_M)$ for the monad $\mathcal{T}_M$ has objects the sets and arrows $X \to Y$ (notice the different symbol) those functions $f^\dagger: \mathcal{T}_M X \to \mathcal{T}_M Y$ such that $f^\dagger(\perp) = \perp$, $f^\dagger(\upsilon, x) = (\upsilon\upsilon, y)$ when $f^\dagger(\epsilon, x) = (\upsilon, y)$ and $f^\dagger(\upsilon, x) = \perp$ when $f(\epsilon, x) = \perp$: in particular, such an arrow is entirely determined by its restriction $f: X \to \mathcal{T}_M Y$, and we will freely switch between these two points of view for the sake of conciseness. The identity on $X$ is then given by the identity function $\text{id}_{\mathcal{T}_M X} = \eta_X^\dagger: \mathcal{T}_M X \to \mathcal{T}_M X$, and the composition of two arrows $X \to Y \to Z$ is given by the composition of the underlying functions $\mathcal{T}_M X \to \mathcal{T}_M Y \to \mathcal{T}_M Z$.

We now have all the ingredients to define our main object of study, monoidal transducers.

**Definition 4.9 (monoidal transducer).** The category Trans$_M$ of $M$-transducers is the category of $(\text{KI}(\mathcal{T}_M), 1, 1)$-automata from Definition 2.1. An $M$-transducer (or monoidal transducer over $M$, or simply transducer) is thus a functor $\mathcal{A}: \mathcal{I} \to \text{KI}(\mathcal{T}_M)$ with $\mathcal{A}(\text{in}) = \mathcal{A}(\text{out}) = 1$, and a morphism of transducers is a natural transformation between the corresponding functors whose restriction to $\mathcal{O}$ is the identity. Similarly given a $(\text{KI}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$, Trans$_M(\mathcal{L})$ is the category of monoidal transducers recognizing $\mathcal{L}$.

In practice, a monoidal transducer $\mathcal{A}$ is thus a tuple $(S, (v_0, s_0), t, (\stackrel{-\odot}{a})_{a \in A})$ where:

* $S$ is the state-set;

* $(v_0, s_0) = \mathcal{A}(\triangleright) \in M \times S + 1$ is the (possibly undefined) pair of the initialization value and initial state;

* $t = \mathcal{A}(\triangleleft): S \to M + 1$ is the partial termination function;

* $s \odot a = \mathcal{A}(a)(s) \in M \times S + 1$ may be undefined, and we write $- \cdot a: S \to S + 1$ for the second component of $- \odot a$, the partial transition function along $a$, and $- \circ a: S \to M + 1$ for its first component, the partial production function along $a$.

Similarly, the language $\mathcal{L} = \mathcal{A} \circ \iota$ recognized by this monoidal transducer is thus a function $L: A^* \to M + 1$ given by $L(a_1 \cdots a_n) = t^\dagger((v_0, s_0) \odot^\dagger a_1 \odot^\dagger \cdots \odot^\dagger a_n)$, and a morphism between two transducers $(S_1, (v_1, s_1), t_1, \odot_1)$ and $(S_2, (v_2, s_2), t_2, \odot_2)$ is a function $f: S_1 \to M \times S_2 + 1$ such that $f^\dagger(v_1, s_1) = (v_2, s_2)$, $t_1(s) = t_2^\dagger(f(s))$ and
## 4.2. Monoidal transducers as functors

In the rest of this paper we fix a countable input alphabet $A$ and an output monoid $(M, \epsilon, \otimes)$. To differentiate between elements of $A^*$ and elements of $M$, we write the former with Latin letters $(a, b, c, \dots$ for letters and $u, v, w, \dots$ for words) and the latter with Greek letters $(\alpha, \beta, \gamma, \dots$ for generating elements and $\upsilon, \nu, \omega, \dots$ for general elements). In particular the empty word over $A$ is denoted $e$ while the unit of $M$ is still written $\epsilon$.

We write $\mathcal{T}_M$ for the monad on Set given by $\mathcal{T}_M X = M \times X + 1 = (M \times X) \sqcup \{\perp\}$ (in Haskell, this monad is the composite of the Maybe monad and a Writer monad). Its unit $\eta: \text{Id} \Rightarrow \mathcal{T}_M$ is given by $\eta_X(x) = (\epsilon, x)$ and its multiplication $\mu: \mathcal{T}_M^2 \Rightarrow \mathcal{T}_M$ is given by $\mu_X((\upsilon, (\nu, x))) = (\nu\upsilon, x)$, $\mu_X((\upsilon, \perp)) = \perp$ and $\mu_X(\perp) = \perp$. Recall that the Kleisli category KI$(\mathcal{T}_M)$ for the monad $\mathcal{T}_M$ has objects the sets and arrows $X \to Y$ (notice the different symbol) those functions $f^\dagger: \mathcal{T}_M X \to \mathcal{T}_M Y$ such that $f^\dagger(\perp) = \perp$, $f^\dagger(\upsilon, x) = (\upsilon\upsilon, y)$ when $f^\dagger(\epsilon, x) = (\upsilon, y)$ and $f^\dagger(\upsilon, x) = \perp$ when $f(\epsilon, x) = \perp$: in particular, such an arrow is entirely determined by its restriction $f: X \to \mathcal{T}_M Y$, and we will freely switch between these two points of view for the sake of conciseness. The identity on $X$ is then given by the identity function $\text{id}_{\mathcal{T}_M X} = \eta_X^\dagger: \mathcal{T}_M X \to \mathcal{T}_M X$, and the composition of two arrows $X \to Y \to Z$ is given by the composition of the underlying functions $\mathcal{T}_M X \to \mathcal{T}_M Y \to \mathcal{T}_M Z$.

We now have all the ingredients to define our main object of study, monoidal transducers.

**Definition 4.9 (monoidal transducer).** The category Trans$_M$ of M-transducers is the category of (KI$(\mathcal{T}_M)$, 1, 1)-automata from Definition 2.1. An M-transducer (or monoidal transducer over $M$, or simply transducer) is thus a functor $\mathcal{A}: \mathcal{I} \to \text{KI}(\mathcal{T}_M)$ with $\mathcal{A}(\text{in}) = \mathcal{A}(\text{out}) = 1$, and a morphism of transducers is a natural transformation between the corresponding functors whose restriction to $\mathcal{O}$ is the identity. Similarly given a (KI$(\mathcal{T}_M)$, 1, 1)-language $\mathcal{L}$, Trans$_M(\mathcal{L})$ is the category of monoidal transducers recognizing $\mathcal{L}$.

In practice, a monoidal transducer $\mathcal{A}$ is thus a tuple $(S, (v_0, s_0), t, (\stackrel{-\odot}{a})_{a \in A})$ where:

* $S$ is the state-set;

* $(v_0, s_0) = \mathcal{A}(\triangleright) \in M \times S + 1$ is the (possibly undefined) pair of the initialization value and initial state;

* $t = \mathcal{A}(\triangleleft): S \to M + 1$ is the partial termination function;

* $s \odot a = \mathcal{A}(a)(s) \in M \times S + 1$ may be undefined, and we write $- \cdot a: S \to S + 1$ for the second component of $- \odot a$, the partial transition function along $a$, and $- \circ a: S \to M + 1$ for its first component, the partial production function along $a$.

Similarly, the language $\mathcal{L} = \mathcal{A} \circ \iota$ recognized by this monoidal transducer is thus a function $L: A^* \to M + 1$ given by $L(a_1 \cdots a_n) = t^\dagger((v_0, s_0) \odot^\dagger a_1 \odot^\dagger \cdots \odot^\dagger a_n)$, and a morphism between two transducers $(S_1, (v_1, s_1), t_1, \odot_1)$ and $(S_2, (v_2, s_2), t_2, \odot_2)$ is a function $f: S_1 \to M \times S_2 + 1$ such that $f^\dagger(v_1, s_1) = (v_2, s_2)$, $t_1(s) = t_2^\dagger(f(s))$ and
$f^\dagger(s \odot a) = f^\dagger(s) \odot^\dagger a$. We say that this function is *subsequential* when it is recognized by a transducer with finite state-space.

**Example 4.10.** Figure 2 is a graphical representation of a monoidal transducer that takes its input in the alphabet $A = \{a, b\}$ and has output in any monoid that is a quotient of $\Sigma^*$, with $\Sigma = \{\alpha, \beta\}$. Formally, it is given by $S = \{1, 2, 3, 4\}$; $(v_0, s_0) = (\epsilon, 1)$; $t(1) = \alpha$, $t(2) = \perp$, $t(3) = \alpha$ and $t(4) = \epsilon$; and finally $1 \odot a = (\epsilon, 2)$, $1 \odot b = (\beta, 3)$, $3 \odot b = (\beta, 3)$ as well as $s \odot c = \perp$ for any other $s \in S$ and $c \in A$. This transducer recognizes the function given by $L(b^n) = \beta^n\alpha$ (seen in the corresponding quotient monoid, so for instance $L(b^n) = \alpha\beta^n$ when $M = \Sigma^*$) for all $n \in \mathbb{N}$ and $L(w) = \perp$ otherwise.

<figure><img src="image_8.png" /><figcaption>Figure 2: A monoidal transducer $\mathcal{A}$</figcaption></figure>

When $M = B^*$ for some alphabet $B$, $M$-transducers coincide with the classical notion of transducers and the minimal transducer is given by **Definition 2.9** [9, 23]. To study the notion of minimal monoidal transducer, it is thus natural to try to follow this framework as well.

**4.3. The initial and final monoidal transducers recognizing a function**

To apply the framework of **Sections 2 and 3** to $(\mathbf{Kl}(\mathcal{T}_M), 1, 1)$-automata, we need three ingredients in $\mathbf{Kl}(\mathcal{T}_M)$ : countable copowers of 1, countable powers of 1, and a factorization system.

We start with the first ingredient, countable copowers of 1. Since **Set** has arbitrary coproducts, $\mathbf{Kl}(\mathcal{T}_M)$ has arbitrary coproducts as well as any Kleisli category for a monad over a category with coproducts does [26]. Hence **Theorem 2.12** applies:

**Corollary 4.11 (initial transducer).** For any $(\mathbf{Kl}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$, $\mathbf{Trans}_M(\mathcal{L})$ has an initial object $\mathcal{A}^{\text{init}}(\mathcal{L})$ with state-set $S^{\text{init}} = A^*$, initial state $s_0^{\text{init}} = e$, initialization value $v_0^{\text{init}} = \epsilon$, termination function $t^{\text{init}}(w) = \mathcal{L}(\vdash w \triangleleft (*)$) and transition function $w \odot^{\text{init}} a = (\epsilon, wa)$. Given any other transducer $\mathcal{A} = (S, (v_0, s_0), t, \odot)$ recognizing $\mathcal{L}$, the unique transducer morphism $f: \mathcal{A}^{\text{init}}(\mathcal{L}) \to \mathcal{A}$ is given by the function $f: A^* \to M \times S + 1$ such that $f(w) = \mathcal{A}(\vdash w)(*) = (v_0, s_0) \odot^\dagger w$.

Similarly, to get a final transducer in $\mathbf{Trans}_M(\mathcal{L})$ for some $\mathcal{L}$, **Theorem 2.12** tells us that it is enough for $\mathbf{Kl}(\mathcal{T}_M)$ to have all countable powers of 1. This is in particular what happens for classical transducers, when $M$ is a free monoid [23]. Hence we study the properties of a monoid $M$ such that $\mathbf{Kl}(\mathcal{T}_M)$ has these powers.
$f^\dagger(s \odot a) = f^\dagger(s) \odot^\dagger a$. We say that this function is *subsequential* when it is recognized by a transducer with finite state-space.

**Example 4.10.** Figure 2 is a graphical representation of a monoidal transducer that takes its input in the alphabet $A = \{a, b\}$ and has output in any monoid that is a quotient of $\Sigma^*$, with $\Sigma = \{\alpha, \beta\}$. Formally, it is given by $S = \{1, 2, 3, 4\}$; $(v_0, s_0) = (\epsilon, 1)$; $t(1) = \alpha$, $t(2) = \perp$, $t(3) = \alpha$ and $t(4) = \epsilon$; and finally $1 \odot a = (\epsilon, 2)$, $1 \odot b = (\beta, 3)$, $3 \odot b = (\beta, 3)$ as well as $s \odot c = \perp$ for any other $s \in S$ and $c \in A$. This transducer recognizes the function given by $L(b^n) = \beta^n\alpha$ (seen in the corresponding quotient monoid, so for instance $L(b^n) = \alpha\beta^n$ when $M = \Sigma^*$) for all $n \in \mathbb{N}$ and $L(w) = \perp$ otherwise.

<figure><img src="image_10.png" /><figcaption>Figure 2: A monoidal transducer $\mathcal{A}$</figcaption></figure>

When $M = B^*$ for some alphabet $B$, $M$-transducers coincide with the classical notion of transducers and the minimal transducer is given by **Definition 2.9** [9, 23]. To study the notion of minimal monoidal transducer, it is thus natural to try to follow this framework as well.

### 4.3. The initial and final monoidal transducers recognizing a function

To apply the framework of Sections 2 and 3 to $(\mathbf{Kl}(\mathcal{T}_M), 1, 1)$-automata, we need three ingredients in $\mathbf{Kl}(\mathcal{T}_M)$: countable copowers of 1, countable powers of 1, and a factorization system.

We start with the first ingredient, countable copowers of 1. Since **Set** has arbitrary coproducts, $\mathbf{Kl}(\mathcal{T}_M)$ has arbitrary coproducts as well as any Kleisli category for a monad over a category with coproducts does [26]. Hence **Theorem 2.12** applies:

**Corollary 4.11 (initial transducer).** For any $(\mathbf{Kl}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$, $\text{Trans}_M(\mathcal{L})$ has an initial object $\mathcal{A}^{\text{init}}(\mathcal{L})$ with state-set $S^{\text{init}} = A^*$, initial state $s_0^{\text{init}} = e$, initialization value $v_0^{\text{init}} = \epsilon$, termination function $t^{\text{init}}(w) = \mathcal{L}(\vdash w \triangleleft (*)$) and transition function $w \odot^{\text{init}} a = (\epsilon, wa)$. Given any other transducer $\mathcal{A} = (S, (v_0, s_0), t, \odot)$ recognizing $\mathcal{L}$, the unique transducer morphism $f: \mathcal{A}^{\text{init}}(\mathcal{L}) \to \mathcal{A}$ is given by the function $f: A^* \to M \times S + 1$ such that $f(w) = \mathcal{A}(\vdash w)(*) = (v_0, s_0) \odot^\dagger w$.

Similarly, to get a final transducer in $\text{Trans}_M(\mathcal{L})$ for some $\mathcal{L}$, **Theorem 2.12** tells us that it is enough for $\mathbf{Kl}(\mathcal{T}_M)$ to have all countable powers of 1. This is in particular what happens for classical transducers, when $M$ is a free monoid [23]. Hence we study the properties of a monoid $M$ such that $\mathbf{Kl}(\mathcal{T}_M)$ has these powers.
To this means, given a countable set $I$ we consider partial functions $\Lambda : I \to M+1$. We write $\perp^I$ for the nowhere defined function $i \mapsto \perp$ and $(M+1)_*^I = (M+1)^I - \{\perp^I\}$ for the set of partial functions that are defined somewhere. If $I \subseteq J$, $(M+1)_*^I$ may thus be identified with the subset of partial functions of $(M+1)_*^J$ that are undefined on $J-I$. We extend the product $\otimes : M^2 \to M$ of $M$ to a function $M \times (M+1)_*^I \to (M+1)_*^I$ by setting $(v \otimes \Lambda)(i) = v \otimes \Lambda(i)$ for $i \in I$ such that $\Lambda(i) \neq \perp$ and $(v \otimes \Lambda)(i) = \perp$ otherwise. The universal property of the product then translates as:

**Proposition 4.12.** *The following are equivalent:*

(1) $\mathrm{KI}(\mathcal{T}_M)$ has all countable powers of 1;

(2) there are two functions $\mathrm{lgcd} : (M+1)_*^N \to M$ and $\mathrm{red} : (M+1)_*^N \to (M+1)_*^N$ such that

a) for all $\Lambda \in (M+1)_*^N$, $\Lambda = \mathrm{lgcd}(\Lambda) \mathrm{red}(\Lambda)$;

b) for all $\Gamma, \Lambda \in (M+1)_*^N$ and $v, \nu \in M$, if $v \mathrm{red}(\Gamma) = \nu \mathrm{red}(\Lambda)$ then $v = \nu$ and $\mathrm{red} \Gamma = \mathrm{red} \Lambda$;

(3) $\mathrm{KI}(\mathcal{T}_M)$ has all countable products.

Moreover when these hold, since any countable set $I$ embeds into $\mathbb{N}$, $\mathrm{lgcd}$ and $\mathrm{red}$ can be extended to $(M+1)_*^I$. $\mathrm{lgcd} \Lambda$ is then a left-$\mathrm{gcd}$ of $(\Lambda(i))_{i|\Lambda(i) \neq \perp}$ and the product of $(X_i)_{i \in I}$ for some $I \subseteq \mathbb{N}$ is the set of pairs $(\Lambda, (x_i)_{i \in I})$ such that $\Lambda \in \mathrm{red}((M+1)_*^I)$ and, for all $i \in I$, $x_i \in X_i$ if $\Lambda(i) \neq \perp$ and $x_i = \perp$ otherwise. In particular, the $I$-th power of 1 is the set of irreducible partial functions $I \to M+1$:

$$ \prod_I 1 = \mathrm{Irr}(I, M) = \{\mathrm{red} \Lambda \in (M+1)_*^I \mid \Lambda \in (M+1)_*^I\} $$

We also write $\mathrm{lgcd}(\perp^N) = \perp$, $\mathrm{red}(\perp^N) = \perp^N = \perp$ and do not distinguish between $(\perp, \perp)$ and $\perp$. Also note that:

**Lemma 4.13.** *Conditions (2)a and (2)b are equivalent to saying that*

(4) a) $\langle \mathrm{lgcd}, \mathrm{red} \rangle$ is injective;

b) for all $\Lambda \in (M+1)_*^N$, $\mathrm{lgcd}(\mathrm{red} \Lambda) = \epsilon$ and $\mathrm{red}(\mathrm{red} \Lambda) = \mathrm{red} \Lambda$;

c) for all $\Lambda \in (M+1)_*^N$ and $v \in M$, $\mathrm{lgcd}(v\Lambda) = v \mathrm{lgcd}(\Lambda)$ and $\mathrm{red}(v\Lambda) = \mathrm{red}(\Lambda)$.

**Corollary 4.14.** *When the functions $\mathrm{lgcd}$ and $\mathrm{red}$ exist, the final transducer $\mathcal{A}^{\mathrm{final}}(\mathcal{L})$ recognizing a $(\mathrm{KI}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$ exists and has state-set $S^{\mathrm{final}} = \mathrm{Irr}(A^*, M)$, initial state $s_0^{\mathrm{final}} = \mathrm{red} \mathcal{L}$, initialization value $v_0^{\mathrm{final}} = \mathrm{lgcd} \mathcal{L}$, termination function $t^{\mathrm{final}}(\Lambda) = \Lambda(e)$ and transition function $\Lambda \odot^{\mathrm{final}} a = (\mathrm{lgcd}(a^{-1}\Lambda), \mathrm{red}(a^{-1}\Lambda))$ where we write $(a^{-1}\Lambda)(w) = \Lambda(aw)$ for $a \in A$. Given any other transducer $\mathcal{A} = (S, (v_0, s_0), t, \odot)$ recognizing $\mathcal{L}$, the unique transducer morphism $f : \mathcal{A} \to \mathcal{A}^{\mathrm{final}}(\mathcal{L})$ is given by the function $f : S \to M \times \mathrm{Irr}(A^*, M) + 1$ such that $f(s) = (\mathrm{lgcd} \mathcal{L}_s, \mathrm{red} \mathcal{L}_s)$ where $\mathcal{L}_s(\triangleright w \triangleleft)(*) = \mathcal{A}(w \triangleleft)(s)$ is the function recognized by $\mathcal{A}$ from the state $s$.
To this means, given a countable set $I$ we consider partial functions $\Lambda : I \to M + 1$. We write $\perp^I$ for the nowhere defined function $i \mapsto \perp$ and $(M+1)_*^I = (M+1)^I - \{\perp^I\}$ for the set of partial functions that are defined somewhere. If $I \subseteq J$, $(M+1)_*^I$ may thus be identified with the subset of partial functions of $(M+1)_*^J$ that are undefined on $J - I$. We extend the product $\otimes : M^2 \to M$ of $M$ to a function $M \times (M+1)_*^I \to (M+1)_*^I$ by setting $(v \otimes \Lambda)(i) = v \otimes \Lambda(i)$ for $i \in I$ such that $\Lambda(i) \neq \perp$ and $(v \otimes \Lambda)(i) = \perp$ otherwise. The universal property of the product then translates as:

**Proposition 4.12.** *The following are equivalent:*

(1) $\mathrm{KI}(\mathcal{T}_M)$ has all countable powers of 1;

(2) there are two functions $\mathrm{lgcd} : (M+1)_*^N \to M$ and $\mathrm{red} : (M+1)_*^N \to (M+1)_*^N$ such that

a) for all $\Lambda \in (M+1)_*^N$, $\Lambda = \mathrm{lgcd}(\Lambda) \mathrm{red}(\Lambda)$;

b) for all $\Gamma, \Lambda \in (M+1)_*^N$ and $v, \nu \in M$, if $v \mathrm{red}(\Gamma) = \nu \mathrm{red}(\Lambda)$ then $v = \nu$ and $\mathrm{red} \Gamma = \mathrm{red} \Lambda$;

(3) $\mathrm{KI}(\mathcal{T}_M)$ has all countable products.

Moreover when these hold, since any countable set $I$ embeds into $\mathbb{N}$, $\mathrm{lgcd}$ and $\mathrm{red}$ can be extended to $(M+1)_*^I$. $\mathrm{lgcd} \Lambda$ is then a left-$\mathrm{gcd}$ of $(\Lambda(i))_{i|\Lambda(i) \neq \perp}$ and the product of $(X_i)_{i \in I}$ for some $I \subseteq \mathbb{N}$ is the set of pairs $(\Lambda, (x_i)_{i \in I})$ such that $\Lambda \in \mathrm{red}((M+1)_*^I)$ and, for all $i \in I$, $x_i \in X_i$ if $\Lambda(i) \neq \perp$ and $x_i = \perp$ otherwise. In particular, the $I$-th power of 1 is the set of irreducible partial functions $I \to M + 1$:

$$ \prod_I 1 = \mathrm{Irr}(I, M) = \{\mathrm{red} \Lambda \in (M+1)_*^I \mid \Lambda \in (M+1)_*^I\} $$

We also write $\mathrm{lgcd}(\perp^N) = \perp$, $\mathrm{red}(\perp^N) = \perp^N = \perp$ and do not distinguish between $(\perp, \perp)$ and $\perp$. Also note that:

**Lemma 4.13.** *Conditions (2)a and (2)b are equivalent to saying that*

(4) a) $\langle \mathrm{lgcd}, \mathrm{red} \rangle$ is injective;

b) for all $\Lambda \in (M+1)_*^N$, $\mathrm{lgcd}(\mathrm{red} \Lambda) = \epsilon$ and $\mathrm{red}(\mathrm{red} \Lambda) = \mathrm{red} \Lambda$;

c) for all $\Lambda \in (M+1)_*^N$ and $v \in M$, $\mathrm{lgcd}(v\Lambda) = v \mathrm{lgcd}(\Lambda)$ and $\mathrm{red}(v\Lambda) = \mathrm{red}(\Lambda)$.

**Corollary 4.14.** *When the functions $\mathrm{lgcd}$ and $\mathrm{red}$ exist, the final transducer $\mathcal{A}^{\mathrm{final}}(\mathcal{L})$ recognizing a $(\mathrm{KI}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$ exists and has state-set $S^{\mathrm{final}} = \mathrm{Irr}(A^*, M)$, initial state $s_0^{\mathrm{final}} = \mathrm{red} \mathcal{L}$, initialization value $v_0^{\mathrm{final}} = \mathrm{lgcd} \mathcal{L}$, termination function $t^{\mathrm{final}}(\Lambda) = \Lambda(e)$ and transition function $\Lambda \odot^{\mathrm{final}} a = (\mathrm{lgcd}(a^{-1}\Lambda), \mathrm{red}(a^{-1}\Lambda))$ where we write $(a^{-1}\Lambda)(w) = \Lambda(aw)$ for $a \in A$. Given any other transducer $\mathcal{A} = (S, (v_0, s_0), t, \odot)$ recognizing $\mathcal{L}$, the unique transducer morphism $f : \mathcal{A} \to \mathcal{A}^{\mathrm{final}}(\mathcal{L})$ is given by the function $f : S \to M \times \mathrm{Irr}(A^*, M) + 1$ such that $f(s) = (\mathrm{lgcd} \mathcal{L}_s, \mathrm{red} \mathcal{L}_s)$ where $\mathcal{L}_s(\triangleright w \triangleleft)(*) = \mathcal{A}(w \triangleleft)(s)$ is the function recognized by $\mathcal{A}$ from the state $s$.
In practice we will assume that $M$ is right-noetherian to ensure algorithms terminate. It is thus interesting to see what the existence of the powers of $1$ implies in this specific case (and in particular, by Lemma 4.7, when $M$ is such that all right- and left-invertibles are invertibles).

**Lemma 4.15.** If right- and left-invertibles of $M$ are all invertibles and if $\mathbf{KI}(\mathcal{T}_M)$ has all countable powers of $1$ then $M$ is both left-cancellative up to invertibles on the left and right-coprime-cancellative, and all non-empty countable families of $M$ have a unique left-gcd up to invertibles on the right.

And conversely, these conditions on $M$ are enough for $\mathbf{KI}(\mathcal{T}_M)$ to have all countable powers of $1$ (even when $M$ is not noetherian), while being easier to show than properly defining the two functions $\text{lgcd}$ and $\text{red}$.

**Lemma 4.16.** If $M$ is both left-cancellative up to invertibles on the left and right-coprime-cancellative, and all non-empty countable subsets of $M$ have a unique left-gcd up to invertibles on the right, then $\mathbf{KI}(\mathcal{T}_M)$ has all countable powers of $1$.

**Example 4.17.** When $M$ is a group it is cancellative (because all elements are invertible) and all countable families have a unique left-gcd up to invertibles on the right ($\epsilon$ itself) hence Lemma 4.16 applies and $\text{Trans}_M(\mathcal{L})$ always has a final object.

The same is true when $M$ is a trace monoid (the left-gcd then being the longest common prefix, whose existence is guaranteed by [13, Proposition 1.3]).

Conversely, the monoids given by join semi-lattices are not left-cancellative up to invertibles in general. In $\mathbb{R}_+$ for instance, there are ways to define the functions $\text{lgcd}$ and $\text{red}$ but they may not satisfy condition (4)c, more precisely that $\text{red}(v\Lambda) = \text{red}\Lambda$. This is expected, as there may be several non-isomorphic ways to minimize automata with outputs in these monoids, which is incompatible with the framework of Definition 2.9.

**Proposition 4.12** is reminiscent of a very similar sufficient condition on a semi-ring for deterministic weighted automata to be minimizable in a unique way [15], namely that only an analogue of the red function should exist. The minimal transducer could then again be obtained as the factorization of the unique arrow $\mathcal{A}^{\text{init}}(\mathcal{L}) \to \mathcal{A}^{\text{final}}(\mathcal{L})$, except $\mathcal{A}^{\text{final}}(\mathcal{L})$ would not be final anymore but only weakly final (for any transducer $\mathcal{A}$ recognizing $\mathcal{L}$ there would be an arrow $\mathcal{A} \to \mathcal{A}^{\text{final}}(\mathcal{L})$ but it would not need to be unique), hence our framework would not entail its unicity. However, as further discussed in Section 5.2, these weaker conditions do not really lead to a proper minimization algorithm.

**Lemma 4.16** provides sufficient conditions that are reminiscent of those developed in [17] for the minimization of monoidal transducers. These conditions are stronger than ours but still similar: the output monoid is assumed to be both left- and right-cancellative, which in particular implies the unicity up to invertibles on the right of the left-gcd whose existence is also assumed. They do only require the existence of left-gcds for finite families (whereas we ask for left-gcds of countable families), which would not be enough for our sake since the categorical framework also encompasses the existence of minimal (infinite) automata for non-regular languages, but in practice our algorithms
In practice we will assume that $M$ is right-noetherian to ensure algorithms terminate. It is thus interesting to see what the existence of the powers of $1$ implies in this specific case (and in particular, by Lemma 4.7, when $M$ is such that all right- and left-invertibles are invertibles).

**Lemma 4.15.** If right- and left-invertibles of $M$ are all invertibles and if $\mathbf{KI}(\mathcal{T}_M)$ has all countable powers of $1$ then $M$ is both left-cancellative up to invertibles on the left and right-coprime-cancellative, and all non-empty countable families of $M$ have a unique left-gcd up to invertibles on the right.

And conversely, these conditions on $M$ are enough for $\mathbf{KI}(\mathcal{T}_M)$ to have all countable powers of $1$ (even when $M$ is not noetherian), while being easier to show than properly defining the two functions $\text{lgcd}$ and $\text{red}$.

**Lemma 4.16.** If $M$ is both left-cancellative up to invertibles on the left and right-coprime-cancellative, and all non-empty countable subsets of $M$ have a unique left-gcd up to invertibles on the right, then $\mathbf{KI}(\mathcal{T}_M)$ has all countable powers of $1$.

**Example 4.17.** When $M$ is a group it is cancellative (because all elements are invertible) and all countable families have a unique left-gcd up to invertibles on the right ($\epsilon$ itself) hence Lemma 4.16 applies and $\text{Trans}_M(\mathcal{L})$ always has a final object.

The same is true when $M$ is a trace monoid (the left-gcd then being the longest common prefix, whose existence is guaranteed by [13, Proposition 1.3]).

Conversely, the monoids given by join semi-lattices are not left-cancellative up to invertibles in general. In $\mathbb{R}_+$ for instance, there are ways to define the functions $\text{lgcd}$ and $\text{red}$ but they may not satisfy condition (4)c, more precisely that $\text{red}(v\Lambda) = \text{red}\Lambda$. This is expected, as there may be several non-isomorphic ways to minimize automata with outputs in these monoids, which is incompatible with the framework of Definition 2.9.

**Proposition 4.12** is reminiscent of a very similar sufficient condition on a semi-ring for deterministic weighted automata to be minimizable in a unique way [15], namely that only an analogue of the red function should exist. The minimal transducer could then again be obtained as the factorization of the unique arrow $\mathcal{A}^{\text{init}}(\mathcal{L}) \to \mathcal{A}^{\text{final}}(\mathcal{L})$, except $\mathcal{A}^{\text{final}}(\mathcal{L})$ would not be final anymore but only weakly final (for any transducer $\mathcal{A}$ recognizing $\mathcal{L}$ there would be an arrow $\mathcal{A} \to \mathcal{A}^{\text{final}}(\mathcal{L})$ but it would not need to be unique), hence our framework would not entail its unicity. However, as further discussed in Section 5.2, these weaker conditions do not really lead to a proper minimization algorithm.

**Lemma 4.16** provides sufficient conditions that are reminiscent of those developed in [17] for the minimization of monoidal transducers. These conditions are stronger than ours but still similar: the output monoid is assumed to be both left- and right-cancellative, which in particular implies the unicity up to invertibles on the right of the left-gcd whose existence is also assumed. They do only require the existence of left-gcds for finite families (whereas we ask for left-gcds of countable families), which would not be enough for our sake since the categorical framework also encompasses the existence of minimal (infinite) automata for non-regular languages, but in practice our algorithms
will only use binary left-gcds as well. We conjecture that, when only those binary
left-gcds exist, the existence of a unique minimal transducer is explained categorically
by the existence of a final transducer in the category of transducers whose states all
recognize functions that are themselves recognized by finite transducers. Where the two
sets of conditions really differ is in the conditions required for the termination of the
algorithms: where we will require right-noetherianity of $M$, they require that if some
$b$ left-divides both some $c$ and some $ac$, then $b$ should also left-divide $ab$. This last
condition leads to better complexity bounds than right-noetherianity, but misses some
otherwise simple monoids that satisfy right-noetherianity, e.g. $\{\alpha, \beta\}^*$ but where we also
let $\alpha$ and $\beta^2$ commute. Conversely, Gerdjikov's main non-trivial example, the tropical
monoid $(\mathbb{R}_+, 0, +)$, is not right-noetherian. It can still be dealt with in our context by
considering submonoids (finitely) generated by the output values of a finite transducer's
transitions, these submonoids themselves being right-noetherian.

**4.4. Factorization systems**

The last ingredient we need in order to be able to apply the framework of Sections 2 and 3 is a factorization system on $\text{Trans}_M(\mathcal{L})$. By Lemma 2.8, it is enough to find a factorization system on $\text{Kl}(\mathcal{T}_M)$.

When $M$ is a free monoid, define $\mathcal{E} = \text{Surj}$ to be the class of those functions $f : X \to M \times Y + 1$ that are surjective on $Y$ and $\mathcal{M} = \text{Inj} \cap \text{Eps} \cap \text{Tot}$ to be the class of those functions $f : X \to M \times Y + 1$ that are total ($f \in \text{Tot}$), injective when corestricted to $Y$ ($f \in \text{Inj}$), and only produce the empty word ($f \in \text{Eps}$). Then the $(\mathcal{E}, \mathcal{M})$-minimal transducer recognizing a function is the one defined by Choffrut [9, 23]: in particular, the fact that the minimal transducer $(\mathcal{E}, \mathcal{M})$-divides all other transducers means (thanks to the surjectivity of $\mathcal{E}$-morphisms and the injectivity of $\mathcal{M}$-morphisms) that it has the smallest possible state-set and produces its outputs as early as possible.

It is thus natural to try and extend this factorization system to $\text{Kl}(\mathcal{T}_M)$ for arbitrary $M$. It is not enough by itself because isomorphisms may produce invertible elements that may be different from $\epsilon$: Iso $\subsetneq$ $\text{Surj} \cap \text{Inj} \cap \text{Eps} \cap \text{Tot}$, yet we need the intersection $\mathcal{E} \cap \mathcal{M}$ to be Iso. $\mathcal{M}$-morphisms must thus be able to produce invertible elements as well. Formally, define therefore $\text{Surj}$, $\text{Inj}$, $\text{Tot}$ and $\text{Inv}$ as follows. For $f : X \to M \times Y + 1$, write $f_1 : X \to M + 1$ for its projection on $M$ and $f_2 : X \to Y + 1$ for its projection on $Y$: we let $f \in \text{Surj}$ whenever $f_2$ is surjective on $Y$, $f \in \text{Inj}$ whenever $f_2$ is injective when corestricted to $Y$, $f \in \text{Tot}$ whenever $f(x) \neq \perp$ for all $x \in X$ and $f \in \text{Inv}$ whenever $f_1(x)$ is either $\perp$ or in $M^\times$. The point is that when replacing $\text{Eps}$ with $\text{Inv}$, we get back that

**Lemma 4.18.** In $\text{Kl}(\mathcal{T}_M)$, $\text{Iso} = \text{Surj} \cap \text{Inj} \cap \text{Inv} \cap \text{Tot}$, and these four classes are all closed under composition (within themselves).

The different ways in which we may distribute these four classes into the two classes
$\mathcal{E}$ and $\mathcal{M}$ leads to not just one but three interesting factorization systems:

**Proposition 4.19.** $(\mathcal{E}_1, \mathcal{M}_1) = (\text{Surj} \cap \text{Inj} \cap \text{Inv}, \text{Tot})$, $(\mathcal{E}_2, \mathcal{M}_2) = (\text{Surj} \cap \text{Inj}, \text{Inv} \cap \text{Tot})$ and $(\mathcal{E}_3, \mathcal{M}_3) = (\text{Surj}, \text{Inj} \cap \text{Inv} \cap \text{Tot})$ are all factorization systems in $\text{Kl}(\mathcal{T}_M)$.
will only use binary left-gcds as well. We conjecture that, when only those binary
left-gcds exist, the existence of a unique minimal transducer is explained categorically
by the existence of a final transducer in the category of transducers whose states all
recognize functions that are themselves recognized by finite transducers. Where the two
sets of conditions really differ is in the conditions required for the termination of the
algorithms: where we will require right-noetherianity of $M$, they require that if some
$b$ left-divides both some $c$ and some $ac$, then $b$ should also left-divide $ab$. This last
condition leads to better complexity bounds than right-noetherianity, but misses some
otherwise simple monoids that satisfy right-noetherianity, e.g. $\{\alpha, \beta\}^*$ but where we also
let $\alpha$ and $\beta^2$ commute. Conversely, Gerdjikov's main non-trivial example, the tropical
monoid $(\mathbb{R}_+, 0, +)$, is not right-noetherian. It can still be dealt with in our context by
considering submonoids (finitely) generated by the output values of a finite transducer's
transitions, these submonoids themselves being right-noetherian.

**4.4. Factorization systems**

The last ingredient we need in order to be able to apply the framework of Sections 2 and 3 is a factorization system on $\text{Trans}_M(\mathcal{L})$. By Lemma 2.8, it is enough to find a factorization system on $\text{KI}(\mathcal{T}_M)$.

When $M$ is a free monoid, define $\mathcal{E} = \text{Surj}$ to be the class of those functions $f: X \to M \times Y + 1$ that are surjective on $Y$ and $\mathcal{M} = \text{Inj} \cap \text{Eps} \cap \text{Tot}$ to be the class of those functions $f: X \to M \times Y + 1$ that are total ($f \in \text{Tot}$), injective when corestricted to $Y$ ($f \in \text{Inj}$), and only produce the empty word ($f \in \text{Eps}$). Then the $(\mathcal{E}, \mathcal{M})$-minimal transducer recognizing a function is the one defined by Choffrut [9, 23]: in particular, the fact that the minimal transducer $(\mathcal{E}, \mathcal{M})$-divides all other transducers means (thanks to the surjectivity of $\mathcal{E}$-morphisms and the injectivity of $\mathcal{M}$-morphisms) that it has the smallest possible state-set and produces its outputs as early as possible.

It is thus natural to try and extend this factorization system to $\text{KI}(\mathcal{T}_M)$ for arbitrary $M$. It is not enough by itself because isomorphisms may produce invertible elements that may be different from $\epsilon$: Iso $\subsetneq$ $\text{Surj} \cap \text{Inj} \cap \text{Eps} \cap \text{Tot}$, yet we need the intersection $\mathcal{E} \cap \mathcal{M}$ to be Iso. $\mathcal{M}$-morphisms must thus be able to produce invertible elements as well. Formally, define therefore $\text{Surj}$, $\text{Inj}$, $\text{Tot}$ and $\text{Inv}$ as follows. For $f: X \to M \times Y + 1$, write $f_1: X \to M + 1$ for its projection on $M$ and $f_2: X \to Y + 1$ for its projection on $Y$: we let $f \in \text{Surj}$ whenever $f_2$ is surjective on $Y$, $f \in \text{Inj}$ whenever $f_2$ is injective when corestricted to $Y$, $f \in \text{Tot}$ whenever $f(x) \neq \perp$ for all $x \in X$ and $f \in \text{Inv}$ whenever $f_1(x)$ is either $\perp$ or in $M^\times$. The point is that when replacing $\text{Eps}$ with $\text{Inv}$, we get back that

**Lemma 4.18.** In $\text{KI}(\mathcal{T}_M)$, $\text{Iso} = \text{Surj} \cap \text{Inj} \cap \text{Inv} \cap \text{Tot}$, and these four classes are all closed under composition (within themselves).

The different ways in which we may distribute these four classes into the two classes
$\mathcal{E}$ and $\mathcal{M}$ leads to not just one but three interesting factorization systems:

**Proposition 4.19.** $(\mathcal{E}_1, \mathcal{M}_1) = (\text{Surj} \cap \text{Inj} \cap \text{Inv}, \text{Tot})$, $(\mathcal{E}_2, \mathcal{M}_2) = (\text{Surj} \cap \text{Inj}, \text{Inv} \cap \text{Tot})$ and $(\mathcal{E}_3, \mathcal{M}_3) = (\text{Surj}, \text{Inj} \cap \text{Inv} \cap \text{Tot})$ are all factorization systems in $\text{KI}(\mathcal{T}_M)$.
The factorization system we choose to define the minimal M-transducer is $(\mathcal{E}_3, \mathcal{M}_3) =$ (Surj, Inj $\cap$ Inv $\cap$ Tot), because it generalizes the factorization system that defines the minimal transducer (with output in a free monoid). It will be our main factorization system, and as such from now on we reserve the notation $(\mathcal{E}, \mathcal{M})$ for it.

**Theorem 2.12** and **Proposition 2.10** show that $(\mathcal{E}, \mathcal{M})$ indeed gives rise to a useful notion of minimal transducer.

**Corollary 4.20.** When $\mathrm{KI}(\mathcal{T}_M)$ has all countable powers of 1, the $(\mathcal{E}, \mathcal{M})$-minimal transducer recognizing a $(\mathrm{KI}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$ is well-defined and has state-set $S^{\min} = \{\mathrm{red}(w^{-1}\mathcal{L}) \mid w \in A^*\} \cap (M + 1)_*^{A^*}$, initial state $s_0^{\min} = \mathrm{red}\,\mathcal{L}$, initialization value $v_0^{\min} = \mathrm{lgcd}\,\mathcal{L}$, termination function $t^{\min}(\Lambda) = \Lambda(e)$ and transition functions $\mathrm{red}(w^{-1}\mathcal{L}) \odot^{\min} a = (\mathrm{lgcd}((wa)^{-1}\mathcal{L}), \mathrm{red}((wa)^{-1}\mathcal{L}))$. It is characterized by the property that all its states are reachable from the initial state and recognize distinct left-coprime functions.

Why are $(\mathcal{E}_1, \mathcal{M}_1)$ and $(\mathcal{E}_2, \mathcal{M}_2)$ also interesting then? They do not give rise to useful notions of minimality, but they show that the computation of Obs can be split into substeps. Indeed, since $\mathcal{E}_1 \subset \mathcal{E}_2 \subset \mathcal{E}_3$ (and equivalently $\mathcal{M}_1 \supset \mathcal{M}_2 \supset \mathcal{M}_3$), $(\mathcal{E}_i, \mathcal{M}_i)_{1 \le i \le 3}$ is a quaternary factorization system:

**Corollary 4.21.** For every $\mathrm{KI}(\mathcal{T}_M)$-arrow $f: X \to Y$, there is a unique (up to isomorphisms) factorization of $f$ into

$$X \xrightarrow{f_1} Z_1 \xrightarrow{f_2} Z_2 \xrightarrow{f_3} Z_3 \xrightarrow{f_4} Y$$

such that $f_1 \in \mathcal{E}_1$, $f_2 \in \mathcal{E}_2 \cap \mathcal{M}_1$, $f_3 \in \mathcal{E}_3 \cap \mathcal{M}_2$ and $f_4 \in \mathcal{M}_3$.

Note how we respectively write $\dashrightarrow_1$, $\dashrightarrow_2$, $\dashleftarrow_1$ and $\dashleftarrow_2$ for arrows in $\mathcal{E}_1$, $\mathcal{E}_2$, $\mathcal{M}_1$ and $\mathcal{M}_2$ (but stick with $\dashrightarrow$ and $\dashleftarrow$ for arrows in $\mathcal{E} = \mathcal{E}_3$ and $\mathcal{M} = \mathcal{M}_3$).

Intuitively, this results means that the computation of any $f$ can be factored into four parts: first forgetting some inputs ($f_1$ belongs to Surj $\cap$ Inj $\cap$ Inv but need not belong to Tot), then producing non-invertible elements of the output monoid ($f_2$ belongs to Surj $\cap$ Inj $\cap$ Tot but need not belong to Inv), then merging some inputs together ($f_3$ belongs to Surj $\cap$ Inv $\cap$ Tot but need not belong to Inj) and finally embedding the result into a bigger set ($f_4$ belongs to Inv $\cap$ Inj $\cap$ Tot but need not belong to Surj).

In particular, the $\mathcal{E}$-quotient $\mathrm{Reach} \mathcal{A} \dashrightarrow \mathrm{Obs}(\mathrm{Reach} \mathcal{A})$ factors as follows.

**Definition 4.22.** Given an M-transducer $\mathcal{A}$ recognizing the $(\mathrm{KI}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$, define Total $\mathcal{A}$ and Prefix $\mathcal{A}$ to be the $(\mathcal{E}_1, \mathcal{M}_1)$- and $(\mathcal{E}_2, \mathcal{M}_2)$-factorizations of the final arrow $\mathrm{Reach} \mathcal{A} \dashrightarrow \mathcal{A}^{\mathrm{final}}(\mathcal{L})$:

$$\mathrm{Reach} \mathcal{A} \dashrightarrow_1 \mathrm{Total} \mathcal{A} \dashrightarrow_2 \mathrm{Prefix} \mathcal{A} \dashrightarrow_2 \mathrm{Min} \mathcal{L} \dashrightarrow \mathcal{A}^{\mathrm{final}}(\mathcal{L})$$

In practice, if $\mathcal{A} = (S, (u_0, s_0), t, \odot)$,

* $\mathrm{Reach} \mathcal{A}$ has state-set the set of states in $S$ that are reachable from $s_0$;
The factorization system we choose to define the minimal M-transducer is $(\mathcal{E}_3, \mathcal{M}_3) =$ (Surj, Inj $\cap$ Inv $\cap$ Tot), because it generalizes the factorization system that defines the minimal transducer (with output in a free monoid). It will be our main factorization system, and as such from now on we reserve the notation $(\mathcal{E}, \mathcal{M})$ for it.

**Theorem 2.12** and **Proposition 2.10** show that $(\mathcal{E}, \mathcal{M})$ indeed gives rise to a useful notion of minimal transducer.

**Corollary 4.20.** When $\mathrm{KI}(\mathcal{T}_M)$ has all countable powers of 1, the $(\mathcal{E}, \mathcal{M})$-minimal transducer recognizing a $(\mathrm{KI}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$ is well-defined and has state-set $S^{\min} = \{\mathrm{red}(w^{-1}\mathcal{L}) \mid w \in A^*\} \cap (M + 1)_*^{A^*}$, initial state $s_0^{\min} = \mathrm{red}\,\mathcal{L}$, initialization value $v_0^{\min} = \mathrm{lgcd}\,\mathcal{L}$, termination function $t^{\min}(\Lambda) = \Lambda(e)$ and transition functions $\mathrm{red}(w^{-1}\mathcal{L}) \odot^{\min} a = (\mathrm{lgcd}((wa)^{-1}\mathcal{L}), \mathrm{red}((wa)^{-1}\mathcal{L}))$. It is characterized by the property that all its states are reachable from the initial state and recognize distinct left-coprime functions.

Why are $(\mathcal{E}_1, \mathcal{M}_1)$ and $(\mathcal{E}_2, \mathcal{M}_2)$ also interesting then? They do not give rise to useful notions of minimality, but they show that the computation of Obs can be split into substeps. Indeed, since $\mathcal{E}_1 \subset \mathcal{E}_2 \subset \mathcal{E}_3$ (and equivalently $\mathcal{M}_1 \supset \mathcal{M}_2 \supset \mathcal{M}_3$), $(\mathcal{E}_i, \mathcal{M}_i)_{1 \le i \le 3}$ is a quaternary factorization system:

**Corollary 4.21.** For every $\mathrm{KI}(\mathcal{T}_M)$-arrow $f: X \to Y$, there is a unique (up to isomorphisms) factorization of $f$ into

$$X \xrightarrow{f_1} Z_1 \xrightarrow{f_2} Z_2 \xrightarrow{f_3} Z_3 \xrightarrow{f_4} Y$$

such that $f_1 \in \mathcal{E}_1$, $f_2 \in \mathcal{E}_2 \cap \mathcal{M}_1$, $f_3 \in \mathcal{E}_3 \cap \mathcal{M}_2$ and $f_4 \in \mathcal{M}_3$.

Note how we respectively write $\dashrightarrow_1$, $\dashrightarrow_2$, $\dashleftarrow_1$ and $\dashleftarrow_2$ for arrows in $\mathcal{E}_1$, $\mathcal{E}_2$, $\mathcal{M}_1$ and $\mathcal{M}_2$ (but stick with $\dashrightarrow$ and $\dashleftarrow$ for arrows in $\mathcal{E} = \mathcal{E}_3$ and $\mathcal{M} = \mathcal{M}_3$).

Intuitively, this results means that the computation of any $f$ can be factored into four parts: first forgetting some inputs ($f_1$ belongs to Surj $\cap$ Inj $\cap$ Inv but need not belong to Tot), then producing non-invertible elements of the output monoid ($f_2$ belongs to Surj $\cap$ Inj $\cap$ Tot but need not belong to Inv), then merging some inputs together ($f_3$ belongs to Surj $\cap$ Inv $\cap$ Tot but need not belong to Inj) and finally embedding the result into a bigger set ($f_4$ belongs to Inv $\cap$ Inj $\cap$ Tot but need not belong to Surj).

In particular, the $\mathcal{E}$-quotient $\mathrm{Reach} \mathcal{A} \dashrightarrow \mathrm{Obs}(\mathrm{Reach} \mathcal{A})$ factors as follows.

**Definition 4.22.** Given an M-transducer $\mathcal{A}$ recognizing the $(\mathrm{KI}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$, define Total $\mathcal{A}$ and Prefix $\mathcal{A}$ to be the $(\mathcal{E}_1, \mathcal{M}_1)$- and $(\mathcal{E}_2, \mathcal{M}_2)$-factorizations of the final arrow $\mathrm{Reach} \mathcal{A} \dashrightarrow \mathcal{A}^{\mathrm{final}}(\mathcal{L})$:

$$\mathrm{Reach} \mathcal{A} \dashrightarrow_1 \mathrm{Total} \mathcal{A} \dashrightarrow_2 \mathrm{Prefix} \mathcal{A} \dashrightarrow_2 \mathrm{Min} \mathcal{L} \dashrightarrow \mathcal{A}^{\mathrm{final}}(\mathcal{L})$$

In practice, if $\mathcal{A} = (S, (u_0, s_0), t, \odot)$,

* $\mathrm{Reach} \mathcal{A}$ has state-set the set of states in $S$ that are reachable from $s_0$;
* Total $\mathcal{A}$ has state-set $S'$ the set of states in $S$ that recognize a function defined for at least one word (in particular if $\mathcal{A}$ recognizes $\perp^{A*}$ then $(u_0, s_0)$ is set to $\perp$);

* Prefix $\mathcal{A} = (S', (u_0 \lgcd(\mathcal{L}_{s_0}), s_0), t', \odot')$, where $\mathcal{L}_s$ is the function recognized from a state $s \in S$ in $\mathcal{A}$, is obtained from Total $\mathcal{A}$ by setting $t'(s) = \lgcd(\mathcal{L}_s)^{-1}t(s)$ and $s \odot' a = (\lgcd(\mathcal{L}_s)^{-1}(s \circ a) \lgcd(\mathcal{L}_{s \circ a}), s \circ a)$;

* Min $\mathcal{L} \cong \text{Obs}(\text{Reach} \mathcal{A})$ is obtained from Prefix $\mathcal{A}$ by merging two states $s_1$ and $s_2$ whenever they recognize functions that are equal up to invertibles on the left in Prefix $\mathcal{A}$, that is when $\text{red}(\mathcal{L}_{s_1}) = \text{red}(\mathcal{L}_{s_2})$ in $\mathcal{A}$.

In particular, these four steps (computing Reach $\mathcal{A}$, Total $\mathcal{A}$, Prefix $\mathcal{A}$ and finally Obs $\mathcal{A}$) match exactly the four steps into which all the algorithms for minimizing (possibly monoidal) transducers are decomposed [4, 7, 9, 15, 17].

**Example 4.23.** For the transducer $\mathcal{A}$ of Figure 2 seen as a transducer with output in the free commutative monoid $\Sigma^*$, the corresponding minimal transducer $\text{Min} \mathcal{L}$ is computed step-by-step in Figure 3.

Notice in particular how in Figure 3b both the functions recognized by the states 1 and 3 are left-divisible by $\alpha$ hence $\alpha$ is pulled back to the initialization value in Figure 3c. This would not have happened had $M$ been the free monoid $\Sigma^*$, and the corresponding minimal transducer would have been different.

<figure><img src="image_9.png" /><figcaption>Figure 3: Increasingly small transducers recognizing the same function as the transducer of Figure 2 when $M = \Sigma^*$</figcaption></figure>

# 5. Algorithms on monoidal transducers

Assume now that $M$ is right-noetherian, left-cancellative up to invertibles on the left and right-coprime-cancellative, and that non-empty countable families of elements of $M$
• Total $\mathcal{A}$ has state-set $S'$ the set of states in $S$ that recognize a function defined for at least one word (in particular if $\mathcal{A}$ recognizes $\perp^{A*}$ then $(u_0, s_0)$ is set to $\perp$);

• Prefix $\mathcal{A} = (S', (u_0 \lgcd(\mathcal{L}_{s_0}), s_0), t', \odot')$, where $\mathcal{L}_s$ is the function recognized from a state $s \in S$ in $\mathcal{A}$, is obtained from Total $\mathcal{A}$ by setting $t'(s) = \lgcd(\mathcal{L}_s)^{-1}t(s)$ and $s \odot' a = (\lgcd(\mathcal{L}_s)^{-1}(s \circ a) \lgcd(\mathcal{L}_{s \circ a}), s \circ a)$;

• Min $\mathcal{L} \cong \text{Obs}(\text{Reach} \mathcal{A})$ is obtained from Prefix $\mathcal{A}$ by merging two states $s_1$ and $s_2$ whenever they recognize functions that are equal up to invertibles on the left in Prefix $\mathcal{A}$, that is when $\text{red}(\mathcal{L}_{s_1}) = \text{red}(\mathcal{L}_{s_2})$ in $\mathcal{A}$.

In particular, these four steps (computing Reach $\mathcal{A}$, Total $\mathcal{A}$, Prefix $\mathcal{A}$ and finally Obs $\mathcal{A}$) match exactly the four steps into which all the algorithms for minimizing (possibly monoidal) transducers are decomposed [4, 7, 9, 15, 17].

**Example 4.23.** For the transducer $\mathcal{A}$ of Figure 2 seen as a transducer with output in the free commutative monoid $\Sigma^*$, the corresponding minimal transducer Min $\mathcal{L}$ is computed step-by-step in Figure 3.

Notice in particular how in Figure 3b both the functions recognized by the states 1 and 3 are left-divisible by $\alpha$ hence $\alpha$ is pulled back to the initialization value in Figure 3c. This would not have happened had $M$ been the free monoid $\Sigma^*$, and the corresponding minimal transducer would have been different.

<figure><img src="image_11.png" /><figcaption>Figure 3: Increasingly small transducers recognizing the same function as the transducer of Figure 2 when $M = \Sigma^*$</figcaption></figure>

# 5. Algorithms on monoidal transducers

Assume now that $M$ is right-noetherian, left-cancellative up to invertibles on the left and right-coprime-cancellative, and that non-empty countable families of elements of $M$
all have a left-gcd that is unique up to invertibles on the right. Thanks to Lemma 4.16, Theorem 2.12 then tells us that the minimal $M$-transducer recognizing a $(\mathbf{KI}(\mathcal{T}_M), 1, 1)$-language $\mathcal{L}$ always exists (and it is given by Corollary 4.20), but it does not tell us how to compute it (in finite time). This section thus discusses two algorithms for computing the minimal transducer, respectively instantiating Algorithms 1 and 2: the first one takes as input two oracles $\text{EVAL}_\mathcal{L}$ and $\text{EQUIV}_\mathcal{L}$ and learns $\text{Min}\,\mathcal{L}$ (Section 5.1), while the second one takes as input any finite transducer recognizing $\mathcal{L}$ and transforms it into $\text{Min}\,\mathcal{L}$ (Section 5.2). The right-noetherianity of $M$ guarantees that these algorithms will terminate when the minimal transducer has finite state-set:

**Lemma 5.1.** An object $X$ of $\mathbf{KI}(\mathcal{T}_M)$ is $M$-noetherian if and only if it is a finite set, in which case $\text{length}_{\mathcal{M}}(m : Y \to X) = |X| - |Y|$.

**Lemma 5.2.** An object $X$ of $\mathbf{KI}(\mathcal{T}_M)$ is $\mathcal{E}$-artinian if and only if it is a finite set and either $M$ is right-noetherian or $X = \emptyset$, in which case $\text{colength}_{\mathcal{E}}(e : X \dasharrow Y) = |X| - |Y| + \text{rk } e$ where $\text{rk } e = \sum_{e(x)=(v,y)} \text{rk } v$.

Given a function $\Lambda \in (M + 1)_*^I$, we write $\text{rk}\,\Lambda = \text{rk}(\text{lgcd}\,\Lambda)$ and, finally, given a transducer $\mathcal{A}$, we then write $\text{rk}\,\mathcal{A} = \sum_{s \in (\text{Total}\,\mathcal{A})(\text{st})} \text{rk}\,\mathcal{L}_s$, $|\mathcal{A}|_{\text{st}}$ for the cardinal of the state-set of $\mathcal{A}$, and $|\mathcal{A}|_{\to}$ for the number of transitions $s \odot a \neq \perp$ in $\mathcal{A}$. We will use these notions to express the complexity of our algorithms.

These two algorithms are modular in $M$: they only require to be given functions computing basic operations and may then be implemented the same no matter the structure of $M$. Hence we also assume that we are given access to the following oracles: one that checks for equality in $M$; $\otimes : M + 1 \to M + 1 \to M + 1$ that computes the product in $M + 1$ (with $v \perp = \perp v = \perp$); $\wedge : M + 1 \to M + 1 \to M + 1$ that computes a left-gcd of two elements of $M + 1$ (with $v \wedge \perp = \perp \wedge v = \perp$); $\text{LEFTDIVIDE}$ that takes as input $\delta, v \in M$ and computes a $v \in M$ such that $v = \delta v$ (or outputs $v = \perp$ when $v = \perp$) or fails when there is no such $v$; and $\text{UP TO INV LEFT}$ that takes as input two families $v, v \in M^I$ indexed by a finite set $I$ and outputs a $\chi \in M^\times$ such that $v = \chi v$ if such a $\chi$ exists, and $\perp$ otherwise. Note that when $M$ is right-cancellative this last oracle may be derived from another oracle that only tests for equality up to invertibles of two elements of $M$ (and not two families), and when $M$ has no non-trivial invertible elements these two oracles just test for equality.

## 5.1. Learning

In this section, we thus first describe an algorithm that, given a subsequential function $\mathcal{L}$, learns $\text{Min}\,\mathcal{L}$ using two oracles: $\text{EVAL}_\mathcal{L}$ takes as input a word $w \in A^*$ and computes $\mathcal{L}(\vdash w \triangleleft)$; and $\text{EQUIV}_\mathcal{L}$ takes as input a transducer $\mathcal{A}$, decides whether it recognizes $\mathcal{L}$, and if not outputs a counter-example word $w \in A^*$ such that $(\mathcal{A} \circ \iota)(\vdash w \triangleleft) \neq \mathcal{L}(\vdash w \triangleleft)$.

When $M$ is a free monoid, Vilar gives a very natural generalization of Angluin's $L^*$ algorithm for learning automata that does exactly this [1, 29]. Here we generalize Vilar's algorithm to arbitrary $M$ by instantiating Algorithm 1 within $\mathbf{KI}(\mathcal{T}_M)$: we get Algorithm 4. This instantiation is possible because the conditions on $M$ also guarantee