# Automata in the Category of Glued Vector Spaces

## Transcript Of Automata in the Category of Glued Vector Spaces

Automata in the Category of Glued Vector Spaces∗†

Thomas Colcombet

Daniela Petri¸san

[email protected] [email protected]

CNRS, IRIF, Univ. Paris-Diderot, Paris 7, France

November 17, 2017

arXiv:1711.06065v1 [cs.FL] 16 Nov 2017

Abstract

In this paper we adopt a category-theoretic approach to the conception of automata classes enjoying minimization by design. The main instantiation of our construction is a new class of automata that are hybrid between deterministic automata and automata weighted over a ﬁeld.

1 Introduction

In this paper we introduce a new automata model, hybrid set-vector automata, designed to accept weighted languages over a ﬁeld in a more eﬃcient way than Schtzenberger’s weighted automata [13]. The space of states for these automata is not a vector space, but rather a union of vector spaces “glued” together along subspaces. We call them hybrid automata, since they naturally embed both deterministic ﬁnite state automata and ﬁnite automata weighted over a ﬁeld. In Section 2 we present at an informal level a motivating example and the intuitions behind this construction, avoiding as much as possible categorytheoretical technicalities. We use this example to guide us throughout the rest of the paper.

A key property that the new automata model should satisfy is minimization. Since the morphisms of “glued” vector spaces are rather complicated to describe, proving the existence of minimal automata “by hand” is rather complicated. Therefore we opted for a more systematic approach and adopted a category-theoretic perspective for designing new forms of automata that enjoy minimization by design. In particular, we introduce the category of “glued” vector spaces in which these automata should live and we analyse its properties that render minimization possible.

∗This work was supported by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No.670624), and by the DeLTA ANR project (ANR-16-CE40-0007). The authors also thank the Simons Institute for the Theory of Computing where this work has been partly developped.

†This is the knowledge enriched version of the same paper published in the proceedings of MFCS 2017.

1

Starting with the seminal papers of Arbib and Manes, see for example [3] and the references therein, and of Goguen [10], it became well established that category theory oﬀers a neat understanding of several phenomena in automata theory. In particular, the key property of minimization in diﬀerent contexts, such as for deterministic automata (over ﬁnite words) and Schtzenberger’s automata weighted over ﬁelds [13], arises from the same categorical reasons (existence of some limits/colimits and an (epi,mono)-factorization system [3]).

There is a long tradition of seeing automata either as algebras or coalgebras for a functor. However, in the case of deterministic automata, the algebraic view does not capture the accepting states, while the coalgebraic view does not capture the initial state. In the coalgebraic setting one needs to consider the so-called pointed coalgebras, see for example [1], where minimal automata are modelled as well-pointed coalgebras. The dual perspective of automata seen as both algebras or coalgebras, as well as the duality between reachability and observability, has been explored more recently in papers such as [4–6].

Here we take yet another approach to deﬁning automata in a category. The reader acquainted with category theory will recognise that we see automata as functors from an input category (that speciﬁes the type of the machines under consideration, which in this paper is restricted to word automata) to a category of output values. We show that the next ingredients are suﬃcient to ensure minimization: the existence of an initial and of a ﬁnal automaton for a language, and a factorization system on the category in which we interpret our automata.

For example, deterministic and weighted automata over a ﬁeld are obtained by considering as output categories the categories Set of sets and functions and Vec of vector spaces and linear maps, respectively. Since Set and Vec have all limits and colimits, it is very easy to prove the existence of initial and ﬁnal automata accepting a given language. In both cases, the minimal automaton for a language is obtained by taking an epi-mono factorization of the unique arrow from the initial to the ﬁnal automaton.

Notice that the initial and the ﬁnal automata have inﬁnite (-dimensional) state sets (spaces). If the language at issue is regular, that is, if the unique map from the initial to the ﬁnal automaton factors through a ﬁnite (-dimensional) automaton then, automatically, the minimal automaton will also be ﬁnite (dimensional). However, this relies on very speciﬁc properties of the categories of sets and vector spaces, namely on the fact that the full subcategories Setﬁn of ﬁnite sets and Vecﬁn of ﬁnite dimensional vector spaces are closed in Set, respectively in Vec, under both quotients and subobjects.

Coming back to hybrid set-vector automata, we deﬁne them as word automata interpreted in an output category Glue(Vec) which we obtain as the completion of Vec under certain colimits, and can be described at an informal level as “glueings” of arbitrary vector spaces. The deﬁnition of this form of cocompletion Glue(C) of a category C is the subject of Section 4.

We are interested in those hybrid automata for which the state object admits a ﬁnitary description, which intuitively can be described as ﬁnite glueings of ﬁnite dimensional spaces. For this reason we will consider the subcategory Glueﬁn(Vecﬁn) of Glue(Vec). It turns out that Glueﬁn(Vecﬁn) is closed under quotients in Glue(Vec) but, crucially, it is not closed under subobjects. For example, a glueing of inﬁnitely many one-dimensional spaces is a subobject of a two-dimensional space, but only the latter is an object of Glueﬁn(Vecﬁn).

This is the motivation for introducing a notion of (ES ,MS )-factorization

2

of a category C through a subcategory S. This is a reﬁnement of the classical notion of factorization system on C and is used for isolating the semantical computations (in C) from the automata themselves (with an object from S as “set of conﬁgurations”).1 We show how it provides a minimization of “S-automata for representing C-languages”. A concrete instance of this is a factorization system on Glue(Vec) through Glueﬁn(Vecﬁn), which plays a crucial role in proving the existence of minimal Glueﬁn(Vecﬁn)-automata for recognizing weighted languages.

The rest of the paper is organised as follows. We ﬁrst develop a motivating example of a hybrid set-vector space automaton in Section 2. We then identify in Section 3 the category-theoretic ingredients that are suﬃcient for a class of automata to enjoy minimization. We then turn to our main contribution, namely the description and the study of the properties of (ﬁnite-)mono-diagrams in a category, in Section 4. We conclude in Section 5 with a discussion of some of the design choices we made in this paper.

2 The hybridisation of deterministic ﬁnite state and vector automata

In this section, we (rather informally) describe the motivating example of this paper: the construction of a family of automata that naturally extends both deterministic ﬁnite state automata and ﬁnite automata weighted over a ﬁeld in the sense of Schtzenberger (i.e., automata in the category of ﬁnite vector spaces). The intuition should then support the categorical constructions that we develop in the subsequent sections.

Set automata (deterministic automata). Let us ﬁx ourselves an alphabet A. A deterministic automaton (or set automaton) is a tuple

