Algebra-coalgebra duality in brzozowski’s minimization algorithm

Reference. Algebra-coalgebra duality in brzozowski’s minimization algorithm

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 nondeterministic and weighted automata.

Cite

Cite as @bonchi-2014-algebra (helia, typst) · \cite{bonchi-2014-algebra} (LaTeX)

BibTeX

bibtex · 1 line

@article{bonchi-2014-algebra, title={Algebra-coalgebra duality in brzozowski’s minimization algorithm}, volume={15}, ISSN={1557-945X}, url={http://dx.doi.org/10.1145/2490818}, DOI={10.1145/2490818}, number={1}, journal={ACM Transactions on Computational Logic}, publisher={Association for Computing Machinery (ACM)}, author={Bonchi, Filippo and Bonsangue, Marcello M. and Hansen, Helle H. and Panangaden, Prakash and Rutten, Jan J. M. M. and Silva, Alexandra}, year={2014}, month=Feb, pages={1–29} }

hayagriva YAML (typst)

yaml · 22 lines

bonchi-2014-algebra:
  type: article
  title: Algebra-coalgebra duality in brzozowski’s minimization algorithm
  author:
  - Bonchi, Filippo
  - Bonsangue, Marcello M.
  - Hansen, Helle H.
  - Panangaden, Prakash
  - Rutten, Jan J. M. M.
  - Silva, Alexandra
  date: 2014-02
  page-range: 1-29
  url: http://dx.doi.org/10.1145/2490818
  serial-number:
    doi: 10.1145/2490818
    issn: 1557-945X
  parent:
    type: periodical
    title: ACM Transactions on Computational Logic
    publisher: Association for Computing Machinery (ACM)
    issue: 1
    volume: 15

Download: bonchi-2014-algebra.bib · bonchi-2014-algebra.yml

Cited by (1)

Weighted NetKAT: A Programming Language for Quantitative Network Verification suarezacevedo-2026-weightedPLDI · 2026

We introduce weighted NetKAT, a domain-specific language for modeling and verifying quantitative quantitative network properties. The language is parametric on a semiring , enabling the treatment of a wide range of quantities in a uniform way. We provide a denotational semantics and an equivalent operational semantics, the latter based on a novel model of weighted NetKAT automata ( WNKA ) capturing the stateful behavior of our language. With WNKA , we obtain a class of generic decision procedures for reasoning about quantitative safety and reachability in a fully automatic way, even in the presence of possibly unbounded iteration. We demonstrate the applicability of our framework in a case study using Internet2’s Abilene network as the underlying topology.

PDF · DOI · arXiv · pldb

Cites 37 works (2 here)

With notes (2)

Brzozowski’s Algorithm (Co)Algebraically bonchi-2012-brzozowskiLogic and Program Semantics · 2012

DOI

Kleene algebra with tests kozen1997kleeneTOPLAS · 1997

We introduce Kleene algebra with tests, an equational system for manipulating programs. We give a purely equational proof, using Kleene algebra with tests and commutativity conditions, of the following classical result: every while program can be simulated by a while program with at most one while loop. The proof illustrates the use of Kleene algebra with tests and commutativity conditions in program equivalence proofs.

PDF · DOI · pldb

External (35)

Sound and Complete Axiomatizations of Coalgebraic Language Equivalence (2013)
A Coalgebraic Perspective on Minimization and Determinization (2012)
Well-Pointed Coalgebras (Extended Abstract) (2012)
Minimization via Duality (2012)
Foundations of Software Science and Computational Structures - Proceedings of the 15th International Conference (FOSSACS'12) (2012)
A coalgebraic perspective on linear weighted automata (2011)
Nondeterministic Moore automata and Brzozowski's algorithm (2011)
THE CATEGORY OF SIMULATIONS FOR WEIGHTED TREE AUTOMATA (2011)
Canonical automata via duality (unpublished note) (2011)
Generalizing the powerset construction, coalgebraically (2010)
Elements of Automata Theory (2009)
Stone Duality and the Recognisable Languages over an Algebra (2009)
Abstract and Concrete Categories - The Joy of Cats (2009)
Automata, representations, and proofs (PhD thesis) (2009)
Duality and Equational Theory of Regular Languages (2008)
On the coalgebraic theory of Kleene algebra with tests (2008)
Experimental Evaluation of Classical Automata Constructions (2005)
Split and join for minimizing: Brzozowski's algorithm (2002)
On the duality between observability and reachability (2001)
Directly constructing minimal DFAs: Combining two algorithms by Brzozowski (2001)
Universal coalgebra: a theory of systems (2000)
Foundations of system theory: The hankel matrix (1980)
Machines in a category (1980)
Adjoint machines, state-behavior machines, and duality (1975)
Extensions of Semilattices (1975)
Fuzzy machines in a category (1975)
Machines in a Category: An Expository Introduction (1974)
Minimal realization of machines in closed categories (1972)
On the relevance of abstract algebra to control theory (1969)
Topics in Mathematical Systems Theory (1969)
Probabilistic automata (1963)
Canonical regular expressions and minimal state graphs for definite events (1962)
Fourier Analysis on Groups (1962)
On the definition of a family of automata (1961)
On the general theory of control systems (1960)