Coequations and Eilenberg-type Correspondences

Julian Rodrigo Salamanca Tellez

promotor: prof. dr. J.J.M.M. Rutten (RU and CWI)
copromotor: dr. M.M. Bonsangue (UL)
Radboud University
Date: 24 April 2018
Thesis: PDF


An Eilenberg–type correspondence is a one–to–one correspondence between vari- eties 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 con- cept 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 equa- tions. 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 corre- spondence. 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 study- ing 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.

In Chapter 5, we provide a categorical version of Birkhoff’s theorem which, for the purpose of this thesis, we state as a one–to–one correspondence between varieties of algebras and equational theories. We introduce the categorical concept of an equational theory, which is a new definition whose main purpose is to explain the concept of a variety of languages used in Eilenberg–type correspondences. We also provide a Birkhoff’s theorem for varieties of finite algebras, for local varieties of algebras and for local varieties of finite algebras.

In Chapter 6, we collect all general background and categorical development of equations, coequations and Birkhoff’s theorem to obtain abstract theorems for Eilenberg–type correspondences. All of this is represented by the slogan

“Eilenberg–type correspondences = Birkhoff’s theorem for (finite) algebras + duality”,

which explains the real nature of Eilenberg–type correspondences. We state a gen- era theorem for Eilenberg–type correspondences for the following four cases: va- rieties of algebras, pseudovarieties of algebras, local varieties of algebras and local pseudovarieties of algebras.

As an application of our general results we show, in Chapter 7, some of the particular instances we can get from our general theorems from Chapter 6. We derive a total of 64 correspondences. To the best of our knowledge, only 20 of them are known in the literature. Most of these known correspondences were proved and published separately in at least 12 different papers. The remaining 44 new correspondences that we show are for varieties and local varieties of algebras, which have been less studied in the literature.