A = (Q, i, f , (δa)a∈A) ,

in which Q is a set of states, i is a map from a one element set 1 = {0} to Q (i.e. an initial state), f is a map from Q to a two elements set 2 = {0, 1} (i.e. a set of accepting states), and δa is a map from Q to itself for all letters a ∈ A. Given a word u = a1 . . . an, the automaton accepts the map [[A]](u) : 1 → 2 deﬁned as:

[[A]](u) = f ◦ δu ◦ i

where δa1...an = δan ◦ · · · ◦ δa1 .

We recognize here the standard deﬁnition of a deterministic automaton, in which a word u is accepted if the map [[A]](u) is the constant 1, and rejected if it is the constant 0.

Vector space automata (automata weighted over a ﬁeld). Now, we can use the same deﬁnition of an automaton, this time with Q a vector space (over, say, the ﬁeld R), i a linear map from R to Q, f a linear map from Q to R (seen as a R-vector space as usual), and δa a linear map from Q to itself. In other words, we have used the same deﬁnition, but this time in the category of vector spaces. Given a word u, a vector space automaton A computes [[A]](u) : R → R as the composite described above. Since a linear map from R to R is only determined

1This distinction is usually not necessary, and we are not aware of its existence in the literature. It is crucial for us, thus we cannot use already existing results from the coalgebraic literature, e.g. [1].

3

by the image of 1, this automaton can be understood as associating to each input word u the real number [[A]](u)(1). We will informally refer to such automata in this section as vector space automata. Let us provide an example.

Leading example. For a word u ∈ {a, b, c}∗ let |u|a denote the number of occurrences of the letter a in u. Let us compute the map F which, given a word u ∈ {a, b, c}∗, outputs 2|u|a if it contains an even number of b’s and no c’s, and 0 in all other cases. This is achieved with the vector space automaton Avec = (Qvec = R2, ivec, f vec, δvec) where for all x, y ∈ R,

ivec(x) = (x, 0) , f vec(x, y) = x ,

δavec(x, y) = (2x, 2y) , δcvec(x, y) = (0, 0) .

δbvec(x, y) = (y, x) ,

One easily checks that indeed [[Avec]](u)(1) = F (u) for all words u ∈ A∗.

Can we do better? It is well known from Schtzenberger’s seminal work that the vector space automaton Avec is minimal, both in an algebraic sense (to be described later) as well as at an intuitive level in the sense that no vector space automaton could recognize F with a dimension one vector space as conﬁguration space: Avec is “dimension minimal.”

However, let us think for one moment on how one would “implement” the function F as an online device that would get letters as input, and would modify its internal state accordingly. Would we implement concretely Avec directly? Probably not, since there is a more economic2 way to obtain the same result: we can maintain 2m where m is the number of a’s seen so far, together with one bit for remembering whether the number of b’s is even or odd. Such an automaton would start with 1 in its unique real valued register. Each time an a is met, the register is doubled, each time b is met, the bit is reversed, and when c is met, the register is set to 0. At the end of the input word, the automaton would output 0 or the value of the register depending on the current value of the bit. If we consider the conﬁguration space that we use in this encoding, we use R R instead of R × R. Can we deﬁne an automata model that would faithfully implement this example?

A ﬁrst generalization: disjoint unions of vector spaces. A way to achieve this is to interpret the generic notion of automata in the category of ﬁnite disjoint unions of vector spaces (duvs). One way to deﬁne such a ﬁnite disjoint unions of vector spaces is to use a ﬁnite set N of ‘indices’ p, q, r . . . , and to each index p associate a vector space Vp. The ‘space’ represented is then {(p, v) | p ∈ N, v ∈ Vp}. A ‘map’ between duvs represented by (N, V ) and (N , V ) is then a pair h : N → N together with a linear map fp from Vp to Vh(p) for all p ∈ N . It can be seen as mapping each (p, v) ∈ N × Vp to (h(p), fp(v)). Call this a duvs map. Such duvs maps are composed in a natural way. This deﬁnes a category, and hence we can consider duvs automata which are automata with a duvs for its state space, and transitions implemented by duvs maps.

For instance, we can pursue with the computation of F and provide a duvs automaton Aduvs = (Qduvs, iduvs, f duvs, δduvs) where Qduvs = {(s, x) | s ∈ {even, odd}, x ∈ R} (considered as a disjoint union of vector spaces with indices even and odd and all associated vector spaces Veven = Vodd = R). The maps can

2Under the reasonable assumption that maintaining a real is more costly than maintaining a bit.

4

be conveniently deﬁned as follows:

iduvs(x) = (even, x) f duvs(even, x) = x

f duvs(odd, x) = 0

δaduvs(even, x) = (even, 2x) δbduvs(even, x) = (odd, x) δcduvs(even, x) = (even, 0)

δaduvs(odd, x) = (odd, 2x) δbduvs(odd, x) = (even, x) δcduvs(odd, x) = (odd, 0)

This automaton computes the expected F . It is also obvious that such automata over ﬁnite disjoint unions of vector spaces generalize both deterministic ﬁnite state automata (using only 0-dimensional vector spaces), and vector space automata (using only one index). However, is it the joint generalization that we hoped for? The answer is no...

Minimization of duvs automata. We could think that the above automaton Aduvs is minimal. However, it involved some arbitrary decisions when deﬁning it. This can be seen in the fact that when δcduvs is applied, we chose to not change the index (and set to null the real value): this is arbitrary, and we could have exchanged even and odd, or ﬁxed it abitrarily to even, or to odd. All these variants would be equally valid for computing F .

It is a bit diﬃcult at this stage to explain the non-minimality of these automata since we did not introduce the proper notions yet. Let us try at a high level, invoking some standard automata-theoretic concepts. The ﬁrst remark is that every conﬁguration in Qduvs is ‘reachable’ in this automaton: indeed (even, x) = iduvs(x) and (odd, x) = δbduvs ◦ iduvs(x) for all x ∈ R. Hence there is no hope to improve the automaton Aduvs or one of its variants by some form of ‘restriction to its reachable conﬁgurations’. Only ‘quotienting of conﬁgurations’ remains. However, one can show that none among Aduvs and the variants mentioned above is the quotient of another. Keeping in mind the Myhill-Nerode equivalence, we should instead merge the conﬁgurations (even, 0) and (odd, 0) since these are observationally equivalent:

f duvs ◦ δuduvs(even, 0) = 0 = f duvs ◦ δuduvs(odd, 0) for all words u ∈ A∗.

