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. Ã Q done A(st) was already an isomorphism and nothing changed; or it was not, in which case Q Ã was added to Q done so that Q done = Q done ∪ Q Ã right after, and we would thus still get that κ Q done Q Ã Q done A(st) had become an E-morphism

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 [START_REF] Fischer | Crafting a Compiler. Crafting a Compiler with C[END_REF], linguistics [START_REF] Kaplan | Regular Models of Phonological Rule Systems[END_REF], or natural language processing [START_REF] Knight | Applications of Weighted Automata in Natural Language Processing[END_REF].

Two subsequential 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 ouput 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 [START_REF] Choffrut | Minimizing Subsequential Transducers: A Survey[END_REF].

Active learning of transducers. Another method for computing a minimal transducer is to learn it through Vilar's algorithm [START_REF] Miguel | Query Learning of Subsequential Transducers[END_REF], a generalization to transducers of Angluin's L*-algorithm, which learns the minimal deterministic automaton recognizing a language [START_REF] Angluin | Learning Regular Sets from Queries and Counterexamples[END_REF]. 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. Consider for instance the partial function recognized by the minimal transducer A of Figure 1a over the input alphabet A = {a, b} and output alphabet Σ = {α, β, γ}. We write this function L( -) : A * → Σ * {⊥} and let e ∈ A * and ∈ Σ * stand for the respective empty words over these two alphabets. To learn A, the algorithm maintains two subsets Q, T ⊂ A * of prefixes and suffixes of input words, and keeps track of the restriction of L( -) to words in QT ∪ 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 ∈ Q and input letter a ∈ A there is a candidate state q ∈ A that we can choose to build an a-transition from q to q ; consistency holds when for any q ∈ Q and a ∈ 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 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 ∈ Q to correspond to the initial state, and the output value produced by the initial transition to be the longest common prefix Λ(e) of each L( et ) for t ∈ T , here Λ(e) = α. But the longest common prefix Λ(a) of each L( at ) for t ∈ T is γαβα, of which Λ(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 Λ(a)! This is a first kind of consistency issue, which we solve by adding a to T , turning Λ(e) into the empty output word and Λ(a) into γαβ. Now Q = {e} and T = {e, a}. The initial transition should go into the state corresponding to e and output Λ(e) = , the final transition from this state should output Λ(e) -1 L( e ) = α, the a-transition from this state should output Λ(e) -1 Λ(a) = γαβ, and this a-transition followed by a final transition should output Λ(e) -1 L( a ) = γαβα. This a-transition should moreover lead to a state from which another a-transition followed by a final transition outputs Λ(a) -1 L( aa ) = γβα 2 : in particular, it cannot lead back to the state corresponding to e, because γβα 2 = γαβα. 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 A on QT ∪ 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 L( bb ) = ⊥ and yet for which our hypothesis transducer produced the output word α 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 (Λ(e) -1 L( et ) = Λ(b) -1 L( bt ) for all t ∈ 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 (L( ebe ) = α yet L( bbe ) = ⊥ 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 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 Σ = {α, β, γ}, that is of elements of the free monoid Σ * . 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 independant 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 αβ = βα, 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 [START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF], 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 [START_REF] Eisner | Simpler and More General Minimization for Weighted Finite-State Automata[END_REF], 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 (nonmonoidal) 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 A of Figure 1a with the assumption that αβ = βα would first produce 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 Σ * / ∼ and recognized by a finite monoidal transducer, and yet so that, when this function is considered to have output in Σ * , Vilar's algorithm may not even terminate if, when answering membership queries, the oracle does not carefully choose the representatives in Σ * of each equivalence class in Σ * / ∼ (the idea of finding such an example was suggested by an anonymous reviewer whom the author thanks): Lemma 1.1. Let A = {a}, Σ = {α, β, γ}, let Σ/∼ be the monoid Σ * with the additional assumption that αβ = βα and let π : Σ * → Σ/∼ be the corresponding quotient. Consider the function f : A * → Σ/∼ that maps a n to α n β n γ = (αβ) n γ.

f is recognized by a finite transducer with outputs in Σ/∼, yet learning a transducer that recognizes any function f : A * → Σ * such that f = f • π with Vilar's algorithm will never terminate if the oracle replies to the membership query for a n with α n β n γ ∈ Σ * (which differs from (αβ) n γ in Σ * but not in Σ/∼).

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 [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF]. This framework encompasses both Angluin's and Vilar's algorithms, as well as a similar algorithm for weighted automata [START_REF] Bergadano | Learning Behaviors of Automata from Multiplicity and Equivalence Queries[END_REF][START_REF] Bergadano | Learning Behaviors of Automata from Multiplicity and Equivalence Queries[END_REF]. We use this specific framework because, while others exist, they either do not encompass transducers or require stronger assumptions [START_REF] Barlocco | Coalgebra Learning via Duality[END_REF][START_REF] Urbat | Automata Learning: An Algebraic Approach[END_REF][START_REF] Gerco Van Heerdt | Learning Automata with Side-Effects[END_REF].

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 [START_REF] Dorsch | Efficient Coalgebraic Partition Refinement[END_REF][START_REF] Wißmann | A Coalgebraic View on Reachability[END_REF], 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 the 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.

Categorical approach to automata minimization and learning

In this section we recall (and extend) the definitions and results of Colcombet, Petrişan and Stabile [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF][START_REF] Petrişan | Automata Minimization: A Functorial Approach[END_REF]. We assume basic knowledge of category theory [START_REF] Mac | Categories for the Working Mathematician[END_REF], but we also focus on the example of deterministic complete automata, on the counter-example of nondeterministic automata, and mention the examples of weighted automata and (classical) transducers, the latter being detailed and generalized in Section 4. We then say that a functor A :

Automata and languages as functors

I → C is a (C, X, Y )-automaton when A(in) = X and A(out) = Y .
The input category represents the basic structure of automata as transition systems: st represents the state-space, the initial configuration, a the transitions along the corresponding letters, and the output values associated to each state.

Example 2.2 (automata and transducers)

. If 1 = { * } and 2 = {⊥, }, a (Set, 1, 2)automaton A is a (possibly infinite) deterministic complete automaton: it is given by a state-set S = A(st), transition functions A(a) : S → S for each a ∈ A, an initial state s 0 = A( )( * ) ∈ S and a set of accepting states

F = {s ∈ S | A( )(s) = } ⊆ 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 stateset S = A(st), transition relations A(a) ⊆ S × S, a set of initial states A( ) ⊆ 1 × S ∼ = S and a set of accepting states A(

) ⊆ S × 1 ∼ = S.
If K is a field we may see K-weighted automata as functors A from I to the category of K-vector-spaces, KVec, such that A(in) = A(out) = K, and if B is an output alphabet, we may see deterministic transducers as functors from I to the Kleisli category of free algebras for the monad

T B * X = B * ×X +1, Kl(T B * ), such that A(in) = A(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 L : O → C, where O, the category of observable inputs, is the full subcategory of I on in and out. In other words, a language is the data of two objects X = L(in) and Y = L(out) in C (in which case we speak of a (C, X, Y )-language), and, for each word w ∈ A * , of a morphism L( w ) : X → Y . In particular, composing an automaton A : I → C with the embedding ι : O → I, we get the language L A = A • ι recognized by A.

Example 2.4 (languages for classical automata). The language recognized by a (Set, 1, 2)automaton A is the language recognized by the corresponding complete deterministic automaton: for a given w ∈ A * , L A ( w )( * ) = if and only if w belongs to the language, and the equality L A ( w ) = A( w ) = A( )A(w)A( ) 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 L( w ) ⊆ 1 × 1, where * is related to itself if and only if w belongs to L. The language recognized by a (Rel, 1, 1)automaton is thus the language recognized by the corresponding non-deterministic automaton.

Similarly, when C is KVec or Kl(B * × -+ 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 C and a language L : O → C, we define the category Auto(L) whose objects are (C, L(in), L(out))automata A recognizing L, and whose morphisms A → A are natural transformations whose components on L(in) and L(out) are the identity. In other words, a morphism of automata is given by a morphism f :

A(st) → A (st) in C such that A ( ) = f • A( ) (it preserves the initial configuration), A (a) • f = f • A(a) (it
commutes with the transitions), and A ( ) • f = A( ) (it preserves the output values).

Factorization systems and the minimal automaton recognizing a language

Definition 2.6 (factorization system). In a category C, a factorization system (E, M) is the data of a class of E-morphisms (represented with ) and a class of M-morphisms (represented with ) M such that every arrow f in C may be factored as f = m • e with m ∈ M and e ∈ E, E ∩ M is exactly the class Iso of isomorphisms of C, E and M are both stable under composition, and for every commuting diagram

X Y 1 Y 2 Z e u v d m where m ∈ M and e ∈ E there is a unique d : Y 1 → Y 2 such that u = d • e and v = m • d.
Example 2.7. (some factorization systems) In Set and KVec, surjective and injective functions and linear transformations form factorization systems (Surj, Inj) such that a map f : X → Y factors through its image f (X) ⊆ Y . In the Kleisli category for the monad X → B * × 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 E-morphisms those relations r : X → Y such that every y ∈ Y is related to some x ∈ X by r, and M-morphisms the graphs of injective functions (i.e. m ∈ M if and only if there is an injective function f such that (x, y) ∈ m ⇐⇒ y = f (x)). A relation r : X → Y then factors through the subset {y ∈ Y | ∃x ∈ X, (x, y) ∈ R} ⊆ Y . We write this factorization system (Surj, Det ∩ Inj) (for surjections and deterministic injections). Lemma 2.8 (factorization system on Auto(L) [START_REF] Petrişan | Automata Minimization: A Functorial Approach[END_REF]Lemma 2.8]). Given L : I → C and (E, M) a factorization system on C, Auto(L) has a factorization given by those natural transformations whose components are respectively E-and M-morphisms.

Because of this last result, we use (E, M) to refer both to a factorization on C and to its extensions to categories of automata. Definition 2.9 (minimal object). When a category C, equipped with a factorization system (E, M), has both an initial object I and a final object F (for every object X there is exactly one morphism I → X and one morphism X → F ), we define its (E, M)minimal object Min to be the one that (E, M)-factors the unique arrow I → F as I Min F . For every object X we also define Reach X and Obs X by the (E, M)factorizations I Reach X X and X Obs X F : when the morphism I → X is in E we say X is reachable and when the morphism X → F we say it is observable. Proposition 2.10 ((E, M)-minimality [START_REF] Petrişan | Automata Minimization: A Functorial Approach[END_REF]Lemma 2.3]). The minimal object of a category C is unique up to isomorphism, and is (E, M)-minimal in the sense that it (E, M)divides every other object X, meaning we have commuting diagrams

X I

Reach X Obs X F

Min

In particular, Min ∼ = Obs(Reach X) ∼ = Reach(Obs X). Since Set is complete and cocomplete, the category of (Set, 1, 2)-automata recognizing a language L : I A * → Set has an initial, a final and a minimal object. The initial automaton has state-set A * , initial state ∈ A * , transition functions δ a (w) = wa and accepting states the w ∈ A * such that w is in L. Similarly, the final automaton has state-set 2 A * , initial state L, transition functions δ a (L) = a -1 L and accepting states the L ∈ 2 A * such that is in 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 (E, M)-minimality ensures that it is the complete deterministic automaton with the smallest state-set that recognizes L : it is in particular finite as soon as L is recognized by a finite automaton.

For the same reason, the category of (KVec, K, K)-automata recognizing a language L : I → KVec also has a minimal object that corresponds to the minimal K-weighted automaton recognizing L [START_REF] Schützenberger | On the Definition of a Family of Automata[END_REF]. The example of transducers seen as automata over the Kleisli category for the monad X → B * × 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 (Kl(T ), 1, 1)-automata : with the right factorization system, we retrieve Choffrut's minimal transducer [START_REF] Choffrut | Minimizing Subsequential Transducers: A Survey[END_REF].

On the contrary, there is no good notion of a unique minimal non-deterministic automaton recognizing a regular ((Rel, 1, 1)-)language L. Auto(L) does have an initial and a final object: the initial automaton is the initial deterministic automaton recognizing 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 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 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 L : I → C with A countable,

• if C has all countable copowers of L(in) then Auto(L) has an initial object A init (L) with A init (L)(st) = A * L(in);

• dually if C has all countable powers of L(out) then Auto(L) has a final object

A f inal (L) with A f inal (L)(st) = A * L(out);
• hence when both of the previous items hold and C is equipped with a factorization system (E, M), Auto(L) has an (E, M)-minimal object Min L.

This is summarized by the diagram below, where κ and π are the canonical inclusion and projections.

A * L(in) L(in) Min(L)(st) L(out) A * L(out) [L( w )] w∈A * w∈A * κwa κ L( w ) w∈A * π w∈A * πaw
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 (E-artinian and M-noetherian objects [10, Definition 24]). In a category C equipped with a factorization system (E, M), an object X is said to be Mnoetherian if every strict chain of M-subobjects is finite: if

(x n : X n X) n∈N and (m n : X n X n+1 ) form the commutative diagram X X 0 X 1 • • • x 0 m 0 x 1 m 1
then only finitely many of the m n 's may not be isomorphisms. Dually,

X is E-artinian if X op is E op -noetherian in C op , that is if every strict cochain of 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 C. Definition 2.14 (co-E-and M-length). For a fixed x 0 : X 0 X, we call M-length of x 0 , written length M x 0 , the (possibly infinite) supremum of the length (the number of pairs of consecutive subobjects) of strict chains of M-subobjects of X that start with x 0 . Dually, we call co-E-length of an E-quotient x 0 : X X 0 the (possibly infinite) quantity colength E x 0 = length E op x op 0 .

Example

(X Y ) = length Inj (Y X) = dim X -dim Y .
Note that the co-E-and 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-Eand -M-length are computed in Lemmas 5.1 and 5.2.

Learning

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

Our goal is to compute Min L with the help of two oracles: Eval L , when queried with a word w ∈ A * , outputs L( w ); while Equiv L , when queried with a (C, L(in), L(out))automaton A, decides whether A recognizes L, and, if not, outputs a counter-example w ∈ A * such that L( w ) = (A • ι)( w ).

For (Set, 1, 2)-automata, if the language is regular this problem is solved using Angluin's L* algorithm [START_REF] Angluin | Learning Regular Sets from Queries and Counterexamples[END_REF]. It works by maintaining a set of prefixes Q and of suffixes T and, using Eval L , incrementally building a table L : Q × (A ∪ { }) × T → 2 that represents partial knowledge of L until it can be made into a (minimal) automaton. This automaton is then submitted to Equiv L : if it is accepted it must be Min L, otherwise the counter-example is added to Q and the algorithm loops over. The FunL* algorithm (Algorithm 1) generalizes this to arbitrary (C, L(in), L(out)), and in particular also encompasses Vilar's algorithm for learning (non-monoidal) transducers which was described in Section 1 [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF].

Instead of maintaining a table, it maintains a biautomaton: if

Q ⊆ A * is prefix- closed (wa ∈ Q ⇒ w ∈ Q) and T ⊆ A * is suffix-closed (aw ∈ T ⇒ w ∈ T ), a (Q, T )-
biautomaton is, similarly to an automaton, a functor A : I Q,T → C, where I Q,T is now the category freely generated by the diagram

in st 1 st 2 out q a t
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 ∈ QA and the right one whenever at ∈ AT .

st 1 st 2 st 2 out in st 1 st 1 st 2 t q (qa) a a (at)
A (Q, T )-biautomaton may thus process a prefix in Q and get in a state in A(st 1 ), follow a transition along A ∪ { } to go in A(st 2 ), and output a value for each suffix in T . The category of biautomata recognizing L Q,T (L restricted to words in QT ∪ QAT ) is written Auto Q,T (L). A result similar to Theorem 2.12 also holds for biautomata [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF]Lemma 18], and the initial and final biautomata are then made of finite copowers of L(in) and finite powers of L(out) (when these exist). Writing Q/T for the (E, M)factorization of the canonical morphism [L( qt )] q∈Q t∈T : Q L(in) → T L(out), the minimal biautomaton recognizing L Q,T then has state-spaces (Min L Q,T )(st 1 ) = Q/(T ∪ AT ) and (Min L Q,T )(st 2 ) = (Q ∪ QA)/T . The table, represented by the morphism [L( qt )] q∈Q t∈T , may be fully computed using Eval L , and hence so can be the minimal (Q, T )-biautomaton.

A biautomaton B can then be merged into a hypothesis (C, L(in), L(out))-automaton precisely when B( ) is an isomorphism, i.e. both an E-and an 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 maitained to be merged into a hypothesis automaton. Theorem 2.16 [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF]Theorem 26]). Algorithm 1 is correct. If (Min L)(st) is Mnoetherian and 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 Equiv L ) is linear in the size of (Min L)(st) (itself defined through Definition 2.14).

