Algebra- Coalgebra Duality in Brzozowski's Minimization Algorithm

Silva A, Bonchi F, Bonsangue M, Hansen HH, Panangaen P, Rutten J.  2014.  Algebra- Coalgebra Duality in Brzozowski's Minimization Algorithm. ACM Transactions on Computacional Logic. 15(1):1-29.


Duality plays a fundamental role in many areas of mathematics, computer science, systems
theory and even physics. For example, the familiar concept of Fourier transform is essentially a duality result: an instance of Pontryagin duality, see, for example the standard textbook [Rudin 1962]. Another basic instance, known to undergraduates, is the duality of a finite-dimensional vector spaces V over some field k, and the space of linear maps from V to k, which is itself a finite-dimensional vector space. Building on this self-duality, a fundamental principle in systems theory due to [Kalman 1959] captures the duality between the concepts of observability and controllability (to be explained below). The latter was further extended to automata theory (where controllability amounts to reachability) in [Arbib and Zeiger 1969], and in various papers [Arbib and Manes 1974; 1975a; 1975c; 1975b; 1980a; 1980b] where Arbib and Manes explored algebraic automata theory in a categorical framework; see also the excellent collection of papers [Kalman et al. 1969] where both automata theory and systems theory is presented.

Citation Key:




bonchi_algebra.pdf648.16 KB