However, the quotient duvs obtained by merging (even, 0) and (odd, 0), albeit not very intuitive, consists of one index associated to a two dimensional vector space, which is essentially an indexed version of the vector space automaton Avec computed before. At this stage, we understand that minimising in the category of duvs is not very helpful, as we do not obtain the desired optimisation.

How to proceed from here. The only reasonable thing to do is indeed to merge (even, 0) and (odd, 0), but we have to be more careful about the precise meaning of ‘quotient’. A possibility is to add explicitly equivalence classes in the deﬁnition of the automaton. However, category theory provides useful concepts and terminology for deﬁning these objects: colimits, and more precisely the free co-completion of a category. In the previous paragraph, we have shown that the category of duvs – which is itself the free completion of Vec with respect to ﬁnite coproducts – is not a good ambient category for our purposes. We need more colimits, so that the notion of ‘quotient’ is further reﬁned. At the other extreme, we could consider the free completion with respect to all colimits, which, informally, consists of objects obtained from the category using copying and gluing. We will explain later in Section 5 why we choose to not use this completion. Intuitively, by adding all colimits we glue the vector spaces “too much”, and not only we loose a geometric intuition of the objects we are dealing

5

with, but we may run into actual technical problems when it comes the existence of minimal automata.

Instead, we restrict our attention to a class of colimits (which strictly contains coproducts) for which diﬀerent spaces in the colimit can be “glued” together along subspaces, but which do not contain implicit self folding (i.e., such that an element of a vector space is not glued to a distinct element of the same vector space, directly or indirectly). E.g., we can describe ‘two one-dimensional spaces, the 0-dimensional subspaces of which are identiﬁed through a linear bijection’. In this way we obtain the new category of glued vector spaces and hybrid set-vector space automata, corresponding to Glue(Vec)-automata in the rest of the paper.

Generic arguments of colimits provide the language for describing these objects, but do not solve the question of minimality. In particular, we are interested in automata whose space of conﬁgurations is a ﬁnite colimit belonging to the class described above. The categorical development in this work addresses the minimization problem for hybrid automata. An intuition in the case of gluing of vector spaces. In the case of gluing of vector spaces, it is possible to isolate a combinatorial statement that plays a crucial role in the existence of minimal hybrid set-vector automata:

(a) Any subset of a ﬁnite-dimensional vector space admits a minimal cover as a ﬁnite union of subspaces. (b) Furthermore, there is a unique such cover which is a union of subspaces which are incomparable with respect to inclusion.

For instance, in the original vector space automaton Avec, the states that are reachable in fact all belong to R × {0} ∪ {0} × R, and this is the minimal cover as in (a) of these reachable conﬁgurations. This subset of R2 has the structure of two R-spaces. These happen to intersect at (0, 0), hence it is necessary to glue them at 0 to faithfully represent this set of reachable conﬁgurations. Thanks to (b) this decomposition is canonical, and hence can be used for describing the automaton.

3 Automata in a category

In this section, we provide the general deﬁnition for a (ﬁnite word) automaton in a category. We also isolate properties guaranteeing the existence of minimal automata. Though presented diﬀerently, the material in the ﬁrst subsection is essentially a slight variation around the work of Arbib and Manes [3], which introduced a notion of automaton in a category and, moreover, highlighted the connection between factorization systems of the ambient category, duality and minimization. In the remaining subsections we develop a reﬁnement of this approach to minimization, and introduce a notion of factorization system through a subcategory.

6

3.1 Automata in a category, initial automaton, ﬁnal automaton

Deﬁnition 1 (automata). Let C be a locally small category, I and F be objects of C, and A be some alphabet. An automaton A in the category C (over the alphabet A), for short a C, I, F -automaton (or simply C-automaton when I and F are obvious in the context), is a tuple (Q, i, f , δ), where Q is an object in C (called the state object), i : I → Q and f : Q → F are morphisms in C (called initial and ﬁnal morphisms), and δ : A → C(Q, Q) is a function associating to each letter a ∈ A a morphism δa : Q → Q in C. We extend the function δ to A∗ as with δ being the identity morphism on Q and δwa = δa ◦ δw for all a ∈ A and w ∈ A∗.

A morphism of C, I, F -automata h : A → A is a morphism h : Q → Q in C between the state objects which commutes with the initial, ﬁnal and transition morphisms:

Q

i

Q δa Q

Qf

I

h

h

h

h

F

(1)

i

Q

Q

Q

δa

Q

f

Example 2. The two guiding instantiation of this deﬁnition are as follows.

When the category C is Set, I = 1 and F = 2, we recover the standard notion of a deterministic and complete automaton (over the alphabet A∗). In the second

case, when C is Vec over a base ﬁeld K, I = K and F = K, we obtain K-weighted automata. Indeed, if Q is isomorphic to Kn for some natural number n, then linear maps i : K → Q are in one-to-one correspondence with vectors Kn. The same holds for linear maps f : Q → K, hence i and f are simply selecting an initial, respectively, a ﬁnal vector.

Deﬁnition 3 (languages and language accepted). A C, I, F -language (or Clanguage when I and F are clear from the context) is a function L : A∗ → C(I, F ).

We say that A accepts the language L if L(w) = [[A]](w) := f ◦ δw ◦ i for all w ∈ A∗. Let AutoC(L) denote the category of C, I, F -automata for L, that is, the category whose objects are C, I, F -automata that accept the language L and whose arrows are morphisms of C, I, F -automata3.

Lemma 4. If the coproduct w∈A∗ I exists in C, then AutoC(L) has an initial object initC(L). If the product w∈A∗ F exists in C, then AutoC(L) has a ﬁnal object finalC(L).

In the case of Set, these automata are well known. The ﬁrst one has as states A∗, as initial state ε, and when it reads a letter a, its maps w to wa. Its ﬁnal map sends the state w to L(w)(0). There exists one and exactly one morphism from this automaton to each automata for the same language. The generalisation of this construction is that the state space is the coproduct of A∗many copies of I. The ﬁnal automaton is known as the automaton of ‘residuals’.

3If A accepts the language L and h : A → A is a morphism of C, I, F -automata, then A also accepts the language L. Hence, AutoC(L) is a ‘connected component’ in the category of all C, I, F -automata.

7

Its set of states are the maps from A∗ to 2. The initial state is L itself, and when reading a letter a, the state S is mapped to w → S(aw). The ﬁnal map sends S to S(ε). The generalisation of this construction is that the state space is the product of A∗-many copies of F .

3.2 Factorizations through a subcategory

It is important in the development of this paper to distinguish the category AutoC(L) in which the initial and ﬁnal automata for a language L exist (recall Lemma 4) and which contains ‘inﬁnite automata’, from the subcategory, named AutoS (L) that is used for the concrete automata (with state object in S) which are intended to be algorithmically manageable. In this section, we provide the concept of factorizing through a subcategory, which articulates the relation between these two categories.