An algorithm for minimizing (C, X, Y )-automata

We now fix a (C, X, Y )-language L and a factorization system (E, M) of C, and assume that C has all the countable copowers of L(in) and all the countable powers of L(out) so that Theorem 2.12 applies and Auto(L) has initial and final objects A init and A f inal .

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

Algorithm 1 The FunL*-algorithm

Input: Eval L and Equiv L Output: Min(L)

1: Q = T = { } 2: loop 3: while min Q,T is not an isomorphism do 4: if min Q,T is not an E-morphism then 5: find qa ∈ QA such that Q/T (Q ∪ {qa})/T is not an E-morphism 6:
add qa to Q 7:

else if min Q,T is not an M-morphism then 8: find at ∈ AT such that Q/(T ∪ {at}) Q/T is not an M-morphism 9:
add at to T 10:

end if 11:
end while

12: merge Min L Q,T into H Q,T L 13:
if Equiv L (H Q,T L) outputs some counter-example w then 14:

add w and its prefixes to Q 15:

else 16: return H Q,T 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.

The basic algorithm

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

Lemma 3.1 ([23, Remark 2.5]). The dual of the (E, M)-factorization Obs A in Auto(L) is the (M op , E op )-factorization Reach A op in Auto(L op ).
Remark 3.2. Note that Lemma 3.1 does not mean that, for a fixed category C along with a factorization system (E, M) and the two objects X and Y , having an algorithm that computes the (E, M)-factorization Reach for (C, X, Y )-automata is equivalent to having one that computes the (E, M)-factorization Obs for (C, X, Y )-automata as well. Indeed, C op and C itself may differ greatly, and even if C were self-dual (hence C = C op ), E and M op or X and Y op could still differ, meaning that computing the (E, M)-and (M op , E op )-factorizations would not necessarily be equivalent. For instance, Rel is selfdual but, as Example 3.13 shows, Reach A may be computed for automata A : I → Rel while Obs A may not.

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

Definition 3.3. Given a set Q ⊆ A * , write e Q : Q L(in) Q/A(st) and m Q : Q/A(st) A(st) for the factorization of the arrow [A( q)] q∈Q : Q L(in) → A(st) in C.
Notice how for Q = A * we get by Theorem 2.12 that A * /A(st) = (Reach A)(st), which is exactly the object we want to compute (along with its embedding into A(st), given by m A * ). But we also want to compute the transition arrows on this object: Lemma 3.4. (similar to [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF]Lemma 31]

) For any w ∈ A * and Q ⊆ A * such that Qw = {qw | q ∈ Q} ⊆ Q , there is a unique morphism κ Q Q•w A(w) : Q/A(st) → Q /A(st) making the two squares in the diagram below commute. Moreover, if uv = w and Qw ⊆ Q v ⊆ Q , then κ Q Q •v A(v) • κ Q Q•u A(u) = κ Q Q•w A(w) . Q L(in) Q /A(st) A(st) Q L(in) Q/A(st) A(st) e Q m Q κ Q Q•w = q∈Q κqw e Q m Q κ Q Q•w A(w) A(w)
We fix the notation κ Q Q•w A(w) for the canonical morphisms of Lemma 3.4, and simply write κ

Q Q A(st) = κ Q Q•
A( ) when w is the empty word. In particular, we have that

(Reach A)(a) = κ A * A * •a A(a)
. Of course, we can't just compute A * /A(st) and its associated morphisms as a factorization of the morphism from A * A(in), as this coproduct is infinite: in Set with A(in) = 1, it corresponds to the set A * itself. Instead our strategy will be to find some finite subset Q that describes Reach A entirely, i.e. such that we have an isomorphism

