Brzozowski’s Algorithm (Co)Algebraically

Reference. Brzozowski’s Algorithm (Co)Algebraically

Cite

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

BibTeX

bibtex · 1 line

@inbook{bonchi-2012-brzozowski, title={Brzozowski’s Algorithm (Co)Algebraically}, ISBN={9783642294853}, ISSN={1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-29485-3_2}, DOI={10.1007/978-3-642-29485-3_2}, booktitle={Logic and Program Semantics}, publisher={Springer Berlin Heidelberg}, author={Bonchi, Filippo and Bonsangue, Marcello M. and Rutten, Jan J. M. M. and Silva, Alexandra}, year={2012}, pages={12–23} }

hayagriva YAML (typst)

yaml · 19 lines

bonchi-2012-brzozowski:
  type: chapter
  title: Brzozowski’s Algorithm (Co)Algebraically
  author:
  - Bonchi, Filippo
  - Bonsangue, Marcello M.
  - Rutten, Jan J. M. M.
  - Silva, Alexandra
  date: 2012
  page-range: 12-23
  url: http://dx.doi.org/10.1007/978-3-642-29485-3_2
  serial-number:
    doi: 10.1007/978-3-642-29485-3_2
    isbn: '9783642294853'
    issn: 1611-3349
  parent:
    type: book
    title: Logic and Program Semantics
    publisher: Springer Berlin Heidelberg

Download: bonchi-2012-brzozowski.bib · bonchi-2012-brzozowski.yml

Cited by (1)

Algebra-coalgebra duality in brzozowski’s minimization algorithm bonchi-2014-algebraTOCL · 2014

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.

DOI

Cites 17 works (1 here)

With notes (1)

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 (16)

Well-pointed Coalgebras (unpublished note) (2012)
Minimization via duality (unpublished note) (2012)
Nondeterministic Moore Automata and Brzozowski's Algorithm (2011)
Generalizing the powerset construction, coalgebraically (2010)
Elements of Automata Theory (2009)
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)
Automata and Computability (1997)
Taxonomies and Toolkits of Regular Language Algorithms (PhD thesis) (1995)
Machines in a category (1980)
Adjoint machines, state-behavior machines, and duality (1975)
Probabilistic automata (1963)
Canonical regular expressions and minimal state graphs for definite events (1962)
On the definition of a family of automata (1961)
The duality of state and observations (unpublished note)