Deﬁnition 5 (factorization through a subcategory). Assume S is a subcategory of C. An arrow f : X → Y in C is called S-small if it factors through some object S of S, that is, f is the composite X u S v Y for some u : X → S and v : S → Y .

A factorization system through S on C (or simply a factorization system on C if C = S) is a pair (ES , MS ) where ES and MS are classes of arrows in C so that the codomains of all arrows in ES , the domains of all arrows in MS are in S, and the following conditions hold:

1. ES and MS are closed under composition with isomorphisms in S, on the right, respectively left side.

2. All S-small arrows in C have an (ES , MS )-factorization, that is, if f : X → Y factors through an object of S, then there exists e ∈ ES and m ∈ MS , such that f = m ◦ e.

3. The unique (ES , MS )-diagonalization property holds: for each commutative diagram X eT

f

g

(2)

u

SmY

with e ∈ ES and m ∈ MS , there exists a unique diagonal, that is, a unique morphism u : T → S such that u ◦ e = f and m ◦ u = g.

Using standard techniques, we can prove that whenever (ES , MS ) is a factorization system through S on C, both classes ES and MS are closed under composition, their intersection consists of precisely the isomorphisms in S, and,

as expected, that (ES , MS )-factorizations of S-small morphisms are unique up to isomorphism.

Example 6. Instantiating (C, S) to be (Set, Setﬁn) yields a natural factorization system through Setﬁn on Set (as the restriction of the standard (epi,mono)factorization system on Set to Setﬁn-small morphisms, i.e., the maps of ﬁnite image). Over these categories Setﬁn-automata are deterministic ﬁnite state automata inside the more general category of Set-automata which are deterministic

8

(potentially inﬁnite) automata. The example (Vec, Vecﬁn) was already mentioned. In this case, being Vecﬁn-small is equivalent to having ﬁnite rank.

Notice that for (C, S) = (Set, Setﬁn) or (Vec, Vecﬁn), the factorization systems through the subcategories are obtained simply by restricting the factorization systems on Set, respectively Vec. This is because, in these cases S is closed under quotients and subobjects in C. The category Glueﬁn(Vecﬁn) used in this paper is closed under quotients, but in general not under subobjects (and this is the important reason for this extension of the standard notion of factorization). This is also a case in which there is a factorization system in the category C, that coincide over S with factorizing through S, but for which factorizing in C of an S-small morphism and factorizing it through S yield diﬀerent results.

A factorization system on C lifts naturally to categories of C-valued functors. Automata being very close in deﬁnition to such a functor category, factorization systems also lift to them. Lemma 7 shows that this is also the case for factorization systems through S, assuming of course that the input and output objects I and F belong to S.

Lemma 7. Whenever (ES , MS ) is a factorization system through a category S then (EAutoS(L), MAutoS(L)) is a factorization system through AutoS (L) for the category AutoC(L), where EAutoS(L) (resp. MAutoS(L)) contains these AutoC(L)morphisms that belong to ES (resp. to MS ) as C-morphisms.

3.3 Minimization through a subcategory

In this section, we show how the joint combination of having initial and ﬁnal automata for a language, as given by Lemma 4, together with a factorization system through a subcategory S yields the existence of a minimal S-automaton for small C-languages.

We make the following assumptions: (ES , MS ) is a factorization system through S on C, and L is a C-language accepted by some S-automaton such that there exist an initial initC(L) C-automaton and a ﬁnal C-automaton finalC(L) for L.

Deﬁnition 8 (minimal automaton). The minimal C-automaton for L, denoted minS (L), is the4 S-automaton for L obtained by (EAutoS(L), MAutoS(L))factorization of the unique AutoS (L)-small morphism from initC(L) to finalC(L).

Theorem 9. For all S-automata A for L satisfying the above assumptions, we have

minS (L) ∼= obsS (reachS (A)) ∼= reachS (obsS (A)) ,

in which

• reachS (A) is the result of applying an (EAutoS(L), MAutoS(L))-factorization to the unique AutoS (L)-morphism from initC(L) to A, and

• obsS (A) is the result of applying an (EAutoS(L), MAutoS(L))-factorization to the unique AutoS (L)-morphism from A to finalC(L).

4It is unique up to isomorphism according to the diagonal property.

9

This theorem does not only state the existence of a minimal automaton, it also makes transparent how to make eﬀective its construction: if one possesses both an implementation of reachS and obsS , then their sequencing minimises an input automaton. From the above theorem it immediately follows that minS (L) is both an EAutoS(L)-quotient of a MAutoS(L)-subobject of A and a MAutoS(L)subobject of an EAutoS(L)-quotient of A: the minimal automaton divides every other automaton for the language.

Proof idea. The proof is contained in the following commutative diagram, in which denotes AutoC(L)-morphisms in EAutoS(L), and AutoC(L)-morphisms in MAutoS (L):

A

initC (L)

reachS (A) obsS (reachS (A)) finalC(L)

minS (L)

That obsS (reachS (A)) is an (EAutoS(L), MAutoS(L))-factorization of the unique AutoC(L)-morphism from initC(L) to finalC(L) follows since EAutoS(L) is closed under composition. By the unique diagonal property, it is isomorphic to minS (L). The case reachS (obsS (A)) is symmetric.

3.4 A special case of factorization through

So far, the description of factorization and minimization of automata is very generic. Hereafter, the classes ES and MS are constructed along a particular principle which we describe now. In the next sections we will instantiate this construction when S is the subcategory Glueﬁn(Vecﬁn) of glued vector spaces.

In this section we ﬁx an (E, M )-factorization system on C and a subcategory S → C.

Deﬁnition 10. An S-extremal epimorphism5 in C is an arrow e : X → S in C, with S an object in S, such that if e = m ◦ g where m is in M with domain in S, then m is an isomorphism. We set MS to be the class of arrows in M with domain in S, and ES to be the class of S-extremal epimorphisms.

Deﬁnition 11. An MS -subobject in S of an object X of C is an equivalence class up to isomorphism of a morphism S → X belonging to M , where S is an object of S. The MS -subobject S → X is called proper if it is not an isomorphism.

Lemma 12. Assume the following conditions hold:

1. all arrows in M are monomorphisms in C,

2. S is closed under E-quotients, i.e., if e : S → T is in E with S in S, then T is isomorphic to an object of S,

3. the intersection of a nonempty set of MS -subobjects of an object X of C exists and is an M S-subobject of X, and,

