Automata and the algebra-coalgebra duality:
on varieties and covarieties, on transition monoids
and their dual
Jan Rutten, CWI and Radboud University Nijmegen
Because of the isomorphism (X x A) -> X = X -> (A -> X) the transition structure of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra  and as a coalgebra [2,3]. This algebra-coalgebra duality goes back to Arbib and Manes , who formulated it as a duality between reachability and observability, and is ultimately based on Kalman's  duality in systems theory between controllability and observability. Recently [6,7], it was used to give a new proof of Brzozowski's minimization algorithm for deterministic automata. In this talk, we will discuss deterministic automata as an elementary and typical example for the combined use of algebraic and coalgebraic methods in computer science. The algebra-coalgebra duality of automata will, more specifically, serve as a common perspective for the study  of both varieties and covarieties, which are classes of automata and languages defined by equations and coequations, respectively. Along the way, we will establish a first connection with Eilenberg's definition  of varieties of languages, which is based on the classical, algebraic notion of varieties of (transition) monoids. This is joint work with Adolfo Ballester-Bolinches and Enric Cosme-Llopez (University of Valencia).