Okay, welcome to this presentation. This is about joint work with Lutz Schreuder on automata learning from an algebraic and category-theoretic point of view.

Automata learning is about the following problem. You're given a black box system, some piece of hardware or software that you don't know any internals about, and you would like to learn a formal model of that system that accurately describes its behavior. For instance, in order to be able to apply model checking techniques to it.

And the standard way to achieve this is by running tests on the system. So you give it certain cleverly chosen inputs, see what happens, and use the information gained from these tests to generate a first hypothesis, some formal model that you think

might be the right one. And then one runs further tests, improves the hypothesis in a step-by-step fashion, and hopefully after finitely many iterations of this process, one ends up with the correct model of the black box. Now, the model that you want to learn could be pretty much anything, depending on

the kind of behavior that you are interested in. So it could be something as simple as a finite automaton, but it could also be something more complex, like, for instance, a squishy automaton or a register automaton. And the standard way to develop learning algorithms is to come up with your own algorithm

for every type of model. And of course, one slight disadvantage of this ad hoc approach is that many of the underlying ideas and constructions and proofs reappear in a very similar form in these different algorithms. And you need to redo a lot of the work every time.

So there are lots of structures that appear in these learning algorithms that have a very strong generic flavor. Therefore, it seems to be natural to pursue a categorical approach to automaton learning that abstracts away from particular models and instead investigates how to learn generic

state-based systems modeled as either co-algebras or algebras. Now, there has been some very interesting recent work in this direction. The first I would like to mention is the Kalf paper by Van Hert, Samartino, and Silber, who modeled several concepts that tend to reappear in learning algorithms in an abstract

categorical framework. The same authors also came up with an algorithm for learning automata with side effects modeled as certain co-algebras in the category of sets. And finally, last year, Baloko, Kupke, and Roth presented a generic algorithm for learning

arbitrary co-algebras in sets where the semantics is given by a co-algebraic logic. So this previous work has a very co-algebraic flavor, as you see. And what I would like to present here is a more algebraic approach to automata learning

that rests on the idea of modeling formal languages and their recognition using monads. This has been quite successful in recent years to develop a generic approach to algebraic language theory, so the kind of language theory that replaces automata by algebraic structures.

And it turns out to be particularly well-suited for things like omega-regular languages, cost functions, and others that cannot be conveniently modeled using co-algebras but have a very natural algebraic point of view. As the basis of all this, let us start by discussing how to learn automata in a category.

And for this purpose, let us first consider the case of classical deterministic automata. So we are given an unknown finite automaton, as usual given by a set of states q, initial and final states, and transitions that can either be modeled algebraically as a function

from sigma times q to q, where sigma is the input alphabet, or co-algebraically as a function from q into the function space from sigma to q, just by carrying. So such an unknown automaton is given, and the goal is to learn an automaton that is

equivalent to q by asking questions to a teacher, which kind of idealizes the idea of running tests on a black box. And there are two types of questions that we are allowed to ask to the teacher. The first one is a membership query, given some input word w, does it lie in the language

of q? And the second one is an equivalence query, given some hypothesis, some automaton that we think might be the right one, we can ask if it is actually equivalent to q. And well, if yes, then we have won, then we have found a correct model for q.

And otherwise, the teacher will give us a counter example, some word that is accepted by one of the two automata, but not by the other one. Now, to understand the idea of the learning algorithm, let us consider two interesting

maps that are related to the unknown automaton q. The upper one, Eq, takes a word w from sigma star and maps it to the state reached on input w in the automaton. And the other one, Mq, maps a state of the automaton to the language accepted by

the state if we use it as the initial state of the automaton. So the composite of these two maps, Mq composed with Eq, is just a map that takes two words v and w and checks whether the word vw lies in Lq.

Now, if we knew this composite map, then we could actually compute the minimal automaton of q, and therefore, we would be done because the kernel of this composite is just the well-known narrowed congruence of the language of q. And from the narrow congruence, we can easily compute the minimal automaton.

But of course, we don't know this composite because the automaton q is unknown, and therefore, we cannot do this right away. However, what we can compute are finite approximations of this map. So if we choose two finite sets of words s and t, say the words in s have length less

than n and the words in t have length less than k, then we can compute the map that we get by starting in this diagram in s, taking the whole round tour and ending in d,2.

