The power of polymorphisms: the triangle of universal algebra, model theory, and theoretical computer science - Part 1
ABSTRACT. I am going to survey tight connections between universal algebra, model theory, and theoretical computer science (specifically, constraint satisfaction) established in the past 25 years, and try to provide the audience with an intuition for them. At the center of this tutorial will be the notion of a polymorphism.
A polymorphism of a relational structure A is a multivariate function on the structure leaving all relations of A invariant. It is a generalization of an endomorphism, which is a unary function under which A is invariant, or of an automorphism, which is a unary function under which A is (strongly) invariant.
Similarly to the automorphism group or the endomorphism monoid of A, the set of all polymorphisms of A, called the polymorphism clone Pol(A) of A, provides us with structural information about A, in particular which other structures A can define, interpret, or construct (in a certain precise way). Since the polymorphism clone Pol(A) consists of multivariate functions on the same domain A, it can be viewed as an algebra, just like the set of automorphisms can be viewed as a group. Therefore, algebraic methods can be used to investigate the polymorphism clone Pol(A), and hence derive information about the original structure A. This is the link between model theory and universal algebra.
Every relational structure A defines a computational problem, the Constraint Satisfaction Problem CSP(A), where given a list of variables and atomic statements (called constraints) about these variables in the language of A one has to find a solution, i.e., a map from the variables into A such that all atomic statements are satisfied. This kind of computational problem is extremely general: every computational problem is polynomial-time (Turing) equivalent to CSP(A) for a suitable structure A. Since the polymorphisms of A leave the set of solutions of any instance of CSP(A) invariant, they are central in the study of the computational complexity of CSP(A): in fact, the computational complexity of CSP(A), certain model-theoretic properties of A, and the algebraic structure of the polymorphism clone Pol(A) are tightly connected, with nontrivial implications holding in all directions of this triangle.
A Categorical Approach to Automata Learning and Minimization - Part 1
ABSTRACT. In this tutorial, we present generic algorithms for the minimization and learning of several forms of automata, beginning with deterministic automata, weighted automata, and sequential transducers.
We first introduce these different forms of automata from an abstract and unifying perspective. An automaton can be viewed as a machine that processes an input according to its structure and produces an output in a given space of values (such as Boolean values, probabilities, weights over a semiring, or words over an alphabet).
We provide a brief introduction to the basic notions of category theory needed to understand our approach. In particular, we view automata as functors from an input category, which describes the structure of the inputs, to an output category, which describes the corresponding computational effect.
We show how results on automata minimization can be formulated at this level of generality. We identify sufficient conditions on the output category that ensure the existence of an algebraically minimal automaton within a given class. This perspective helps explain why minimization works for some classes of automata but fails for others.
We then give an overview of Angluin’s L* algorithm and its variants, and show how the minimization results can be reused to obtain a generic learning algorithm for functorial automata. Finally, we illustrate this framework with a new application to automata weighted over number rings, as described in a recent paper of Aristote et al.