κ A * Q A(st) : Q/A(st) ∼ = A * /A(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 = ∅ and add words to it until the κ Q∪{qa} Q A(st) are isomorphisms for all q ∈ Q and a ∈ 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 κ

Q∪QA Q A(st)
and then that so is κ

A * Q A(st) . Finally, notice that if Q ⊆ Q then κ Q Q A(st)
is already an M-morphism (by [8, Proposition 14.9(1)], because A( ) = id is an M-morphism): in Set, the Q-reachable states are in particular Q -reachable. Hence to check that κ Q∪{qa} Q A(st) is an isomorphism we only really need to check that it is an E-morphism (since E ∩ M is exactly the class of isomorphisms): in Set, that the set of Q-reachable states surjects onto the set of (Q ∪ {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.

Algorithm 2 A categorical algorithm for computing Reach Input: an automaton

A : I → C Output: Reach A 1: set todo ← {{ }} 2: set Q done ← ∅ 3: while there is a Q ∈ todo do 4: remove Q from todo 5: if κ Q done Q Q done A(st) : Q done /A(st) Q done Q/A(st) is not an E-morphism then 6: choose a partition P of A and set todo ← todo {Q Ã | Ã ∈ P } 7: set Q done ← Q done Q 8:
end if 9: end while 10: return the automaton

A(in) Q done /A(st) A(out) e Q done •κ A( )•m Q done κ Q done ∪Q done a Q done A(st) -1 • κ Q done ∪Q done a Q done •a A(a)
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 ⊆ A * it may also be more efficient to compute (Q done ∪ Qa)/A(st) in a batch instead of computing each (Q done ∪ {qa})/A(st) for q ∈ 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 A(st) is M-noetherian, Algorithm 2 is correct, terminates, and the condition on line 5 is satisfied at most length M (m ∅ : ∅/A(st) A(st)) times.

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/A(st) incrementally: in Set, it does not tell us that the set of (Q ∪ {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 C.

Lemma 3.7. For every Q, Q ⊆ A * , if the coproduct Q/A(st) + Q /A(st) exists, [m Q , m Q ] : Q/A(st) + Q /A(st) → A(st) (E, M)-factors into m Q Q • κ Q Q Q A(st) , κ Q Q Q A(st) : Q/A(st) + Q A(st) (Q Q ) A(st) A(st) Lemma 3.8. For every Q ⊆ A * , A(a) • m Q (E, M)-factors into m Qa • κ Qa Q•a A(st) : Q/A(st) Qa/A(st) A(st).
When the binary coproducts of the Q/A(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 /A(st) → A(st) is the already-visited subobject of A(st), while each (m Q , Ã) in the to-do list corresponds to a subobject m Q of A(st) along with a subset of transitions from this subobject that we have to consider next. We also keep track of e Q done • κ , which represents the initial transition into the already-visited subobject m Q done . Corollary 3.9. Assume that for every finite Q, Q ⊆ A * , the coproduct Q/A(st) + Q /A(st) exists.

Then, if A(st) is M-noetherian, Algorithm 3 is correct, terminates, and the condition on line 12 is satisfied at most length M (m : { }/A(st) A(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 κ

Q done Q Ã Q done A(st)
is an E-morphism, that is whether the set of Q done -reachable states surjects onto that of (Q done Q Ã)-reachable states, but it does not tell us that to check this it is enough to just check whether the Q Ã-reachable states had already been visited. Again, this can be expressed categorically with an additional assumption on the factorization system (E, M).

Lemma 3.10. If κ Q Q Q A(st) : Q/A(st) (Q Q )/A(st) is an isomorphism then m Q = m Q • κ Q Q Q A(st) -1 • κ Q Q Q A(st) Algorithm 3 A detailed version of Algorithm 2 Input: an automaton A : I → C Output: Reach A 1: compute e { } : A(in) { }/A(st) and m { } : { }/A(st) A(st) 2: choose a partition P of A and set todo ← {(m , Ã) | Ã ∈ P } 3: set m Q done ← m { } 4: set e Q done • κ ← e { } 5: while there is a pair (m Q , Ã) ∈ todo do 6:
remove (m Q , Ã) from todo end for 10:

compute m Q Ã : Q Ã A(st) A(st) by factoring [m Qa ] a∈ Ã as in Lemma 3.7 11: compute κ Q done Q Ã Q done A(st) : Q done /A(st) Q done Q Ã A(st) and m Q done Q Ã : Q done Q Ã A(st) A(st) by factoring [m Q done , m Q Ã] as in Lemma 3.7 12: if κ Q done Q Ã Q done A(st) is not an E-morphism then 13: choose a partition P of A and set todo ← todo {(m Q Ã, Ã ) | Ã ∈ P } 14: set m Q done ← m Q Q Ã 15: set e Q done • κ ← κ Q done Q Ã Q done A(st) • e Q done • κ : A(in) → Q Q Ã A(st) 16:
end if 17: end while 18: return the automaton

A(in) Q done /A(st) A(out) e Q done •κ A( )•m Q done κ Q done ∪Q done a Q done A(st) -1 • κ Q done ∪Q done a Q done a A(st) • κ Q done a Q done •a A(a) with κ Q done a Q done •a A(a) : Q done /A(st) Q done a/A(st) computed by factoring A(a) • m Q done as in Lemma 3.8
Conversely, in the context of Lemma 3.7, assume also that all split epimorphisms are in E (if e • s = id for some e, s then e ∈ E).

If m Q factors as m Q • f for some f : Q/A(st) → (Q Q )/A(st) then κ Q Q Q A(st) is an isomorphism. Corollary 3.11. When E contains all split epimorphisms, it is enough to check on line 12 of Algorithm 3 that m Q Ã : Q Ã A(st) A(st) doesn't factor through m Q done : Q done /A(st)
A(st). In particular, line 11 can be moved inside the if statement on line 12.

Examples

Example 3.12 (Graph traversal). Fix a (Set, 1, 2)-automaton A with finite state-set. Since Set is cocomplete and E = 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 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 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 M-subobject m Q : Q/A(st)

A(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 done , and a to-do list of states and transitions to consider next (the factorization of a morphism 1 → A(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 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. κ

Q done {qa} Q done A(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 A. Example 3.13 (Graph traversal for non-deterministic automata). As explained in Example 2.11, the factorization system (Surj, Det ∩ 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 A, Reach (Surj,Det∩Inj) A is the restriction of A to its reachable states. Since Rel has arbitrary coproducts, Reach A may be computed using Algorithm 3 (by Corollary 3.9) with the partitions of 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 ⊆ X × Y for which there is a surjective function f : X → Y with codomain some subset X ⊆ X such that (x, y) ∈ r ⇐⇒ y = f (x)): the condition on line 12 would then be satisfied at most as many times as there are states in 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 A with finite stateset. Since Set is complete and M = 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 A chosen to be the trivial partition P = {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 A.

The resulting algorithm is similar to Moore's algorithm [START_REF] Moore | Gedanken-Experiments on Sequential Machines[END_REF], a standard algorithm for merging the equivalent states of an automaton: an E-quotient of e T : A(st)

T /A(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 ≤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 ≤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 • 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 ≤n+1 through the factorization of e A ≤n , e A n+1 , which means computing the intersection of every two equivalence class of e A ≤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 ≤n then e A ≤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 ≤n and initial and final states as well as transition functions inherited from those of 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 ≤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 [START_REF] Hopcroft | AN n Log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATON[END_REF], 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 A(out) = 2 and the possibility to compute cardinals of objects.

Example 3.15 (Minimization of weighted automata). Given a field K, fix a (KVec, K, K)automaton A with finite-dimensional state-space. Since KVec is cocomplete and E = 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 A(st) times.

The resulting algorithm computes Reach A, i.e. an automaton whose configurations are exactly those that are reachable in A: v ∈ (Reach A)(st) if and only if there are λ 1 , . . . , λ k ∈ K and w 1 , . . . , w k ∈ A * such that v = k i=1 λ i A( w). An M-subobject of A(st) is a subvector space of A(st) or equivalently a set of independant vectors of A(st). The algorithm thus maintains m Q done : Q/A(st) → A(st), a set of independant vectors of A(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}/A(st) → A(st) (the factorization of a morphism K → A(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 A(a) and then checks whether m {qa} factors through m Q done hence solves a linear system to check whether the vector m {qa} is a linear combination of those generating m Q done . If this is not the case, (m {qa} , a ) is added to the to-do list for each a ∈ A and m {qa} is added to the basis of m Q done to form the basis of m Q done {qa} . Once the to-do list is empty, the algorithm returns the automaton with state-space Q done /A(st) whose initial configuration, transition functions and final values are inherited from those of A through a change of basis.

Since the algorithm terminates, it only considers finite subsets Q of 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 K on itself and swaps Surj and Inj. We are thus in the very special case mentioned in Remark 3.2 where the algorithm that computes the transpose of Obs A is exactly the one that computes Reach as described above, but applied to the transpose of A.

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.

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, M , ⊗ M ) is a set M equipped with a binary operation ⊗ M (often called the product) that is associative (∀u, v, w ∈ M, u ⊗ M (v ⊗ M w) = (u ⊗ M v) ⊗ M w) and has M as unit element (∀u ∈ M, u ⊗ M M = M ⊗ M u = u).
When non-ambiguous, it is simply written (M, , ⊗) or even M , and the symbol for the binary operation may be omitted.

The dual of (M, , ⊗), written (M op , op , ⊗ op ), has underlying set M op = M and identity op = , but symmetric binary operation :

∀u, v ∈ M, u ⊗ op v = v ⊗ 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 leftproperty 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 ∈ M such that xy = , and y is then called the right-inverse of x. It is left-invertible when it is right-invertible in M 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 × .

Two families (u i ) i∈I and (v i ) i∈I indexed by some non-empty set I are equal up to invertibles on the left when there is some invertible x ∈ M such that ∀i ∈ I, u i = xv i . Definition 4.3 (divisibility). An element u of a monoid M left-divides a family w = (w i ) i∈I of M indexed by some set I when there is a family (v i ) i∈I such that ∀i ∈ 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 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 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 ω, 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∈I and (v i ) i∈I of M indexed by some set I and for any w ∈ M , u = v as soon as wu i = wv i for all i ∈ I. If this only implies u i = xv i for some x ∈ M × , 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 ∈ M and any left-coprime family (w i ) i∈I indexed by some set I, u = v as soon as uw i = vw i for all i ∈ I.

Definition 4.5 (noetherianity)

. A monoid M is right-noetherian when for any sequences (u n ) n∈N and (v n ) n∈N of M such that v n = v n+1 u n for all n ∈ N, there is some n ∈ 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∈N that satisfies v n = v n+1 u n for a sequence (v n ) n∈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 • • • u 0 right-divides v 0 ). Note that rk(uv) ≤ rk u + rk v, and rk : M → 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. 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.

Lemma 4.6. M is right-noetherian if and only if for any sequences

(u n ) n∈N and (v n ) n∈N of M such that v n = v n+1 u n for all n ∈ N, there is some n ∈ N such that for all i ≥ n, u i is invertible.
The free commutative monoid A over A has elements the functions A → N with finite support, product (f ⊗ g)(a) = f (a) + g(a) and unit the zero function a → 0. It is commutative (f ⊗ g = g ⊗ f ) hence is its own dual : the divisibility relation is the pointwise order inherited from 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 rightnoetherian.

A final monoid of interest is (E, ∨, ⊥) for E any join-semilattice with a bottom element ⊥. 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 = R + .

Monoidal transducers as functors

In the rest of this paper we fix a countable input alphabet A and an output monoid (M, , ⊗). To differentiate between elements of A * and elements of M , we write the former with Latin letters (a, b, c, . . . for letters and u, v, w, . . . for words) and the latter with Greek letters (α, β, γ, . . . for generating elements and υ, ν, ω, . . . for general elements). In particular the empty word over A is denoted e while the unit of M is still written .

We write T M for the monad on Set given by T M X = M × X + 1 = (M × X) {⊥} (in Haskell, this monad is the composite of the Maybe monad and a Writer monad). Its unit η : Id ⇒ T M is given by η X (x) = ( , x) and its multiplication µ : T 2 M ⇒ T M is given by µ X ((υ, (ν, x))) = (νυ, x), µ X ((υ, ⊥)) = ⊥ and µ X (⊥) = ⊥. Recall that the Kleisli category Kl(T M ) for the monad T M has objects the sets and arrows X Y (notice the different symbol) those functions f

† : T M X → T M Y such that f † (⊥) = ⊥, f † (υ, x) = (υν, y) when f † ( , x) = (ν, y) and f † (υ, x) = ⊥ when f ( , x) = ⊥:
in particular, such an arrow is entirely determined by its restriction f : X → 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 id T M X = η † X : T M X → T M X, and the composition of two arrows X Y Z is given by the composition of the underlying functions

T M X → T M Y → 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 (Kl(T M ), 1, 1)-automata from Definition 2.1. An M -transducer (or monoidal transducer over M , or simply transducer) is thus a functor A : I → Kl(T M ) with A(in) = A(out) = 1, and a morphism of transducers is a natural transformation between the corresponding functors whose restriction to O is the identity. Similarly given a (Kl(T M ), 1, 1)-language L, Trans M (L) is the category of monoidal transducers recognizing L.

In practice, a monoidal transducer A is thus a tuple (S, (υ 0 , s 0 ), t, (-a) a∈A ) where:

• S is the state-set;

• (υ 0 , s 0 ) = A( ) ∈ M × S + 1 is the (possibly undefined) pair of the initialization value and initial state;

• t = A( ) : S → M + 1 is the partial termination function;

• s a = A(a)(s) ∈ M × S + 1 may be undefined, and we write -• a : S → S + 1 for the second component of -a, the partial transition function along a, and -a : S → M + 1 for its first component, the partial production function along a

Similarly, the language L = A • ι recognized by this monoidal transducer is thus a function L :

A * → M + 1 given by L(a 1 • • • a n ) = t † ((υ 0 , s 0 ) † a 1 † • • • † a n )
, and a morphism between two transducers (S 1 , (υ 1 , s 1 ), t 1 , 1 ) and

(S 2 , (υ 2 , s 2 ), t 2 , 2 ) is a function f : S 1 → M × S 2 + 1 such that f † (υ 1 , s 1 ) = (υ 2 , s 2 ), t 1 (s) = t † 2 (f (s)) and f † (s a) = f † (s) † 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 Σ * , with Σ = {α, β}. Formally, it is given by S = {1, 2, 3, 4}; (υ 0 , s 0 ) = ( , 1); t(1) = α, t 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 [START_REF] Choffrut | Minimizing Subsequential Transducers: A Survey[END_REF][START_REF] Petrişan | Automata Minimization: A Functorial Approach[END_REF]. To study the notion of minimal monoidal transducer, it is thus natural to try to follow this framework as well.

The initial and final monoidal transducers recognizing a function

To apply the framework of Sections 2 and 3 to (Kl(T M ), 1, 1)-automata, we need three ingredients in Kl(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, Kl(T M ) has arbitrary coproducts as well as any Kleisli category for a monad over a category with coproducts does [START_REF] Szigeti | On Limits and Colimits in the Kleisli Category[END_REF]. Hence Theorem 2.12 applies: Corollary 4.11 (initial transducer). For any (Kl(T M ), 1, 1)-language L, Trans M (L) has an initial object A init (L) with state-set S init = A * , initial state s init 0 = e, initialization value υ init 0 = , termination function t init (w) = L( w )( * ) and transition function w init a = ( , wa). Given any other transducer A = (S, (υ 0 , s 0 ), t, ) recognizing L, the unique transducer morphism f : A init (L) =⇒ A is given by the function f :

A * → M × S + 1 such that f (w) = A( w)( * ) = (υ 0 , s 0 ) † w.
Similarly, to get a final transducer in Trans M (L) for some L, Theorem 2.12 tells us that it is enough for Kl(T M ) to have all countable powers of 1. This is in particular what happens for classical transducers, when M is a free monoid [START_REF] Petrişan | Automata Minimization: A Functorial Approach[END_REF]. Hence we study the properties of a monoid M such that Kl(T M ) has these powers.

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 Kl(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 Kl(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 lgcd and red.

Lemma 4.16. If M is both left-cancellative up to invertibles on the left and rightcoprime-cancellative, and all non-empty countable subsets of M have a unique left-gcd up to invertibles on the right, then Kl(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 ( itself) hence Lemma 4.16 applies and Trans M (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 [START_REF] Cori | Automates et commutations partielles[END_REF]Proposition 1.3]).

Conversely, the monoids given by join semi-lattices are not left-cancellative up to invertibles in general. In R + for instance, there are ways to define the functions lgcd and red but they may not satisfy condition (4)c, more precisely that red(υΛ) = red Λ. 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 [START_REF] Eisner | Simpler and More General Minimization for Weighted Finite-State Automata[END_REF], 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 A init (L) → A f inal (L), except A f inal (L) would not be final anymore but only weakly final (for any transducer A recognizing L there would be an arrow A → A f inal (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 [START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF] 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 rightcancellative, 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. {α, β} * but where we also let α and β 2 commute. Conversely, Gerdjikov's main non-trivial example, the tropical monoid (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.

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 Trans M (L). By Lemma 2.8, it is enough to find a factorization system on Kl(T M ).

When M is a free monoid, define E = Surj to be the class of those functions f : X → M × Y + 1 that are surjective on Y and M = Inj ∩ Eps ∩ Tot to be the class of those functions f : X → M × Y + 1 that are total (f ∈ Tot), injective when corestricted to Y (f ∈ Inj), and only produce the empty word (f ∈ Eps). Then the (E, M)-minimal transducer recognizing a function is the one defined by Choffrut [START_REF] Choffrut | Minimizing Subsequential Transducers: A Survey[END_REF][START_REF] Petrişan | Automata Minimization: A Functorial Approach[END_REF]: in particular, the fact that the minimal transducer (E, M)-divides all other transducers means (thanks to the surjectivity of E-morphisms and the injectivity of 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 Kl(T M ) for arbitrary M . It is not enough by itself because isomorphisms may produce invertible elements that may be different from : Iso Surj ∩ Inj ∩ Eps ∩ Tot, yet we need the intersection E ∩ M to be Iso. M-morphisms must thus be able to produce invertible elements as well. Formally, define therefore Surj, Inj, Tot and Inv as follows. For f : X → M × Y + 1, write f 1 : X → M + 1 for its projection on M and f 2 : X → Y + 1 for its projection on Y : we let f ∈ Surj whenever f 2 is surjective on Y , f ∈ Inj whenever f 2 is injective when corestricted to Y , f ∈ Tot whenever f (x) = ⊥ for all x ∈ X and f ∈ Inv whenever f 1 (x) is either ⊥ or in M × . The point is that when replacing Eps with Inv, we get back that Lemma 4.18. In Kl(T M ), Iso = Surj ∩ Inj ∩ Inv ∩ 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 E and M leads to not just one but three interesting factorization systems:

Proposition 4.19. (E 1 , M 1 ) = (Surj ∩ Inj ∩ Inv, Tot), (E 2 , M 2 ) = (Surj ∩ Inj, Inv ∩ Tot)
and (E 3 , M 3 ) = (Surj, Inj ∩ Inv ∩ Tot) are all factorization systems in Kl(T M ).

The factorization system we choose to define the minimal M -transducer is (E 3 , M 3 ) = (Surj, Inj ∩ Inv ∩ 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 (E, M) for it.

Theorem 2.12 and Proposition 2.10 show that (E, M) indeed gives rise to a useful notion of minimal transducer. Corollary 4.20. When Kl(T M ) has all countable powers of 1, the (E, M)-minimal transducer recognizing a (Kl(T M ), 1, 1)-language L is well-defined and has state-set

S min = {red(w -1 L) | w ∈ A * } ∩ (M + 1) A *
* , initial state s min 0 = red L, initialization value υ min 0 = lgcd L, termination function t min (Λ) = Λ(e) and transition functions red(w -1 L) min a = (lgcd((wa) -1 L), red((wa) -1 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 (E 1 , M 1 ) and (E 2 , 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

E 1 ⊂ E 2 ⊂ E 3 (and equivalently M 1 ⊃ M 2 ⊃ M 3 ), (E i , M i ) 1≤i≤3
is a quaternary factorization system: Corollary 4.21. For every Kl(T M )-arrow f : X Y , there is a unique (up to isomorphisms) factorization of f into

X Z 1 Z 2 Z 3 Y 1 f 1 1 2 f 2 2 f 3 f 4 such that f 1 ∈ E 1 , f 2 ∈ E 2 ∩ M 1 , f 3 ∈ E 3 ∩ M 2 and f 4 ∈ M 3 .
Note how we respectively write M 1 and M 2 (but stick with and for arrows in E = E 3 and M = 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 ∩ Inj ∩ Inv but need not belong to Tot), then producing non-invertible elements of the output monoid (f 2 belongs to Surj ∩ Inj ∩ Tot but need not belong to Inv), then merging some inputs together (f 3 belongs to Surj ∩ Inv ∩ Tot but need not belong to Inj) and finally embedding the result into a bigger set (f 4 belongs to Inv ∩ Inj ∩ Tot but need not belong to Surj).

In particular, the E-quotient Reach A Obs(Reach A) factors as follows.

Definition 4.22. Given an M -transducer A recognizing the (Kl(T M ), 1, 1)-language L, define Total A and Prefix A to be the

(E 1 , M 1 )-and (E 2 , M 2 )-factorizations of the final arrow Reach A A f inal (L): Reach A Total A Prefix A Min L A f inal (L) 1 2 1 2
In practice, if A = (S, (u 0 , s 0 ), t, ),

• Reach A has state-set the set of states in S that are reachable from s 0 ;

• Total A has state-set S the set of states in S that recognize a function defined for at least one word (in particular if A recognizes ⊥ A * then (u 0 , s 0 ) is set to ⊥);

• Prefix A = (S , (u 0 lgcd(L s 0 ), s 0 ), t , ), where L s is the function recognized from a state s ∈ S in A, is obtained from Total A by setting t (s) = lgcd(L s ) -1 t(s) and s a = (lgcd(L s ) -1 (s a) lgcd(L s•a ), s • a);

• Min L ∼ = Obs(Reach A) is obtained from Prefix 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 A, that is when red(L s 1 ) = red(L s 2 ) in A.

In particular, these four steps (computing Reach A, Total A, Prefix A and finally Obs A) match exactly the four steps into which all the algorithms for minimizing (possibly monoidal) transducers are decomposed [START_REF] Béal | Computing the Prefix of an Automaton[END_REF][START_REF] Breslauer | The Suffix Tree of a Tree and Minimizing Sequential Transducers[END_REF][START_REF] Choffrut | Minimizing Subsequential Transducers: A Survey[END_REF][START_REF] Eisner | Simpler and More General Minimization for Weighted Finite-State Automata[END_REF][START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF].

Example 4.23. For the transducer A of Figure 2 seen as a transducer with output in the free commutative monoid Σ , the corresponding minimal transducer Min 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 α hence α is pulled back to the initialization value in Figure 3c. This would not have happened had M been the free monoid Σ * , and the corresponding minimal transducer would have been different.

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 (Kl(T M ), 1, 1)language 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 Eval L and Equiv L and learns Min L (Section 5.1), while the second one takes as input any finite transducer recognizing L and transforms it into Min L (Section 5.2). The right-noetherianity of M guarantees that these algorithms will terminate when the minimal transducer has finite state-set: Given a function Λ ∈ (M + 1) I * , we write rk Λ = rk(lgcd Λ) and, finally, given a transducer A, we then write rk A = s∈(Total A)(st) rk L s , |A| st for the cardinal of the state-set of A, and |A| → for the number of transitions s a = ⊥ in A. We will use these notions to express the complexity of our algorithms.

Lemma 5.1. An object X of Kl(T M ) is M-noetherian if and only if it is a finite set, in which case length M (m : Y X) = |X| -|Y |. Lemma 5.2. An object X of Kl(T M ) is E-artinian if
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 ; ⊗ :

M + 1 → M + 1 → M + 1 that computes the product in M + 1 (with υ⊥ = ⊥υ = ⊥); ∧ : M + 1 → M + 1 → M + 1 that
computes a left-gcd of two elements of M + 1 (with υ ∧ ⊥ = ⊥ ∧ υ = ⊥); LeftDivide that takes as input δ, υ ∈ M and computes a ν ∈ M such that υ = δν (or outputs ν = ⊥ when υ = ⊥) or fails when there is no such ν; and UpToInvLeft that takes as input two families υ, ν ∈ M I indexed by a finite set I and outputs a χ ∈ M × such that υ = χν if such a χ exists, and ⊥ 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. the existence of the minimal biautomata described in Section 2.3. To the best of the author's knowledge, no other algorithm in the literature solves the problem of learning transducers whose output monoid is not free.

Algorithm 4 is very similar to Vilar's algorithm, the main difference being that the longest common prefix is now the left-gcd and that, in some places, testing for equality is now testing for equality up to invertibles on the left. It thus maintains two sets Q and T that are respectively prefix-closed and suffix-closed, and tables Λ :

Q × (A ∪ {e}) → M + 1 and R : Q × (A ∪ {e}) × T → M + 1.
They satisfy that, for all a ∈ A ∪ {e}, Λ(q, a)R(q, a, t) = L( qat ) and R(q, a, •) is left-coprime (hence Λ(q, a) is a left-gcd of (L( qat )) t∈T ).

The algorithm then extends Q and T until some closure and consistency conditions are satisfied, and then build a hypothesis transducer H(Q, T ) using Λ and R: its state-set S can be constructed by, starting with e ∈ Q, picking as many q ∈ Q so that R(q, e, •) is never ⊥ T and so that, for any two distinct q, q ∈ S, R(q, e, •) and R(q , e, •) are not equal up to invertibles on the left; it then has initial state e ∈ Q, initialization value Λ(e, e), termination function t = q ∈ S → R(q, e, e) and transition function given by q a = (LeftDivide(Λ(q, e), Λ(q, a))χ, q ) for q, q ∈ S such that R(q, a, •) = χR(q , e, •). The algorithm then adds the counter-example given by Equiv L (H(Q, T )) to Q and builds a new hypothesis automaton until no counter-example is returned and H(Q, T ) = Min L. The three kinds of consistency issues that arise are again explained by the quaternary factorization system of Section 4.4, as the three conditions on line 10 hold when some morphism respectively does not belong to Tot, belongs to Tot but not Inv or belongs to Tot ∩ Inv but not Inj. Algorithm 4 also differs from Vilar's original learning algorithm in a small additional way: the latter also keeps track of the left-gcds of every Λ(q, ã) where ã ranges over A ∪ {e} and q ∈ Q is fixed, and checks for consistency issues accordingly. This is a small optimization of the algorithm that does not follow immediately from the categorical framework. In Section 1 we thus actually provided an example run of our version of the algorithm when the output monoid is a free monoid. It also provides example runs of our algorithm for non-free output monoids, as quotienting the output monoid will only remove closure and consistency issues and make the run simpler. For instance letting α commute with β for the transducer of Figure 1a would have removed the closure issue and the need to add a to Q while learning the corresponding monoidal transducer, and letting α also commute with γ would have removed the first consistency issue to arise and the need to add a to T .

Minimization

To transform a transducer A = (S, (u 0 , s 0 ), t, ) recognizing L into Min L, a first method is of course to use Algorithm 4, implementing Eval L using A and Equiv L by trying Algorithm 4 The FunL*-algorithm for monoidal transducers Input: Eval L and Equiv L Output: Min M (L)

1: Q = T = {e} 2: for a ∈ A ∪ {e} do 3:
Λ(e, a) = Eval L (a)

4:
R(e, a, e) = 5: end for 6: loop

7: if there is a qa ∈ QA such that ∀q ∈ Q, χ ∈ M × , R(q, a, •) = χR(q , e, •) then 8: add qa to Q 9:
else if there is an at ∈ AT such that • either there is a q ∈ Q such that R(q, a, t) = ⊥ but R(q, e, T ) = ⊥ T ;

• or there is a q ∈ Q such that Λ(q, e) does not left-divide Λ(q, a)R(q, a, t);

• or there are q, q ∈ Q and χ ∈ M × such that R(q, e, T ) = χR(q , e, T ) but LeftDivide(Λ(q, e), Λ(q, a)R(q, a, t)) = χLeftDivide(Λ(q , e), Λ(q , a))R(q , a, t)) build H(Q, T ) using Λ and R 13:

if Equiv L (H Q,T (L)) outputs some counter-example w then 14:

add w and its prefixes to Q update Λ and R using Eval L 20: end loop to compute a morphism of transducers Reach A H(Q, T ). But in practice when M is a free monoid this is not the method that is used: there are algorithms designed specifically for minimizing a transducer, surveyed by Choffrut [START_REF] Choffrut | Minimizing Subsequential Transducers: A Survey[END_REF]. These algorithms all decompose the problem into four steps that match exactly those of Definition 4.22.

Computing Reach and Total is straightforward and may be done in linear time using depth-first searches on the underlying graph of A, and this stays true for arbitrary M . The problem of computing Prefix and Obs was first tackled in [START_REF] Eisner | Simpler and More General Minimization for Weighted Finite-State Automata[END_REF], but the solution relied on the existence of an oracle that computes non-trivial left-divisors of countable (but rational) families, and also leaves red Λ over when repeatedly applied to some Λ. In comparison, our instantiation of Algorithm 2 and its dual requires much weaker tools: only UpToInvLeft and the binary ∧.

The resulting algorithm itself is not new, as it is exactly the one described in [START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF]. Our main result relative to minimization is instead that this algorithm can be made to work with not just left-and right-cancellative output monoids: left-cancellativity up to invertibles on the left and right-coprime-cancellativity is enough. Similarly, rightnoetherianity is enough to ensure termination, although the resulting complexity now also depends on the rank of elements of M . We thus do not describe the implementation in detail, but instead only discuss the insights we get through the big picture of the categorical framework, as well as how easy it is to actually retrieve the concrete algorithms for computing Reach, Total, Prefix and Obs.

Computing Reach. Since Kl(T M ) has all coproducts, Corollary 3.9 holds and to compute Reach we may directly use Algorithm 3. Moreover all split epimorphisms in Kl(T M ) are in Surj = E, hence we may also use the optimization of Corollary 3.11. The resulting algorithm is the transducer version of Example 3.12, a depth-or breadth-first search depending on the order in which the to-do list is gone through, and Lemma 5.1 tells us that the complexity is linear in the number of states of A.

There is not much to say here: the instantiation goes smoothly.

Computing Total. The case of Total is more interesting, as instantiating the algorithm from the categorical framework is more troublesome, yet the result is still trivial: to remove the states that recognize the empty function, it is enough to do a depth-or breadth-first search on the underlying graph of the transducer, starting from the states where the termination function is defined and following transitions backwards. Kl(T M ) has all finite products by Proposition 4.12 hence by the dual of Corollary 3.9 we may instantiate this algorithm through the dual of Algorithm 3. But this categorical algorithm tells us to keep track of a (Surj ∩ Inj ∩ Inv)-quotient A(st)

1 A(st)/T , that
is a partial function that tells us for each state s ∈ A(St) whether there is a t ∈ T such that A(t )(s) = ⊥. To compute the factorizations incrementally we would then need to factorize the cartesian products of such functions, which, while correct, is quite unnatural.

A more intuitive way to instantiate the algorithm is to notice that (Surj ∩ Inj ∩ Inv)quotients are exactly the split epimorphisms of Kl(T M ), and, as such, have right inverses.

Keeping track of the right inverse of the quotient A(st) 1 A(st)/T would then mean keeping track of its codomain as a subset of A(st). This is more natural, only now we cannot compute the factorizations incrementally anymore, as we would want to do so by factorizing the coproduct of such embeddings but this is not encompassed by the dual of Lemma 3.7. This obstacle can be overcome by considering the transducer as the transpose of a non-deterministic transducer, i.e. seeing Kl(T M ) op as a subcategory of Kl(P(M op × -)), where P is the powerset monad. With this point of view, the states that recognize a non-empty function are exactly those that are reachable in the non-deterministic reverse transducer: computing Total can be done by reversing the transducer, computing Reach in the category of non-deterministic M op -transducers and reversing the result back. This categorical algorithm yields precisely the graph traversal we were looking for, with the same catch as that of Example 3.13: it does not tell us that transitions along the same letter and to the same state can be considered separately.

However we choose to view this instantiation, the (Surj ∩ Inj ∩ Inv)-codimension of a set is its cardinal, hence we know the main loop will be run at most once for each state of A.

Computing Prefix. The core of the problem is to compute Prefix A knowing Total A, that is to compute the left-gcds of the functions recognized from each state that is reachable and recognizes a non-empty function. Béal and Carton do it by pulling back letters along the transitions of A [START_REF] Béal | Computing the Prefix of an Automaton[END_REF], but this relies crucially on M being a free monoid as the letters to pull back must be produced by every transition going out of a given state. This would for instance not be enough to see that the left-gcd of state 3 in Figure 3b is α (when M is the free commutative monoid). Breslauer does it by computing over-approximations and the length of the left-gcds, and then taking the corresponding prefixes [START_REF] Breslauer | The Suffix Tree of a Tree and Minimizing Sequential Transducers[END_REF], but again this algorithm does not generalize to arbitrary M because it relies crucially on the free monoid being graded.

In the general case, Prefix A may be computed using a fixed-point algorithm, keeping track of a tentative left-gcd l(s) for each state s ∈ A(st) and replacing l(s) with l(s) ∧ a∈A (s a)l(s • a) as long as needed [START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF]Section 4], and this is exactly what we get when we instantiate the dual of Algorithm 3 and the optimization dual to that of Corollary 3.11 for the factorization system (E 2 , M 2 ).

An interesting thing to notice here is that since we start from Total A, we may consider that we are computing the (Surj ∩ Inj, Inv ∩ Tot)-factorization of Total A 1 A f inal (L) in the category of total transducers (those whose final morphism to A f inal is in Tot) and total morphisms between them (the morphisms between them are also in Tot, thanks to [8, Lemma 14.9(1)]). Hence we actually compute a (Surj ∩ Inj ∩ Tot, Inv ∩ Tot)factorization. This is particularly interesting when giving a complexity-bound for the number of times the main loop is run. The (Surj∩Inj)-codimension of some e : X Y is just rk e : the prior knowledge that the transducer was total got rid of the cardinality term. Still, [START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF]Lemma 6] gets a much better complexity result than we do: where we get a complexity linear in rk A, they get one linear in |A(st)|. This is because they use an assumption quite different from right-noetherianity (namely, that if υ left-divides ω and νω then it left-divides νυ) that allows them to prove some kind of pumping lemma for transducers.

Computing Obs. Computing Obs from Prefix A is also straightforward when M is the free monoid as it amounts to minimizing a deterministic automaton, which can be done using Hopcroft's algorithm for instance [START_REF] Choffrut | Minimizing Subsequential Transducers: A Survey[END_REF]. This is still true when M has no nontrivial invertibles, but for arbitrary M it is not as easy: checking whether two states are equivalent amounts to checking for equality of (left-coprime) subsequential functions up to invertibles.

A general algorithm for computing Obs A can be designed by extending Moore's partition refinement algorithm with equality up to invertibles. In a nutshell, this algorithm should maintain a partition of the states into equivalence classes and for every pair of equivalent states an invertible element that witnesses the equivalence, and refine this equivalence as long as needed [START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF]Section 5]. This is, again, exactly the algorithm we get when we instantiate the dual of Algorithm 3 along with the optimization dual to that of Corollary 3.11 for the factorization system (E 3 , M 3 ).

Just as for Prefix we restricted ourselves to the category of total transducers, we can restrict ourselves to the category of onwards transducers (those for which the final morphism to A f inal (L) is in Inv ∩ Tot) and (Inv ∩ Tot)-morphisms between them. In particular, this means the complexity of computing Obs A from Prefix A only depends on the number of states of Total A, and we retrieve the same complexity as that of [START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF]Lemma 13].

Worklist algorithms everywhere. A final insight we get from applying the minimization algorithm of our categorical framework is that the algorithms for computing Reach, Total, Prefix and Obs all share the same structure: they are worklist algorithms, that is fixed-points of an operator on a graph defined by dataflow-style equations on each vertex.

Since the technical details of the algorithm are quite heavy to lay out, we also provide a modular OCaml implementation for right-cancellative output monoids [START_REF] Aristote | Monoidal Transducers Minimization[END_REF] as a proofof-concept (it is in particular not fully optimized), that includes implementations of the oracles for trace monoids, the group Z and products of monoids. It uses the OCamlGraph library [START_REF] Sylvain Conchon | Designing a Generic Graph Library Using ML Functors[END_REF] to represent the underlying graph of a transducer, and its Fixpoint module to implement each of Reach, Total, Prefix and Obs as worklist algorithms: this module only requires the dataflow-style equations and computes the corresponding fixpoint automatically.

Summary and future work

In this work, we extended Colcombet, Petrişan and Stabile's active learning categorical framework with a minimization algorithm, and instantiated it with monoidal transduc-ers. We gave some simple sufficient conditions on the output monoid for the minimal transducer to exist and be unique up to isomorphism, which in particular extend Gerdjikov's conditions for minimization to be possible [START_REF] Gerdjikov | A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)Sequential Transducers[END_REF]. Finally, we described what the active learning algorithm of the categorical framework instantiated to in practice under these conditions, relying in particular on the quaternary factorization system in the output category.

This work was mainly a theoretical excursion and was not motivated by practical examples where monoidal transducers are used. Although we expect them to be useful in concurrency theory and in natural language processing, such examples are thus still to be found. In particular, can monoidal transducers with outputs in trace monoids (and their learning) to programatically schedule jobs, as mentioned in the introduction. We also leave the search for other interesting examples for future work.

Some intermediate results of this work go beyond what the categorical framework currently provides and could be generalized. The use of a quaternary factorization system (or any n-ary factorization system) would split the algorithms into several substeps that should be easier to work with. Here our factorization systems seemed to arise as the image of the factorization system on Set through the monad T M ; generalizing this to other monads could provide meaningful examples of factorization systems in any Kleisli category. Finally, we mentioned in Section 4.3 that a problem with the current framework is that it may only account for the minimization of both finite and infinite transition systems at the same time, and conjectured that we could restrict to only the finite case by working in a subcategory of well-behaved transducers: this subcategory is perhaps an instance of a general construction that has its own version of Theorem 2.12, so as to still have a generic way to build the initial, final and minimal objects.

A. Proofs for Section 1 (Introduction)

Lemma 1.1. Let A = {a}, Σ = {α, β, γ}, let Σ/∼ be the monoid Σ * with the additional assumption that αβ = βα and let π : Σ * → Σ/∼ be the corresponding quotient. Consider the function f : A * → Σ/∼ that maps a n to α n β n γ = (αβ) n γ.

f is recognized by a finite transducer with outputs in Σ/∼, yet learning a transducer that recognizes any function f : A * → Σ * such that f = f • π with Vilar's algorithm will never terminate if the oracle replies to the membership query for a n with α n β n γ ∈ Σ * (which differs from (αβ) n γ in Σ * but not in Σ/∼).

Proof. f is recognized by the Σ/∼-transducer (Definition 4.9) with one state s that is initial, initial value υ 0 = , transition function a s = (αβ, s) and termination function t(s) = γ.

Consider now the run of Vilar's algorithm (Algorithm 4 with M = Σ * and M × = { }) with the oracle answering the membership query for a n with f (a n ) = α n β n γ. We start with Q = T = {e}, Λ(e) = γ, Λ(a) = αβγ and R(e, e) = R(a, e) = , where Λ(w) for w ∈ Q ∪ QA is the longest common prefix of the {f (wt) | t ∈ T } and R(w, t) is the suffix such that f (wt) = Λ(w)R(w, t).

Since Λ(e) = γ is not a prefix of Λ(a) = αβγ, there is a consistency issue and we add a to T . Taking n = 0, we are now in the configuration C n given by Q

= Q n = {a k | k ≤ n}, T = {e, a}, and Λ(a k ) = α k , R(a k , e) = β k γ and R(a k , a) = αβ k+1 γ for every k ≤ n + 1
(since the oracle replies to the membership query for a k with α k β k γ and to that for a k a with α k+1 β k+1 γ).

Suppose now we are in the configuration C n for some n ∈ N. Then there is a closure issue, since for all k ≤ n, R(a k , e) = β k γ = β n+1 γ = R(a n+1 , e). We thus add a n+1 to Q. To compute Λ(a n+2 ), R(a n+2 , e) and R(a n+2 , a), we make a membership query for a n+3 : the oracle answers with f (a n+3 ) = α n+3 β n+3 γ. The longest common prefix of f (a n+2 ) = Λ(a n+1 )R(a n+1 , a) = α n+2 β n+2 γ and f (a n+2 a) = α n+3 β n+3 γ is thus α n+2 , and the corresponding suffixes are R(a n+2 , e) = β n+2 γ and R(a n+2 , a) = αβ n+3 γ: we are now in the configuration C n+1 .

Hence the run of the algorithm never terminates and never even reaches an equivalence query, as it must first go through all the configurations C n for n ∈ N.

B. Proofs for Section 3 (An algorithm for minimizing

(C, X, Y )-automata) Proof. Obs A is given by the (E, M)-factorization A Obs A A f inal in Auto(L). Its dual is thus given by the (M op , E op )-factorization (A f inal ) op (Obs A) op A op in Auto(L) op . But A f inal is final in Auto(L) hence its dual is initial in Auto(L) op . Similarly, (M op , E op ) is a factorization system in Auto(L) op [8, Proposition 14.3], hence (Obs A) op is none other than Reach A op . Lemma 3.4. (similar to [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF]Lemma 31]) For any w ∈ A * and Q

⊆ A * such that Qw = {qw | q ∈ Q} ⊆ Q , there is a unique morphism κ Q Q•w A(w) : Q/A(st) → Q /A(st) making the two squares in the diagram below commute. Moreover, if uv = w and Qw ⊆ Q v ⊆ Q , then κ Q Q •v A(v) • κ Q Q•u A(u) = κ Q Q•w A(w) . Proof. κ Q Q•w A(w) arises immediately by the diagonal fill-in property of (E, M) applied to m Q • e Q • q∈Q κ q = (A(w) • m Q ) • e Q .
Since this diagonal fill-in is unique, by composing these diagrams we get the last equality. Theorem 3.6. If A(st) is M-noetherian, Algorithm 2 is correct, terminates, and the condition on line 5 is satisfied at most length M (m ∅ : ∅/A(st)

A(st)) times.

Proof. We first focus on termination, then on correctness.

Termination. Every time line 7 is executed, the condition on line 5 must hold. Hence if we write Q n for the value of Q done after n executions of line 7, then

Q 0 = ∅ and ( Q n /A(st) Q n+1 /A(st)
) n forms a strict chain of M-subobjects of A(st) (it is strict because the morphisms it contains are not E-morphisms hence not isomorphisms). But A(st) is M-noetherian by assumption hence this chain must be finite and line 7 and thus line 6 must be executed a finite number of times, and in particular at most length M m Q 0 = length M m ∅ times. But we only add at most |A| elements to the to-do list on line 6, hence the while loop is run a finite number of times, in particular at most 1 + |A| length M (m ∅ ) times.

Correctness.

Let us first show some preliminary results. Lemma B.1. Consider the following diagonal fill-in (where g is an M-morphism):

Y 1 Y 1 /Y 2 Y 2 X 1 X 1 /X 2 X 2 ey my f ex mx f /g g f /
g is an M-morphism, and it is an isomorphism if and only if there is an h such that the following diagram commutes:

Y 1 Y 1 /Y 2 X 1 X 1 /X 2 ey h f ex f /g
Proof. f /g is an M-morphism by [8, Proposition 14.9 [START_REF] Angluin | Learning Regular Sets from Queries and Counterexamples[END_REF]]. If it is an isomorphism, then h = ( f /g ) -1 • e y immediately makes the diagram above commute.

Conversely, assume such an h exists and (E, M)-factor it as h = m • e : Y 1 Z X 1 /X 2 . By unicity of the diagonal fill-in, there is an isomorphism χ :

Y 1 /Y 2 ∼ = Z such that e = χ • e y and f /g • m • χ = id. We claim that m • χ is the inverse of f /g : we already have that f /g • m • χ = id, but also g • m x • m • χ • f /g = m y • f /g • m • χ • f /g = m y • f /g = g • m x and m • χ • f /g • e x = m • χ • e y • f = h • f = e x
hence by unicity of the diagonal fill-in (within the square composed of two copies of e x and g

• m x ), m • χ • f /g = id.
Definition B.2 (prefix-closedness). Q ⊆ A * is said to be prefix-closed if it contains the empty word and if for every q ∈ A * and a

∈ A, if qa ∈ Q then q ∈ Q. Proposition B.3. Let Q ⊆ A * be prefix-closed. If κ Q∪QA Q A(st) is an isomorphism, then so is κ A Q A(st) .
Proof. We apply Lemma B.1 and build a morphism h : A * A(in) → Q/A(st) that makes the corresponding diagram commute. We thus let h • κ = e Q • κ (this is possible because Q is prefix-closed hence contains ) and, by induction, for w ∈ A * and a ∈ A we

let h • κ wa = κ Q∪QA Q A(st) -1 • κ Q∪QA Q•a A(a) • h • κ w .
We then have that e Q = h • [κ q ] q∈Q . The proof is by induction on Q, which is possible because Q is prefix-closed. We already have h • κ = e Q • κ by definition, and if h • κ w = e Q • κ w , then for a ∈ A we have

h • κ wa = κ Q∪QA Q A(st) -1 • κ Q∪QA Q•a A(a) • h • κ w = κ Q∪QA Q A(st) -1 • κ Q∪QA Q•a A(a) • e Q • κ w = κ Q∪QA Q A(st) -1 • e Q∪QA • [κ qa ] q∈Q • κ w = κ Q∪QA Q A(st) -1 • e Q∪QA • [κ q ] q∈Q • κ wa = e Q • κ wa Moreover, for all w ∈ A * , we have κ A * Q•w A(w) = κ A * Q∪QA•w A(w) • κ Q∪QA Q A(st) hence κ A * Q•w A(w) • κ Q∪QA Q A(st) -1 = κ A * Q∪QA•w A(w)
and it follows by induction (again, thanks to the prefix-closedness of Q) that

κ A * Q A(st) • h • κ w = κ A * Q•w A(w) • e Q • κ = e A * • [κ qw ] q∈Q • κ = e A * • κ w hence that κ A * Q A(st) • h = e A * .
Lemma B.4 (generalization of [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF]Lemma 40]). For every k in some set K, let

P k ⊆ Q k ⊆ A * be such that κ Q k P k A(st) is an isomorphism. Also assume that Q k ∩ Q k = P k ∩ P k for all k = k ∈ K. Then, κ ∪ K Q k ∪ K P k A(st) is also an isomorphism.
Proof. We apply Lemma B.1 and build h :

∪ K Q k A(in) → ∪ K P k /A(st) . If p ∈ P l for some l ∈ K, set h • κ p = e ∪ K P k • κ p . Otherwise, for q ∈ Q l for some (unique) l ∈ K, set h • κ q = κ ∪ K P k P l A(st) • h l • κ q where h l : Q l A(in) → P l /A(st) witnesses that κ Q l P l A(st) is an isomorphism. We then have by definition h•[κ w ] w∈∪ K P k = e ∪ K P k and in particular κ ∪ K Q k ∪ K P k A(st) • h • κ p = e ∪ K Q k • κ p when p ∈ k∈K P k . Moreover, for some l ∈ K and q ∈ Q l such that q / ∈ k∈K P k , we have κ ∪ K Q k ∪ K P k A(st) • h • κ q = κ ∪ K Q k P l A(st) • h l • κ q = κ ∪ K Q k Q l A(st) • κ Q l P l A(st) • h l • κ q = κ ∪ K Q k Q l A(st) • e Q l • κ q = e ∪ K Q k • κ q
hence h has the relevant diagram commute.

We now have everything we need to show the algorithm is correct. First note that it is easy to show by induction that all the subsets that go through to-do list are pairwise disjoint, hence why we use disjoint unions in the algorithm. But the fact that these unions are disjoint is not needed for the proof of correctness.

Consider some q ∈ Q done after the algorithm has stopped, and some a ∈ A. The only way to get added to Q done is through line 7 of the algorithm, hence q must have belonged to some Q. Hence there was an à such that a ∈ à for which Q à must have been added to the to-do list and thus have been considered in a run of the if statement on line 5. During this run, either κ Q done ∪Q hence an isomorphism (by the dual of [8, Proposition 14.9(1)], because the morphism

Q done A(in) → Q done ∪Q Ã A(in) is an isomorphism). By Lemma B.4, for any Q 1 ⊆ Q 2 ⊆ A * , if κ Q 1 ∪Q Q 1 A(st) is an isomorphism then so is κ Q 2 ∪Q Q 2
A(st) . Hence since Q done may only grow and since we just showed that at some point of the execution of the algorithm the morphism κ Q done ∪Q Ã Q done A(st) is an isomorphism, it stays so until the algorithm stops.

Hence at the end of the algorithm, for every q ∈ Q done and a ∈ A there is some Q

à such that qa ∈ Q à and κ Q done Q à Q done A(st) is an isomorphism. Using Lemma B.4 again, we get that κ Q done ∪Q done A Q done A(st) is an isomorphism. But Q done must be prefix-closed:
has gone through Q todo and qa ∈ Q Ã only gets added to Q todo if q ∈ Q has been added to Q done already. Hence Proposition B.3 applies and κ A * Q done A(st) : Q done /A(st) ∼ = (Reach A)(st) is an isomorphism at the end of the algorithm, and it is easy to check that it forms a morphism of automata between the automaton produced by the algorithm and Reach A. Lemma 3.7. For every Q, Q ⊆ A * , if the coproduct Q/A(st) In particular, x Proof. The equality holds by definition of κ Qa Q•a A(st) in Lemma 3.4. This morphism is an E-morphism because [κ qa ] q∈Q is an isomorphism hence the dual of [8, Proposition 14.9(1)] applies.

+ Q /A(st) exists, [m Q , m Q ] : Q/A(st) + Q /A(st) → A(st) (E, M)-factors into m Q Q • κ Q Q Q A(st) , κ Q Q Q A(st) : Q/A(st) + Q A(st) (Q Q ) A(st) A(st) Proof. Factor [m Q , m Q ] : Q/A(st) + Q /A(
• z Q • e Q = e Q Q • [κ q ] q∈Q and m Q Q • x • z Q = m Q , hence
Lemma 3.10. If κ Q Q Q A(st) : Q/A(st) (Q Q )/A(st) is an isomorphism then m Q = m Q • κ Q Q Q A(st) -1 • κ Q Q Q A(st)
Conversely, in the context of Lemma 3.7, assume also that all split epimorphisms are in E (if e • s = id for some e, s then e ∈ E). If m Q factors as m Q • f for some

f : Q/A(st) → (Q Q )/A(st) then κ Q Q Q A(st) is an isomorphism.
Proof. We immediately have that

m Q = m Q Q • κ Q Q Q A(st) = m Q • κ Q Q Q A(st) -1 κ Q Q Q A(st) since m Q = m Q Q • κ Q Q Q A(st) . Conversely, assume m Q = m Q • f for some f . Then [m Q , m Q ] = m Q • [id, f ]. But [id, f ] is a split epimorphism ([id, f ] • κ 1 = id)
hence it is also an E-morphism. We thus get two (E, M)-factorizations for [m Q , m Q ]:

m Q • [id, f ] = m Q Q • κ Q Q Q A(st) , κ Q Q Q A(st)

C. Proofs for Section 4 (The category of monoidal transducers)

Lemma 4.6. M is right-noetherian if and only if for any sequences (u n ) n∈N and (v n ) n∈N of M such that v n = v n+1 u n for all n ∈ N, there is some n ∈ N such that for all i ≥ n, u i is invertible.

Proof. The reverse implication is trivial. Now assume M right-noetherian, and consider (u n ) n∈N and (v n ) n∈N such that v n = v n+1 u n for all n ∈ N. Consider the set I = {i 0 < i 1 < . . .} of all the indices i such that u i is not invertible and, letting i -1 = -1, define u n = u in • • • u i n-1 +1 and v n = v in+1 for all n ∈ N. Then u n is never invertible because u in is not but u in-1 , . . . , u i n-1 +1 are (by definition), yet we still have by induction that v n = v n+1 u n . Since M is left-noetherian, I must be finite hence there is some n ∈ N such that for all i ≥ n, m i is invertible. Proof. Assume M right-noetherian and consider some x that is right-invertible with x r its right-inverse. For n ∈ N, set u 2n = x r , v 2n = and u 2n+1 = v 2n+1 = x. Then v n = v n+1 u n for all n ∈ N hence by right-noetherianity x is invertible. If x is leftinvertible instead, its left-inverse is right-invertible hence invertible and therefore so is x.

Proposition 4.12. The following are equivalent: Proof. Let us first show left-cancellativity up to invertibles. If υγ i = υλ i for some υ ∈ M and two countable families (γ i ) i∈I , (λ i ) i∈I of elements of M with I ⊆ N >0 , then defining Γ(0) = Λ(0) = , Γ(i) = γ i and Λ(i) = λ i for all i ∈ I and Γ(j) = Λ(j) = ⊥ for all j / ∈ I, we have that υΓ = υΛ. Hence red Γ = red Λ and υ lgcd(Γ) = υ lgcd(Λ). But lgcd Γ and lgcd Λ left-divide = Γ(0) = Λ(0) hence they are right-invertible and thus invertible: γ i and λ i = lgcd(Λ)lgcd(Γ) -1 γ i are equal up to an invertible (that does not depend on i) on the left.

Moreover, if υΛ = νΛ for some Λ such that (Λ(i)) i|Λ(i) =⊥ is left-coprime, then lgcd Λ is right-invertible (by definition of left-coprimality) and thus since υ lgcd(Λ) = lgcd(υΛ) = lgcd(νΛ) = ν lgcd(Λ) Conversely, if f : X → M × Y + 1 is an isomorphism it has an inverse f -1 : Y → M × X + 1 such that f • f -1 = id Y and f -1 • f = id X . For all x ∈ X, (f -1 ) † (f (x)) = ( , x) hence f (x) = ⊥: f ∈ Tot, and similarly for f -1 . Writing f = f 1 , f 2 and f -1 = (f -1 ) 1 , (f -1 ) 2 , we have that f 2 is a bijection with inverse f 2 -1 = (f -1 ) 2 , hence f ∈ Surj∩Inj. Finally, for all x ∈ X we have that f 1 (x)(f -1 ) 1 (f 2 (x)) = and conversely, hence f 1 (x) is invertible and f ∈ Inv. Proof. By Lemma 4.18 we only need to show for each i ∈ {1, 2, 3} that every f : X Y may be factored as m•e with e ∈ E i and m ∈ M i , and that E i and M i satisfy the diagonal fill-in property of Definition 2.6.

• (E 1 , M 1 ). Any f : X → M × Y + 1 may be factored through e : X → M × f

Figure 1 :

 1 Figure 1: Two transducers: unlike automata, the transitions are also labelled with output words.

Definition 2 . 1 (

 21 (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. in st out a

Example 2 .

 2 11 (initial, final and minimal automata and transducers [23, Example 3.1]).

7 :

 7 for a ∈ Ã do 8: compute m Qa : Qa/A(st) A(st) by factoring A(a) • m Q as in Lemma 3.8 9:

Lemma 4 . 7 .

 47 If M is right-noetherian then all its right-and left-invertibles are invertible.

  = ⊥, t(3) = α and t(4) = ; and finally 1 a = ( , 2), 1 b = (β, 3), 3 b = (β, 3) as well as s c = ⊥ for any other s ∈ S and c ∈ A. This transducer recognizes the function given by L(b n ) = β n α (seen in the corresponding quotient monoid, so for instance L(b n ) = αβ n when M = Σ ) for all n ∈ N and L(w) = ⊥ otherwise.

Figure 2 :

 2 Figure 2: A monoidal transducer A

1 , 2 , 1 and 2 for arrows in E 1 ,

 12121 E 2 ,

Figure 3 :

 3 Figure 3: Increasingly small transducers recognizing the same function as the transducer of Figure 2 when M = Σ

  and only if it is a finite set and either M is right-noetherian or X = ∅, in which case colength E (e : X Y ) = |X| -|Y | + rk e where rk e = e(x)=(υ,y) rk υ.

Theorem 5 . 3 .

 53 Algorithm 4 is correct and terminates as soon as Min L has finite stateset and M is right-noetherian. It makes at most 3 |Min L| st + rk(Min L) updates to Q (lines 8 and 14) and at most rk(Min L) + |Min L| st updates to T (line 10).

2 Y

 2 is indeed |X|-|Y |+rk e, whereas the (Surj∩Inj∩Tot)-codimension of some e : X 1 2

Lemma 3 . 1 ([ 23 ,

 3123 Remark 2.5]). The dual of the (E, M)-factorization Obs A in Auto(L) is the (M op , E op )-factorization Reach A op in Auto(L op ).

  st) → A(st) as e = [z Q , z Q ] : Q/A(st) + Q /A(st) Z and m : Z A(st). Since e Q + e Q : Q A(in) + Q A(in) Q/A(st) + Q /A(st)is an E-morphism (as a coproduct of E-morphisms, by the dual of[START_REF] Castellini | Abstract and Concrete Categories[END_REF] Proposition 14.15]), e • (e Q + e Q ) :Q Q A(in) Z and m : Z A(st) form a factorization of [m Q • e Q , m Q • e Q ] = [A( q )] q∈Q Q : Q Q A(in) → A(st)as in Definition 3.3. By unicity of the diagonal fill-in, there is an isomorphismx : Z ∼ = (Q Q )/A(st) such that m = m Q Q • x and x • e • (e Q + e Q ) = e Q Q .

Lemma 3 . 8 .

 38 by unicity of the diagonal fill-inx • z Q = κ Q Q Q A(st) . The same results holds for Q hence [m Q , m Q ] = (m • x -1 ) • [x • z Q , x • z Q ] yields the expected factorization. For every Q ⊆ A * , A(a) • m Q (E, M)-factors into m Qa • κ Qa Q•a A(st) : Q/A(st)Qa/A(st) A(st).

Lemma 4 . 7 .

 47 If M is right-noetherian then all its right-and left-invertibles are invertible.

( 1 )Lemma 4 . 15 .

 1415 Kl(T M ) has all countable powers of 1; • (4)a: if lgcd Γ = lgcd Λ and red Γ = red Λ then Γ = lgcd(Γ) red(Γ) = lgcd(Λ) red(Λ) = Λ • (4)b: red Λ = lgcd(red Λ) red(red Λ) hence lgcd(red Λ) = and red(red Λ) = red Λ; • (4)c: (υ lgcd(Λ)) red(Λ) = υΛ hence υ lgcd(Λ) = lgcd(υΛ) and red(uΛ) = red Λ. And conversely, assuming conditions (4)a, (4)b and (4)c, we get that • (2)a: by injectivity, Λ = lgcd(Λ) red(Λ) since lgcd(lgcd(Λ) red(Λ)) = lgcd(Λ) lgcd(red Λ) red(lgcd(Λ) red(Λ)) = red(red Λ) = lgcd Λ = red Λ • (2)b: if υ red(Γ) = ν red(Λ) then υ = υ lgcd(red Γ) red Γ = red(red Γ) = lgcd(υ red(Γ)) = red(υ red(Γ)) = lgcd(ν red(Λ)) = red(ν red(Λ)) = ν lgcd(red Λ) = red(red Λ) = ν = red Λ If right-and left-invertibles of M are all invertibles and if Kl(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.

Proposition 4 . 19 .

 419 (E 1 , M 1 ) = (Surj ∩ Inj ∩ Inv, Tot), (E 2 , M 2 ) = (Surj ∩ Inj, Inv ∩ Tot)and (E 3 , M 3 ) = (Surj, Inj ∩ Inv ∩ Tot) are all factorization systems in Kl(T M ).

- 1 (Finally 3 ,FinallyLemma 5 . 1 .: n i=0 1 n+1i=0 1

 135111 M × Y ) + 1 (given by e(x) = ( , x) if e(x) = ⊥ and e(x) = ⊥ otherwise) and m : f -1 (M × Y ) → M × Y + 1 (given by m(x) = e(x) when e(x) = ⊥).Moreover, given a commuting diagram choice for a φ :Y 1 → M × Y 2 + 1 is given by φ(y 1 ) = ⊥ if v(y 1 ) = ⊥ and φ(y 1 ) = (υ e -1 υ u , y 2 ) if e(x) = (υ e , y 1 ), u(x) = (υ u , y 2 ), v(y 1 ) = (υ v , z), m(y 2 ) = (υ m , z)and υ e υ v = υ u υ m . This definition does not depend on the choice of x because of the bijectiveness property of e, and we immediately have the commuting diagram 2 , M 2 ). Any f :X → M × Y + 1 may be factored through e : X → M × f -1 (M × Y ) + 1 (given by e(x) = (υ, x) if e(x) = (υ, -) and e(x) = ⊥ otherwise) and m : f -1 (M × Y ) → M × Y + 1 (given by m(x) = ( , y) when e(x) = (-, y)). choice for a φ : Y 1 → M × Y 2 + 1 is given by φ(y 1 ) = ⊥ if v(y 1 ) = ⊥ and φ(y 1 ) = (υ v υ m -1 , y 2 ) if e(x) = (υ e , y 1 ), u(x) = (υ u , y 2 ), v(y 1 ) = (υ v , z), m(y 2 ) = (υ m , z)and υ e υ v = υ u υ m . This definition does not depend on the choice of x because of the bijectiveness property of e, and we immediately have the commuting diagram M 3 ). Any morphism f :X → M × Y + 1 factors through e : X → M × Z + 1 and m : Z → M × Y + 1 with Z = {y ∈ Y | ∃x ∈ X, f (x) = (-, y)} e(x) = f (x) and m(y) = ( , y). choice for a φ : Y 1 → M ×Y 2 +1 is given by φ(y 1 ) = ⊥ if v(y 1 ) = ⊥ and φ(y 1 ) = (υ v υ m -1 , y 2 ) if e(x) = (υ e , y 1 ), u(x) = (υ u , y 2 ), v(y 1 ) = (υ v , z), m(y 2 ) = (υ m , z)and υ e υ v = υ u υ m . This definition does not depend on the choice of x because m is injective on Y , and we immediately have the commuting diagram An objectX of Kl(T M ) is M-noetherian if and only if it is a finite set, in which case length M (m : Y X) = |X| -|Y |.Proof. Let (x i : 1 X) i∈N be an infinite sequence of distincts elements of an infinite set X. Then the m n = [κ i ] n i=0 provide a counter-example to the M-noetherianity of X as none of them are isomorphisms (they are not surjective) yet[x i ] n+1 i=0 • m n = [x i ] n i=0 and [x i ] n i=0is always an M-morphism. Hence infinite sets are never M-noetherian. If X and the sequence (x i ) i∈N were finite instead, this example would prove that length M (m : Y X) ≥ |X| -|Y |.

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 ⊆ X we have colength Surj (XY ) = length Inj (Y X) = |X -Y |.Similarly, in KVec X has finite dimension if and only if it is Inj-noetherian iff it is Surj-artinian, and in that case for Y ⊆ X we have colength Surj

To this means, given a countable set I we consider partial functions Λ : I → M + 1. We write ⊥ I for the nowhere defined function i → ⊥ and (M + 1) I * = (M + 1) I -{⊥ I } for the set of partial functions that are defined somewhere. If I ⊆ 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 ⊗ : M 2 → M of M to a function M × (M + 1) I * → (M + 1) I * by setting (υ ⊗ Λ)(i) = υ ⊗ Λ(i) for i ∈ I such that Λ(i) = ⊥ and (υ ⊗ Λ)(i) = ⊥ otherwise.The universal property of the product then translates as:

Proposition 4.12. The following are equivalent:

(1) Kl(T M ) has all countable powers of 1;

(2) there are two functions lgcd : (M + 1) N * → M and red : (M + 1) N * → (M + 1) N * such that a) for all Λ ∈ (M + 1) N * , Λ = lgcd(Λ) red(Λ); b) for all Γ, Λ ∈ (M + 1) N * and υ, ν ∈ M , if υ red(Γ) = ν red(Λ) then υ = ν and red Γ = red Λ;

(3) Kl(T M ) has all countable products. Moreover when these hold, since any countable set I embeds into N, lgcd and red can be extended to (M + 1) I * . lgcd Λ is then a left-gcd of (Λ(i)) i|Λ(i) =⊥ and the product of (X i ) i∈I for some I ⊆ N is the set of pairs (Λ, (x i ) i∈I ) such that Λ ∈ red((M + 1) I * ) and, for all i ∈ I, x i ∈ X i if Λ(i) = ⊥ and x i = ⊥ otherwise. In particular, the I-th power of 1 is the set of irreducible partial functions I → M + 1:

We also write lgcd(⊥ N ) = ⊥, red(⊥ N ) = ⊥ N = ⊥ and do not distinguish between (⊥, ⊥) and ⊥. Also note that: Corollary 4.14. When the functions lgcd and red exist, the final transducer A f inal (L) recognizing a (Kl(T M ), 1, 1)-language L exists and has state-set

where we write (a -1 Λ)(w) = Λ(aw) for a ∈ A. Given any other transducer A = (S, (υ 0 , s 0 ), t, ) recognizing L, the unique transducer morphism f : A =⇒ A f inal (L) is given by the function f : S → M × Irr(A * , M ) + 1 such that f (s) = (lgcd L s , red L s ) where L s ( w )( * ) = A(w )(s) is the function recognized by A from the state s.

Learning

In this section, we thus first describe an algorithm that, given a subsequential function L, learns Min L using two oracles: Eval L takes as input a word w ∈ A * and computes L( w ); and Equiv L takes as input a transducer A, decides whether it recognizes L, and if not outputs a counter-example word w ∈ A * such that

When M is a free monoid, Vilar gives a very natural generalization of Angluin's L* algorithm for learning automata that does exactly this [START_REF] Angluin | Learning Regular Sets from Queries and Counterexamples[END_REF][START_REF] Miguel | Query Learning of Subsequential Transducers[END_REF]. Here we generalize Vilar's algorithm to arbitrary M by instantiating Algorithm 1 within Kl(T M ): we get Algorithm 4. This instantiation is possible because the conditions on M also guarantee (3) Kl(T M ) has all countable products. Moreover when these hold, since any countable set I embeds into N, lgcd and red can be extended to (M + 1) I * . lgcd Λ is then a left-gcd of (Λ(i)) i|Λ(i) =⊥ and the product of (X i ) i∈I for some

In particular, the I-th power of 1 is the set of irreducible partial functions I → M + 1: In particular when these conditions are satisfied lgcd(Λ) red(Λ) = Λ hence lgcd Λ left-divides (Λ(i)) i|Λ(i) =⊥ and if δ left-divides this family then Λ = δΓ for some Γ = ⊥ N hence Λ = (δ lgcd(Γ)) red(Γ) and thus δ left-divides lgcd(Λ) = δ lgcd(Γ).

Finally, let us show (2) ⇒ (3) along with the formula for the product of a countable number of objects. Given (X i ) i∈I indexed by some I ⊆ N, define I X i as in the statement of the proposition and the projection π j : Proof. Split the set of those Λ ∈ (M +1) N * such that (Λ(i)) i|Λ(i) =⊥ is left-coprime into the equivalence classes given by χΛ ∼ Λ for all χ ∈ M × . Then, for each equivalence class C pick a red C in C (using the axiom of choice) and for all υ ∈ M define lgcd(υ red(C)) = υ and red(υ red(C)) = red C so that in particular lgcd(red C) = and red(red

This is well-defined because if υ red(C) = ν red(D) for υ, ν ∈ M and two equivalence classes C, D, then if δ is a left-gcd of υ red(C) we have that δ = υυ for some υ (since υ left-divides υ red(C)) and there is some Λ such that υ red(C) = υυ Λ. But then by left-cancellativity up to invertibles, there is some χ ∈ M × such that υ Λ = χ red(C), hence χ -1 υ left-divides red C and as such is right-invertible (it left-divides , a leftgcd of red C), making υ right-invertible as well. This shows that υ is a left-gcd of υ red(C) = ν red(D) and we show similarly that this is also true of ν, hence by unicity of the left-gcd there is a ξ ∈ M × such that υ = νξ. Therefore by left-cancellativity up to invertibles there is another invertible ξ ∈ M × such that ξ red(C) = ξ red(D) hence by definition C = D and, by right-coprime-cancellativity, υ = ν.

Moreover this defines lgcd Λ and red Λ for any Λ because if δ is a left-gcd of Λ, then Λ = δΓ for some left-coprime Γ (if δ left-divides Γ then δδ left-divides Λ hence δ, therefore δ is invertible by left-cancellativity up to invertibles) hence Λ = δχ red(C) if Γ ∈ C and Γ = χ red(C).

We have thus defined two functions lgcd and red that immediately satisfy the conditions (2)a and (2)b of Proposition 4.12.

Lemma 4.18. In Kl(T M ), Iso = Surj ∩ Inj ∩ Inv ∩ Tot, and these four classes are all closed under composition (within themselves).

Proof. Closure under composition is immediate.

Conversely, a strict chain of M-subobjects of X is a strict chain of subsets X 0 X 1 • • • of X. In particular, the cardinality of these subsets is strictly increasing: if X is finite, the chain must be finite as well, and its length at most |X| -|X 0 |. Proof. Let (x i ) i∈N be an infinite sequence of distincts elements of an infinite set X, and set

Lemma 5.2. An object X of Kl(T M ) is E-artinian if and only if it is a finite set and either

X n be defined by e(x i ) = ( , x i ) for i ≤ n and e(x) = ⊥ otherwise, and let e n+1 n : X n+1

X n be the restriction of e n to X n+1 . None of the e n+1 n are isomorphisms (they are not total) yet e n+1 n • e n+1 = e n : infinite sets are never E-artinian.

Assume now X is not empty and M is not right-noetherian: there is an element x * ∈ X and two sequences (υ n ) n∈N and (ν n ) n∈N of elements of M such that for all n ∈ N, υ n / ∈ M × and ν n = ν n+1 υ n . Let e n : X 1 be defined by e n (x * ) = (ν n , * ) and e n (x) = ⊥ for all other x ∈ X, and let e n+1 n : 1 1 be defined by e n+1 n ( * ) = (υ n , * ). None of the e n+1 n are isomorphisms (they do not only produce invertible elements of M ) yet e n+1 n • e n+1 = e n : non-empty sets are never E-artinian when M is not rightnoetherian.

Conversely, if X is empty then it is immediately E-artinian: there is only one Emorphism out of X, id X . Suppose now that X is finite and M right-noetherian, and consider a cochain e n+1 n :

X n witness a decrease of the cardinality from their domain to their codomain and are not in Inj ∩ Tot. Fix now an x ∈ X such that e 0 (x) = ⊥ and write e n (x) = (ν n , x n ) and e n+1 n (x n+1 ) = (υ n , x n ) (this is well-defined because e n+1 n • e n+1 = e n ). Then ν n = ν n+1 υ n for all n ∈ N, hence since M is right-noetherian only a finite number of the e n+1 n , at most rk ν 0 , produce a noninvertible element on x n+1 . This is true for all x ∈ X, hence a finite number of the e n+1 n , at most rk e 0 , are not in Inv, and a finite number of them, at most |X| -|X 0 | + rk e 0 , are not in Iso: X is E-artinian and colength E (e 0 : X X 0 ) ≤ |X| -|X 0 | + rk e 0 . Finally, if rk e is finite, in light of this proof it is now easy to build a strict cochain of E-quotients of X starting with e : X Y that has length exactly |X| -|Y | + rk e. For each ν(x) ∈ M such that e(x) = (ν(x), y) for some x ∈ X and y ∈ Y , write indeed υ 1 (x), . . . , υ rk ν(x) (x) for a sequence of non-invertible divisors of ν of maximum length. Each morphism between two consecutive E-quotients in the cochain should either decrease the size of the quotient by 1, or produce exactly one of the υ i (x) on x for exactly one x ∈ X. Similarly, if rk e is infinite there sequences of divisors of some ν(x) or arbitrary length and it is then easy to build strict cochains of E-quotients of X of arbitrary lengths. Proof. Notice first that Algorithm 4 is indeed the instance of Algorithm 1 in Kl(T M ): for all q ∈ Q and a ∈ A ∪ { }, Λ(q, a) is a left-gcd of L(q, a, •) = (L( qat )) t∈T = Λ(q, a)R(q, a, •), hence R(q, a, •) is left-coprime and there is a χ ∈ M × such that Λ(q, a)χ -1 = lgcd(L(q, a, •)) and χR(q, a, •) = red(L(q, a, •)). Hence Q/T = {red(L(q, e, •)) | q ∈ Q, L(q, e, •) = ⊥ T } is the quotient of the set {R(q, e, •) | q ∈ Q, R(q, e, •) = ⊥ T } by equality up to invertibles on the left. It follows that Q/T (Q ∪ {qa})/T is an E-morphism if and only if it is surjective, that is if and only if the condition on line 7 is not satisfied, and Q/(T ∪ {at}) Q/T is an M-morphism if and only if it is total, produces only invertibles elements and is injective, that is if and only if it respectively does not satisfy any of the three conditions on line 9: it is easy to see that it is total if and only if the first condition is not satisfied; it is total but does not only produce invertible elements if and only if there is some q ∈ Q and at ∈ AT such that L(q, a, t) is not left-divisible by Λ(q, e) which is equivalent to the second condition holding; and finally it is easy to see that it is total and only produces invertible elements but is not injective if and only if the third condition holds.

The correction and termination is then given by Theorem 2.16, thanks to Lemmas 5.1 and 5.2. These two lemmas also provide the complexity bound of the algorithm, as Theorem 2.16 is proven in [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF] by showing that each addition to T contributes to a morphism in a strict chain of M-subobjects of (Min L)(st) starting with { }/A * A * /A * = (Min L)(st) [START_REF] Colcombet | Learning Automata and Transducers: A Categorical Approach[END_REF]Lemma 33], and each addition to Q contributes to a morphism in a chain of E-quotients of (Min L)(st) ending with (Min L)(st) = A * /A * A * /{ } [10, Lemma 33] and whose isomorphisms may only be contributed by the addition of a counter-example outputted by Equiv L and are immediately followed by a nonisomorphism in the chain for T or the cochain for Q [10, Lemma 36].