5Note that S-extremal epimorphisms need not be epimorphisms in C.

10

Thomas Colcombet

Daniela Petri¸san

[email protected] [email protected]

CNRS, IRIF, Univ. Paris-Diderot, Paris 7, France

November 17, 2017

arXiv:1711.06065v1 [cs.FL] 16 Nov 2017

Abstract

In this paper we adopt a category-theoretic approach to the conception of automata classes enjoying minimization by design. The main instantiation of our construction is a new class of automata that are hybrid between deterministic automata and automata weighted over a ﬁeld.

1 Introduction

In this paper we introduce a new automata model, hybrid set-vector automata, designed to accept weighted languages over a ﬁeld in a more eﬃcient way than Schtzenberger’s weighted automata [13]. The space of states for these automata is not a vector space, but rather a union of vector spaces “glued” together along subspaces. We call them hybrid automata, since they naturally embed both deterministic ﬁnite state automata and ﬁnite automata weighted over a ﬁeld. In Section 2 we present at an informal level a motivating example and the intuitions behind this construction, avoiding as much as possible categorytheoretical technicalities. We use this example to guide us throughout the rest of the paper.

A key property that the new automata model should satisfy is minimization. Since the morphisms of “glued” vector spaces are rather complicated to describe, proving the existence of minimal automata “by hand” is rather complicated. Therefore we opted for a more systematic approach and adopted a category-theoretic perspective for designing new forms of automata that enjoy minimization by design. In particular, we introduce the category of “glued” vector spaces in which these automata should live and we analyse its properties that render minimization possible.

∗This work was supported by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No.670624), and by the DeLTA ANR project (ANR-16-CE40-0007). The authors also thank the Simons Institute for the Theory of Computing where this work has been partly developped.

†This is the knowledge enriched version of the same paper published in the proceedings of MFCS 2017.

1

Starting with the seminal papers of Arbib and Manes, see for example [3] and the references therein, and of Goguen [10], it became well established that category theory oﬀers a neat understanding of several phenomena in automata theory. In particular, the key property of minimization in diﬀerent contexts, such as for deterministic automata (over ﬁnite words) and Schtzenberger’s automata weighted over ﬁelds [13], arises from the same categorical reasons (existence of some limits/colimits and an (epi,mono)-factorization system [3]).

There is a long tradition of seeing automata either as algebras or coalgebras for a functor. However, in the case of deterministic automata, the algebraic view does not capture the accepting states, while the coalgebraic view does not capture the initial state. In the coalgebraic setting one needs to consider the so-called pointed coalgebras, see for example [1], where minimal automata are modelled as well-pointed coalgebras. The dual perspective of automata seen as both algebras or coalgebras, as well as the duality between reachability and observability, has been explored more recently in papers such as [4–6].

Here we take yet another approach to deﬁning automata in a category. The reader acquainted with category theory will recognise that we see automata as functors from an input category (that speciﬁes the type of the machines under consideration, which in this paper is restricted to word automata) to a category of output values. We show that the next ingredients are suﬃcient to ensure minimization: the existence of an initial and of a ﬁnal automaton for a language, and a factorization system on the category in which we interpret our automata.

For example, deterministic and weighted automata over a ﬁeld are obtained by considering as output categories the categories Set of sets and functions and Vec of vector spaces and linear maps, respectively. Since Set and Vec have all limits and colimits, it is very easy to prove the existence of initial and ﬁnal automata accepting a given language. In both cases, the minimal automaton for a language is obtained by taking an epi-mono factorization of the unique arrow from the initial to the ﬁnal automaton.

Notice that the initial and the ﬁnal automata have inﬁnite (-dimensional) state sets (spaces). If the language at issue is regular, that is, if the unique map from the initial to the ﬁnal automaton factors through a ﬁnite (-dimensional) automaton then, automatically, the minimal automaton will also be ﬁnite (dimensional). However, this relies on very speciﬁc properties of the categories of sets and vector spaces, namely on the fact that the full subcategories Setﬁn of ﬁnite sets and Vecﬁn of ﬁnite dimensional vector spaces are closed in Set, respectively in Vec, under both quotients and subobjects.

Coming back to hybrid set-vector automata, we deﬁne them as word automata interpreted in an output category Glue(Vec) which we obtain as the completion of Vec under certain colimits, and can be described at an informal level as “glueings” of arbitrary vector spaces. The deﬁnition of this form of cocompletion Glue(C) of a category C is the subject of Section 4.

We are interested in those hybrid automata for which the state object admits a ﬁnitary description, which intuitively can be described as ﬁnite glueings of ﬁnite dimensional spaces. For this reason we will consider the subcategory Glueﬁn(Vecﬁn) of Glue(Vec). It turns out that Glueﬁn(Vecﬁn) is closed under quotients in Glue(Vec) but, crucially, it is not closed under subobjects. For example, a glueing of inﬁnitely many one-dimensional spaces is a subobject of a two-dimensional space, but only the latter is an object of Glueﬁn(Vecﬁn).

This is the motivation for introducing a notion of (ES ,MS )-factorization

2

of a category C through a subcategory S. This is a reﬁnement of the classical notion of factorization system on C and is used for isolating the semantical computations (in C) from the automata themselves (with an object from S as “set of conﬁgurations”).1 We show how it provides a minimization of “S-automata for representing C-languages”. A concrete instance of this is a factorization system on Glue(Vec) through Glueﬁn(Vecﬁn), which plays a crucial role in proving the existence of minimal Glueﬁn(Vecﬁn)-automata for recognizing weighted languages.

The rest of the paper is organised as follows. We ﬁrst develop a motivating example of a hybrid set-vector space automaton in Section 2. We then identify in Section 3 the category-theoretic ingredients that are suﬃcient for a class of automata to enjoy minimization. We then turn to our main contribution, namely the description and the study of the properties of (ﬁnite-)mono-diagrams in a category, in Section 4. We conclude in Section 5 with a discussion of some of the design choices we made in this paper.

2 The hybridisation of deterministic ﬁnite state and vector automata

In this section, we (rather informally) describe the motivating example of this paper: the construction of a family of automata that naturally extends both deterministic ﬁnite state automata and ﬁnite automata weighted over a ﬁeld in the sense of Schtzenberger (i.e., automata in the category of ﬁnite vector spaces). The intuition should then support the categorical constructions that we develop in the subsequent sections.

Set automata (deterministic automata). Let us ﬁx ourselves an alphabet A. A deterministic automaton (or set automaton) is a tuple

A = (Q, i, f , (δa)a∈A) ,