This map is just a domain codomain restriction of Mq composed with Eq. So it takes a word s from s and a word t from t and asks whether the word s,t is contained in the unknown language. And because s and t are finite sets, we can actually compute this using finitely

many membership queries. This map is usually called an observation table because it can be represented as a binary S times t matrix. So we can compute this map H s,t, and therefore, we can also compute its image, which we call capital H s,t. And now the key idea of the learning algorithm is to define an automata structure on this

image set, and the definition is actually quite simple. So whenever you are in the image of some word s and read an input letter a, then there is a transition to the image of the word s,a. Of course, there is a potential problem.

These transitions in general have no reason to be well-defined because you need to make sure that, for example, the element on the right-hand side is actually an element of the image set capital H s,t. This is called closeness. And you also need to make sure that the transition does not depend on the choice of

representatives. This is called consistency. And the idea is now whenever you encounter a transition that is not well-defined because it's not closed or not consistent, then you simply extend the sets s or t. So you add some words to s or t that fix the non-well-definedness.

And so we have the following algorithm that goes back to the work of Dana Englund from the 1980s. So the goal is to learn an automaton equivalent to an unknown automaton Q. And to do this, we start by initializing the sets s and t to the empty word.

Then we keep extending s and t until this pair is closed and consistent, so until the hypothesis on capital H s,t is well-defined. Then we ask whether this hypothesis is actually equivalent to the unknown automaton Q by asking an equivalence query. If so, then we return the automaton H s,t because then we have found a correct hypothesis.

And otherwise, we get a counterexample that we add to the set s together with all its prefixes. And then all this is repeated until after polynomially many iterations, we come up with a correct hypothesis.

So this is a fairly simple and ingenious algorithm. And to some extent, it forms the basis of all active learning algorithms out there in the literature. So even for models that are more complicated than finite automata, the algorithms usually follow the basic structure of Englund s algorithm and are ultimately modifications of it.

And therefore, it is natural to ask whether we can come up with a categorical version of this algorithm that not only captures the classical one that we have shown here, but also its generalizations and extensions in a kind of uniform way.

To motivate this categorical approach, let us again look at classical deterministic automata and let us observe that the possibility to view the transitions both as an algebra and as a co-algebra rests on the fact that the category of sets is Cartesian

closed. So the functor sigma times identity is left adjoint to the function space functor. And let us also observe that the set sigma star of finite words can be seen as the initial algebra for the functor 1 plus sigma times, and that the language of Q can

be described as taking the unique homomorphism from the initial algebra sigma star into the automaton Q. We call that this is the map that takes a word to the state reached in Q, and composing this map with the final state predicate f. So this gives a purely categorical view of the language of Q.

And this motivates a categorical generalization of this situation, going back to the work of R.B. Patmanis in the 1970s. So we now consider an abstract adjoint situation like this, so two adjoint functors f and

g on category C. And we define an f-automaton to be given by the following diagram. So we have an object Q of states, we have two morphisms i and f representing initial and final states, where capital I and capital O are just fixed objects in the category,

and we have a transition structure that can either be modeled as an algebra for the functor f, or by adjointness as a co-algebra for the functor g. And the language of such an automaton is now given by forming the initial algebra for the functor i plus f, which we denote by mu f i, and composing the unique homomorphism

from mu f i into Q with the final state morphism f. So all this is a direct generalization of what we have seen on the previous slide. Now the nice feature of this categorical generality is that it not only covers classical

deterministic automata, but also many other interesting types of automata. So for instance, by going to the category of vector spaces and replacing the product by the tensor product, one gets exactly weighted automata. By going to semilatuses, one gets a notion of automaton that can be interpreted as non-deterministic

automata, where the idea is that one can represent a structure like this as a non-deterministic automaton whose states are the joined irreducible elements of the semilatous Q. And finally, by going to the category of nominal sets, one gets various notions of nominal automata

with possible allocation and deallocation of resources by combining binding and freshness functors in a suitable way. So without going into much detail here, this shows that lots of interesting kinds of automata are captured by this abstract Arbib-Etmanis framework.

And let me point out that for four of the types of automata that I listed here, learning algorithms are already known. So we have seen the classical angloin algorithm for deterministic automata, and there are also versions of it for weighted automata and non-deterministic automata and nominal automata without binding. But for the two notions

