Automata and the algebra-coalgebra duality: on varieties and covarieties, on transition monoids and their dual
Jan Rutten, CWI and Radboud University Nijmegen

Abstract

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 [1] and as a coalgebra [2,3]. This algebra-coalgebra duality goes back to Arbib and Manes [4], who formulated it as a duality between reachability and observability, and is ultimately based on Kalman's [5] 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 [8] 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 [1] 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).

References

  1. S.Eilenberg. Automata, languages and machines (Volumes A and B). Pure and applied mathematics. Academic Press, 1974 and 1976.
  2. J.J.M.M. Rutten. Automata and coinduction (an exercise in coalgebra). Proceedings of CONCUR'98. Volume 1466 of LNCS, pages 194--218, 1998.
  3. J.J.M.M. Rutten. Universal coalgebra: a theory of systems. Theoretical Computer Science, 249(1):3--80, 2000.
  4. M.A. Arbib and E.G. Manes. Adjoint machines, state-behaviour machines, and duality. Journal of Pure and Applied Algebra, 6:313--344, 1975.
  5. R. Kalman.On the general theory of control systems. IRE Transactions on Automatic Control, 4(3):110--110, 1959.
  6. F. Bonchi, M. Bonsangue, J. Rutten, and A. Silva. Brzozowski's algorithm (co)algebraically. In Logic and Program Semantics, volume 7230 of LNCS, pages 12--23, 2012.
  7. F. Bonchi, M. Bonsangue, H. Hansen, P. Panangaden, J. Rutten, and A. Silva. Algebra-coalgebra duality in Brzozowski's minimization algorithm. Submitted.
  8. J.Rutten, A. Ballester-Bolinches, E. Cosme-Llopez. Varieties and covarieties of languages (extended abstract). Preliminary proceedings MFPS 2013.