Coequations and Eilenberg-type Correspondences

An Eilenberg–type correspondence is a one–to–one correspondence between varieties of algebras and the so–called “varieties of languages”. They have been broadly studied in the literature since Eilenberg’s variety theorem in the 1970s. The concept of a variety of algebras is a well–known concept in universal algebra which, by Birkhoff’s theorem, is the same as a class of algebras satisfying some given equations. However, the concept of a variety of languages is less known and its defining properties have not been fully explained in the literature, they have been ad hoc definitions. The work in this thesis fully explains what varieties of languages are and where their defining properties come from. In fact, varieties of languages are duals of equational theories, that is, coequational theories.

The fact that varieties of languages are duals of equational theories not only allows us to fully understand Eilenberg–type correspondences, but also to get a general categorical version for Eilenberg–type correspondences from which we can derive countless instances. Some of those instances have been proved separately and published in different papers. Another advantage of this understanding is the simplification of proofs for particular Eilenberg–type corerspondences found in the literature. Most of the proofs in the literature follow the same idea as Eilenberg by proving the existence of syntactic algebras in order to obtain the desired correspondence. The work in this thesis shows that existence of syntactic algebras is not a necessary condition for the existence Eilenberg–type correspondences.

After introducing some basic concepts and fixing the notation, we start by studying two particular structures: deterministic automata and weighted automata. In both cases we show what equations and coequations for these automata are and what it means for an automaton to satisfy them. The concept of a coequation, which is the dual of an equation, is less known in the literature and we fully explain them for the cases of deterministic automata and weighted automata. Additionally, we show duality results between equations and coequations for automata.

We develop a general abstract theory of equations and coequations in Chapter 4. In the case of equations, we define equations for algebras for an endofunctor and also equations for Eilenberg–Moore algebras. We present a similar work for the case of coequations, that is, coequations for coalgebras for an endofunctor and coequations for Eilenberg–Moore coalgebras. We define categories of equations and coequations. Then, we show how dualities on the base categories can be lifted, under mild assumptions, to a duality between the categories of algebras and coalgebras and also how the duality is lifted to categories of equations and coequations. We also obtain the previous liftings for the case of Eilenberg–Moore algebras and coalgebras.