of nominal automata with binders, learning algorithms are not known to the best of my knowledge. And so having a learning algorithm for general Arbib-Etmanis type automata would not only give a nice uniform view of these existing algorithms,

but also directly apply to interesting new settings. So the goal of our generalized learning algorithm is to learn an automaton that is equivalent to an unknown automaton like this. And to explain how this works, let us again look

at the diagram that explains the classical angloin algorithm for deterministic automata, and see if we can interpret what happens there from a category theoretic point of view. So we have already seen that this set sigma star here is actually the initial algebra for the functor 1 plus sigma times, and we can also observe that this chain of finite

approximations of sigma star is actually the initial chain for that functor. And similarly, we can see that the set of languages or predicates on sigma star down here is the final co-algebra for the functor 2 times function space, and that this co-chain

of finite approximations is actually the final co-chain for this functor. So you can probably anticipate where this is going. In our categorical setting, we now replace the set sigma star of words by the initial algebra for the functor i plus f.

We replace this upper chain of approximations by the initial chain for this functor. Likewise, we replace the set of predicates on sigma star down here by the final co-algebra for the functor o times g, and we replace this co-chain of approximations by the final

co-chain of this functor. And finally, s and t, which originally were sets of words, are now just subobjects and quotients in this diagram. So this is now a completely categorical diagram, and it turns out that one can phrase the learning algorithm at

this level of abstraction. So this is the categorical angloin algorithm. Its statement is actually almost identical to the classical one, but of course these blue highlighted parts need to be explained. Now we need to explain what it means to be closed and consistent, we need to explain how hypotheses are constructed,

we need to explain what a counterexample is, because all these concepts were originally in the classical angloin algorithm concepts dealing with words and sets and functions, and now we have to explain them in a purely diagrammatic, categorical way at the level

of this abstract diagram. And so I will not go into any technical details here, but it can be done using techniques like factorizations, diagonal fill-ins, and something like that. And so this algorithm is actually a completely categorical algorithm that can be stated at the level of the abstract Abit Menes setting. Of course, the crucial question to ask

about any learning algorithm is, does it actually terminate? Because if you look at this algorithm, it is conceivable that it could loop through these steps indefinitely without ever finding a correct hypothesis. And unsurprisingly, to guarantee termination of the algorithm,

we need to assume something about the finiteness of the unknown automaton Q. And since Q is now in this setting not a set of states, but an abstract object in a category, we first need to explain what the word finite actually means in this setting.

And the correct notion of finiteness in this context is the following one. We say that an object Q in the category C is finite if every proper ascending chain of sub-objects is finite, and likewise, every proper ascending chain of quotients is finite. And in this case, we

have many of these chains. So it turns out that in many categories, this notion of finiteness is fairly natural and coincides with the expected one. So for instance, in vector spaces, finite means exactly finite dimensional and the size

is the dimension of the space. And now we have the following general correctness theorem for our learning algorithm. It states that whenever the unknown automaton Q is finite in this categorical sense, then the learning algorithm terminates after a linear number of steps in the size of Q, and the automaton it returns is the minimization of

Q. So in the process of learning the automaton, it is actually also minimized. Okay, so to sum up, we have seen that the generalized angloin algorithm covers quite some ground, including known and new learning algorithms. I should emphasize that although

these algorithms that I listed here are now covered by the categorical one in a uniform fashion, this does not mean that they are just trivial, because in every single case, you still need to explain how to represent the objects and morphisms in this abstract diagram

by proper finite data structures, which typically require some insight into the underlying category. So there is still some work to be done. But the nice feature of this categorical modeling is that the correctness theorem and parts of the complexity analysis come completely for free as instances of the general categorical results. So there is no need anymore

to redo these proofs in every single instance. Okay, so this concludes the first part of this talk. And next I would like to explain how to extend our setting to types of languages that

cannot be directly modeled using categorical automata, but can be modeled using monads. So part two of this talk is about learning monad recognizable languages. So the setting is now extended as follows. We still have these two objects I and O that represent inputs and outputs. And on top of that, we now assume that we are given a monad

T on C that represents some kind of algebraic theory. And in this setting, the language is now defined to be a morphism from TI to O. And we say that a language is recognizable if it factorizes through some finite T algebra. So if we have a triangle like this.