in which Q is a set of states, i is a map from a one element set 1 = {0} to Q (i.e. an initial state), f is a map from Q to a two elements set 2 = {0, 1} (i.e. a set of accepting states), and δa is a map from Q to itself for all letters a ∈ A. Given a word u = a1 . . . an, the automaton accepts the map [[A]](u) : 1 → 2 deﬁned as:

[[A]](u) = f ◦ δu ◦ i

where δa1...an = δan ◦ · · · ◦ δa1 .

We recognize here the standard deﬁnition of a deterministic automaton, in which a word u is accepted if the map [[A]](u) is the constant 1, and rejected if it is the constant 0.

Vector space automata (automata weighted over a ﬁeld). Now, we can use the same deﬁnition of an automaton, this time with Q a vector space (over, say, the ﬁeld R), i a linear map from R to Q, f a linear map from Q to R (seen as a R-vector space as usual), and δa a linear map from Q to itself. In other words, we have used the same deﬁnition, but this time in the category of vector spaces. Given a word u, a vector space automaton A computes [[A]](u) : R → R as the composite described above. Since a linear map from R to R is only determined

1This distinction is usually not necessary, and we are not aware of its existence in the literature. It is crucial for us, thus we cannot use already existing results from the coalgebraic literature, e.g. [1].

3

by the image of 1, this automaton can be understood as associating to each input word u the real number [[A]](u)(1). We will informally refer to such automata in this section as vector space automata. Let us provide an example.

Leading example. For a word u ∈ {a, b, c}∗ let |u|a denote the number of occurrences of the letter a in u. Let us compute the map F which, given a word u ∈ {a, b, c}∗, outputs 2|u|a if it contains an even number of b’s and no c’s, and 0 in all other cases. This is achieved with the vector space automaton Avec = (Qvec = R2, ivec, f vec, δvec) where for all x, y ∈ R,

ivec(x) = (x, 0) , f vec(x, y) = x ,

δavec(x, y) = (2x, 2y) , δcvec(x, y) = (0, 0) .

δbvec(x, y) = (y, x) ,

One easily checks that indeed [[Avec]](u)(1) = F (u) for all words u ∈ A∗.

Can we do better? It is well known from Schtzenberger’s seminal work that the vector space automaton Avec is minimal, both in an algebraic sense (to be described later) as well as at an intuitive level in the sense that no vector space automaton could recognize F with a dimension one vector space as conﬁguration space: Avec is “dimension minimal.”

However, let us think for one moment on how one would “implement” the function F as an online device that would get letters as input, and would modify its internal state accordingly. Would we implement concretely Avec directly? Probably not, since there is a more economic2 way to obtain the same result: we can maintain 2m where m is the number of a’s seen so far, together with one bit for remembering whether the number of b’s is even or odd. Such an automaton would start with 1 in its unique real valued register. Each time an a is met, the register is doubled, each time b is met, the bit is reversed, and when c is met, the register is set to 0. At the end of the input word, the automaton would output 0 or the value of the register depending on the current value of the bit. If we consider the conﬁguration space that we use in this encoding, we use R R instead of R × R. Can we deﬁne an automata model that would faithfully implement this example?

A ﬁrst generalization: disjoint unions of vector spaces. A way to achieve this is to interpret the generic notion of automata in the category of ﬁnite disjoint unions of vector spaces (duvs). One way to deﬁne such a ﬁnite disjoint unions of vector spaces is to use a ﬁnite set N of ‘indices’ p, q, r . . . , and to each index p associate a vector space Vp. The ‘space’ represented is then {(p, v) | p ∈ N, v ∈ Vp}. A ‘map’ between duvs represented by (N, V ) and (N , V ) is then a pair h : N → N together with a linear map fp from Vp to Vh(p) for all p ∈ N . It can be seen as mapping each (p, v) ∈ N × Vp to (h(p), fp(v)). Call this a duvs map. Such duvs maps are composed in a natural way. This deﬁnes a category, and hence we can consider duvs automata which are automata with a duvs for its state space, and transitions implemented by duvs maps.

For instance, we can pursue with the computation of F and provide a duvs automaton Aduvs = (Qduvs, iduvs, f duvs, δduvs) where Qduvs = {(s, x) | s ∈ {even, odd}, x ∈ R} (considered as a disjoint union of vector spaces with indices even and odd and all associated vector spaces Veven = Vodd = R). The maps can

2Under the reasonable assumption that maintaining a real is more costly than maintaining a bit.

4

be conveniently deﬁned as follows:

iduvs(x) = (even, x) f duvs(even, x) = x

f duvs(odd, x) = 0

δaduvs(even, x) = (even, 2x) δbduvs(even, x) = (odd, x) δcduvs(even, x) = (even, 0)

δaduvs(odd, x) = (odd, 2x) δbduvs(odd, x) = (even, x) δcduvs(odd, x) = (odd, 0)

This automaton computes the expected F . It is also obvious that such automata over ﬁnite disjoint unions of vector spaces generalize both deterministic ﬁnite state automata (using only 0-dimensional vector spaces), and vector space automata (using only one index). However, is it the joint generalization that we hoped for? The answer is no...

Minimization of duvs automata. We could think that the above automaton Aduvs is minimal. However, it involved some arbitrary decisions when deﬁning it. This can be seen in the fact that when δcduvs is applied, we chose to not change the index (and set to null the real value): this is arbitrary, and we could have exchanged even and odd, or ﬁxed it abitrarily to even, or to odd. All these variants would be equally valid for computing F .

It is a bit diﬃcult at this stage to explain the non-minimality of these automata since we did not introduce the proper notions yet. Let us try at a high level, invoking some standard automata-theoretic concepts. The ﬁrst remark is that every conﬁguration in Qduvs is ‘reachable’ in this automaton: indeed (even, x) = iduvs(x) and (odd, x) = δbduvs ◦ iduvs(x) for all x ∈ R. Hence there is no hope to improve the automaton Aduvs or one of its variants by some form of ‘restriction to its reachable conﬁgurations’. Only ‘quotienting of conﬁgurations’ remains. However, one can show that none among Aduvs and the variants mentioned above is the quotient of another. Keeping in mind the Myhill-Nerode equivalence, we should instead merge the conﬁgurations (even, 0) and (odd, 0) since these are observationally equivalent:

f duvs ◦ δuduvs(even, 0) = 0 = f duvs ◦ δuduvs(odd, 0) for all words u ∈ A∗.

However, the quotient duvs obtained by merging (even, 0) and (odd, 0), albeit not very intuitive, consists of one index associated to a two dimensional vector space, which is essentially an indexed version of the vector space automaton Avec computed before. At this stage, we understand that minimising in the category of duvs is not very helpful, as we do not obtain the desired optimisation.

