Skip to main content



Algebra-Coalgebra Duality in Brzozowski’s Minimization Algorithm

F. Bonchi, M.M. Bonsangue, H.H. Hansen, P. Panangaden, J.J.M.M. Rutten, A. Silva

Discussion led by Steffen Smolka on February 5, 2016

We give a new presentation of Brzozowski’s algorithm to minimize finite automata, using elementary facts from universal algebra and coalgebra, and building on earlier work by Arbib and Manes on a categorical presentation of Kalman duality between reachability and observability. This leads to a simple proof of its correctness and opens the door to further generalizations. Notably, we derive algorithms to obtain minimal, language equivalent automata from Moore, non-deterministic and weighted automata.

PDF