So for instance, to capture classical regular languages, we can take the semigroup monad on the category of sets. And similarly, if we want to capture omega regular languages, we can take the omega semigroup monad. So an omega semigroup is basically a semigroup

with an infinitary multiplication. And the corresponding monad is a monad on two sorted sets that maps the two sorted set I empty set to the set of finite and infinite words. And one can show that the languages recognizable by this monad are exactly

languages accepted by finite Buechier automata. And similarly, many other kinds of languages like data languages or cost functions and others can be modeled by suitable monads over suitable categories. So this concept of algebraic recognition by monads is fairly ubiquitous and

captures many interesting types of languages. So we would like to get a handle on learning unknown T recognizable languages. And our basic approach and idea to do this is to reduce the task of learning such a language to the task of learning a suitable finite

automaton in the category C. And then we can simply apply the generalized angloin algorithm or any other algorithm for learning automata in C. So the crucial thing here is certainly this reduction process in step one. And to get the

idea of how this works, let us look at the case of omega regular languages. And let us observe that every language of infinite words L induces in a natural way a language of finite words, the so-called set of lassos that consists of all pairs of finite words U and V,

so that the infinite word UV to the W lies in the language L. And now the crucial feature of this construction is that it preserves regularity. So whenever L is an omega regular language, then the lasso language is a regular language. And this reduction is ultimately

the basis of all known learning algorithms for omega regular languages. And now it turns out that this idea that you can project some complicated kind of language to a simple regular language can be generalized to our monad setting using the concept of an

automata presentation of a monad. So the basic idea of an automata presentation is to look at the free T-algebra on the object I of inputs and to represent its algebraic structure in terms of a suitable automata structure. So formally, an automata presentation

of TI is given by an F-algebra structure on TI for some suitable functor F, so that finite quotient F-algebras of TI correspond uniquely to finite quotient T-algebras of TI. So in other words, there is a one-to-one correspondence between

commutative diagrams like this one and commutative diagrams like this one. So how is this useful? Well, given such a presentation, we can now turn a language over the monad T, a morphism from TI to O, into an automata-theoretic language

by precomposing it with a unique homomorphism from the initial algebra for the functor I plus F into the automaton TI. And note that this is exactly the kind of language that F-automata can accept. It's a morphism from the initial algebra mu F I into the output object O. And now let us note that if we assume this morphism E-T-I to be epimorphic,

then the language L is actually uniquely determined by its linearization. So in order to learn L, it suffices to learn an automaton for the linearized language

to get a complete representation of the language L. And for that reason, the following theorem is interesting. It states that if we assume the unknown language L to be recognizable, which is recognized by some finite T-algebra, then its linearization is regular in the sense

of being accepted by some finite F-automaton. And this means that we can use the generalized angloin algorithm to learn the linearization of L and therefore indirectly the language L itself. So this theorem is quite useful, and since automata presentations turn out to exist for

pretty much every interesting monad in formal language theory, it is also widely applicable. So for illustration, let us briefly look at the case of the omega semigroup monad that, as we have seen, represents omega regular languages. So here we can present the free

omega semigroup consisting of finite and infinite words by a suitable two-sorted sigma automaton, where the idea is that the alphabet sigma and the transitions of the automaton capture the omega semigroup structure. So for instance, if you look at this blue highlighted part, there is an input letter called omega and the transition that says if you are in the

state w from i plus, so a finite word, and you read the letter omega, then you can go to the state w to the omega, which is now an infinite word. So this transition captures the fact that we can take infinite powers in an omega semigroup.

And one can see that if L is a language of infinite words, then the linearization of L is essentially a two-sorted version of the LASSO language of L. So in particular, the fact that the LASSO construction preserves regularity is a special case of this general

theory. Okay, so to conclude, we have this generic strategy for learning recognizable languages over pretty much any monad. Of course, at this stage, this is still fairly high level, so it will certainly be interesting to turn this generic approach into an implementation level

algorithm and tool that we can benchmark against tailor-made learning algorithms for specific kinds of languages. And something that might be helpful in this direction is the recent work on co-algebraic minimization algorithms and their implementation, because we have seen that learning is ultimately just an interactive version of minimization,

and so one can expect that some of the techniques developed in this paper also apply to the learning framework. Okay, so this concludes my talk. Thank you for your interest.