How to proceed from here. The only reasonable thing to do is indeed to merge (even, 0) and (odd, 0), but we have to be more careful about the precise meaning of ‘quotient’. A possibility is to add explicitly equivalence classes in the deﬁnition of the automaton. However, category theory provides useful concepts and terminology for deﬁning these objects: colimits, and more precisely the free co-completion of a category. In the previous paragraph, we have shown that the category of duvs – which is itself the free completion of Vec with respect to ﬁnite coproducts – is not a good ambient category for our purposes. We need more colimits, so that the notion of ‘quotient’ is further reﬁned. At the other extreme, we could consider the free completion with respect to all colimits, which, informally, consists of objects obtained from the category using copying and gluing. We will explain later in Section 5 why we choose to not use this completion. Intuitively, by adding all colimits we glue the vector spaces “too much”, and not only we loose a geometric intuition of the objects we are dealing

5

with, but we may run into actual technical problems when it comes the existence of minimal automata.

Instead, we restrict our attention to a class of colimits (which strictly contains coproducts) for which diﬀerent spaces in the colimit can be “glued” together along subspaces, but which do not contain implicit self folding (i.e., such that an element of a vector space is not glued to a distinct element of the same vector space, directly or indirectly). E.g., we can describe ‘two one-dimensional spaces, the 0-dimensional subspaces of which are identiﬁed through a linear bijection’. In this way we obtain the new category of glued vector spaces and hybrid set-vector space automata, corresponding to Glue(Vec)-automata in the rest of the paper.

Generic arguments of colimits provide the language for describing these objects, but do not solve the question of minimality. In particular, we are interested in automata whose space of conﬁgurations is a ﬁnite colimit belonging to the class described above. The categorical development in this work addresses the minimization problem for hybrid automata. An intuition in the case of gluing of vector spaces. In the case of gluing of vector spaces, it is possible to isolate a combinatorial statement that plays a crucial role in the existence of minimal hybrid set-vector automata:

(a) Any subset of a ﬁnite-dimensional vector space admits a minimal cover as a ﬁnite union of subspaces. (b) Furthermore, there is a unique such cover which is a union of subspaces which are incomparable with respect to inclusion.

For instance, in the original vector space automaton Avec, the states that are reachable in fact all belong to R × {0} ∪ {0} × R, and this is the minimal cover as in (a) of these reachable conﬁgurations. This subset of R2 has the structure of two R-spaces. These happen to intersect at (0, 0), hence it is necessary to glue them at 0 to faithfully represent this set of reachable conﬁgurations. Thanks to (b) this decomposition is canonical, and hence can be used for describing the automaton.

3 Automata in a category

In this section, we provide the general deﬁnition for a (ﬁnite word) automaton in a category. We also isolate properties guaranteeing the existence of minimal automata. Though presented diﬀerently, the material in the ﬁrst subsection is essentially a slight variation around the work of Arbib and Manes [3], which introduced a notion of automaton in a category and, moreover, highlighted the connection between factorization systems of the ambient category, duality and minimization. In the remaining subsections we develop a reﬁnement of this approach to minimization, and introduce a notion of factorization system through a subcategory.

6

3.1 Automata in a category, initial automaton, ﬁnal automaton

Deﬁnition 1 (automata). Let C be a locally small category, I and F be objects of C, and A be some alphabet. An automaton A in the category C (over the alphabet A), for short a C, I, F -automaton (or simply C-automaton when I and F are obvious in the context), is a tuple (Q, i, f , δ), where Q is an object in C (called the state object), i : I → Q and f : Q → F are morphisms in C (called initial and ﬁnal morphisms), and δ : A → C(Q, Q) is a function associating to each letter a ∈ A a morphism δa : Q → Q in C. We extend the function δ to A∗ as with δ being the identity morphism on Q and δwa = δa ◦ δw for all a ∈ A and w ∈ A∗.

A morphism of C, I, F -automata h : A → A is a morphism h : Q → Q in C between the state objects which commutes with the initial, ﬁnal and transition morphisms:

Q

i

Q δa Q

Qf

I

h

h

h

h

F

(1)

i

Q

Q

Q

δa

Q

f

Example 2. The two guiding instantiation of this deﬁnition are as follows.

When the category C is Set, I = 1 and F = 2, we recover the standard notion of a deterministic and complete automaton (over the alphabet A∗). In the second

case, when C is Vec over a base ﬁeld K, I = K and F = K, we obtain K-weighted automata. Indeed, if Q is isomorphic to Kn for some natural number n, then linear maps i : K → Q are in one-to-one correspondence with vectors Kn. The same holds for linear maps f : Q → K, hence i and f are simply selecting an initial, respectively, a ﬁnal vector.

Deﬁnition 3 (languages and language accepted). A C, I, F -language (or Clanguage when I and F are clear from the context) is a function L : A∗ → C(I, F ).

We say that A accepts the language L if L(w) = [[A]](w) := f ◦ δw ◦ i for all w ∈ A∗. Let AutoC(L) denote the category of C, I, F -automata for L, that is, the category whose objects are C, I, F -automata that accept the language L and whose arrows are morphisms of C, I, F -automata3.

Lemma 4. If the coproduct w∈A∗ I exists in C, then AutoC(L) has an initial object initC(L). If the product w∈A∗ F exists in C, then AutoC(L) has a ﬁnal object finalC(L).

In the case of Set, these automata are well known. The ﬁrst one has as states A∗, as initial state ε, and when it reads a letter a, its maps w to wa. Its ﬁnal map sends the state w to L(w)(0). There exists one and exactly one morphism from this automaton to each automata for the same language. The generalisation of this construction is that the state space is the coproduct of A∗many copies of I. The ﬁnal automaton is known as the automaton of ‘residuals’.

3If A accepts the language L and h : A → A is a morphism of C, I, F -automata, then A also accepts the language L. Hence, AutoC(L) is a ‘connected component’ in the category of all C, I, F -automata.

7

Its set of states are the maps from A∗ to 2. The initial state is L itself, and when reading a letter a, the state S is mapped to w → S(aw). The ﬁnal map sends S to S(ε). The generalisation of this construction is that the state space is the product of A∗-many copies of F .

3.2 Factorizations through a subcategory

It is important in the development of this paper to distinguish the category AutoC(L) in which the initial and ﬁnal automata for a language L exist (recall Lemma 4) and which contains ‘inﬁnite automata’, from the subcategory, named AutoS (L) that is used for the concrete automata (with state object in S) which are intended to be algorithmically manageable. In this section, we provide the concept of factorizing through a subcategory, which articulates the relation between these two categories.

Deﬁnition 5 (factorization through a subcategory). Assume S is a subcategory of C. An arrow f : X → Y in C is called S-small if it factors through some object S of S, that is, f is the composite X u S v Y for some u : X → S and v : S → Y .

A factorization system through S on C (or simply a factorization system on C if C = S) is a pair (ES , MS ) where ES and MS are classes of arrows in C so that the codomains of all arrows in ES , the domains of all arrows in MS are in S, and the following conditions hold:

1. ES and MS are closed under composition with isomorphisms in S, on the right, respectively left side.

2. All S-small arrows in C have an (ES , MS )-factorization, that is, if f : X → Y factors through an object of S, then there exists e ∈ ES and m ∈ MS , such that f = m ◦ e.

3. The unique (ES , MS )-diagonalization property holds: for each commutative diagram X eT

f

g

(2)

u

SmY

with e ∈ ES and m ∈ MS , there exists a unique diagonal, that is, a unique morphism u : T → S such that u ◦ e = f and m ◦ u = g.

Using standard techniques, we can prove that whenever (ES , MS ) is a factorization system through S on C, both classes ES and MS are closed under composition, their intersection consists of precisely the isomorphisms in S, and,

as expected, that (ES , MS )-factorizations of S-small morphisms are unique up to isomorphism.

Example 6. Instantiating (C, S) to be (Set, Setﬁn) yields a natural factorization system through Setﬁn on Set (as the restriction of the standard (epi,mono)factorization system on Set to Setﬁn-small morphisms, i.e., the maps of ﬁnite image). Over these categories Setﬁn-automata are deterministic ﬁnite state automata inside the more general category of Set-automata which are deterministic

8

(potentially inﬁnite) automata. The example (Vec, Vecﬁn) was already mentioned. In this case, being Vecﬁn-small is equivalent to having ﬁnite rank.

Notice that for (C, S) = (Set, Setﬁn) or (Vec, Vecﬁn), the factorization systems through the subcategories are obtained simply by restricting the factorization systems on Set, respectively Vec. This is because, in these cases S is closed under quotients and subobjects in C. The category Glueﬁn(Vecﬁn) used in this paper is closed under quotients, but in general not under subobjects (and this is the important reason for this extension of the standard notion of factorization). This is also a case in which there is a factorization system in the category C, that coincide over S with factorizing through S, but for which factorizing in C of an S-small morphism and factorizing it through S yield diﬀerent results.

A factorization system on C lifts naturally to categories of C-valued functors. Automata being very close in deﬁnition to such a functor category, factorization systems also lift to them. Lemma 7 shows that this is also the case for factorization systems through S, assuming of course that the input and output objects I and F belong to S.

Lemma 7. Whenever (ES , MS ) is a factorization system through a category S then (EAutoS(L), MAutoS(L)) is a factorization system through AutoS (L) for the category AutoC(L), where EAutoS(L) (resp. MAutoS(L)) contains these AutoC(L)morphisms that belong to ES (resp. to MS ) as C-morphisms.

3.3 Minimization through a subcategory

In this section, we show how the joint combination of having initial and ﬁnal automata for a language, as given by Lemma 4, together with a factorization system through a subcategory S yields the existence of a minimal S-automaton for small C-languages.

We make the following assumptions: (ES , MS ) is a factorization system through S on C, and L is a C-language accepted by some S-automaton such that there exist an initial initC(L) C-automaton and a ﬁnal C-automaton finalC(L) for L.

Deﬁnition 8 (minimal automaton). The minimal C-automaton for L, denoted minS (L), is the4 S-automaton for L obtained by (EAutoS(L), MAutoS(L))factorization of the unique AutoS (L)-small morphism from initC(L) to finalC(L).

Theorem 9. For all S-automata A for L satisfying the above assumptions, we have

minS (L) ∼= obsS (reachS (A)) ∼= reachS (obsS (A)) ,

in which

• reachS (A) is the result of applying an (EAutoS(L), MAutoS(L))-factorization to the unique AutoS (L)-morphism from initC(L) to A, and

• obsS (A) is the result of applying an (EAutoS(L), MAutoS(L))-factorization to the unique AutoS (L)-morphism from A to finalC(L).

4It is unique up to isomorphism according to the diagonal property.

9

This theorem does not only state the existence of a minimal automaton, it also makes transparent how to make eﬀective its construction: if one possesses both an implementation of reachS and obsS , then their sequencing minimises an input automaton. From the above theorem it immediately follows that minS (L) is both an EAutoS(L)-quotient of a MAutoS(L)-subobject of A and a MAutoS(L)subobject of an EAutoS(L)-quotient of A: the minimal automaton divides every other automaton for the language.

Proof idea. The proof is contained in the following commutative diagram, in which denotes AutoC(L)-morphisms in EAutoS(L), and AutoC(L)-morphisms in MAutoS (L):

A

initC (L)

reachS (A) obsS (reachS (A)) finalC(L)

minS (L)

That obsS (reachS (A)) is an (EAutoS(L), MAutoS(L))-factorization of the unique AutoC(L)-morphism from initC(L) to finalC(L) follows since EAutoS(L) is closed under composition. By the unique diagonal property, it is isomorphic to minS (L). The case reachS (obsS (A)) is symmetric.

3.4 A special case of factorization through

So far, the description of factorization and minimization of automata is very generic. Hereafter, the classes ES and MS are constructed along a particular principle which we describe now. In the next sections we will instantiate this construction when S is the subcategory Glueﬁn(Vecﬁn) of glued vector spaces.

In this section we ﬁx an (E, M )-factorization system on C and a subcategory S → C.

Deﬁnition 10. An S-extremal epimorphism5 in C is an arrow e : X → S in C, with S an object in S, such that if e = m ◦ g where m is in M with domain in S, then m is an isomorphism. We set MS to be the class of arrows in M with domain in S, and ES to be the class of S-extremal epimorphisms.

Deﬁnition 11. An MS -subobject in S of an object X of C is an equivalence class up to isomorphism of a morphism S → X belonging to M , where S is an object of S. The MS -subobject S → X is called proper if it is not an isomorphism.

Lemma 12. Assume the following conditions hold:

1. all arrows in M are monomorphisms in C,

2. S is closed under E-quotients, i.e., if e : S → T is in E with S in S, then T is isomorphic to an object of S,

3. the intersection of a nonempty set of MS -subobjects of an object X of C exists and is an M S-subobject of X, and,

5Note that S-extremal epimorphisms need not be epimorphisms in C.

10