
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.
[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Applications of universal algebra in computer science, automata, Data Science, Algebraic theory of languages and automata, Algebra, Algebra; Automata; Coalgebra; Duality; Theoretical Computer Science; Computer Science (all); Logic; Computational Mathematics, duality, Theory, coalgebra, Algorithms
[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Applications of universal algebra in computer science, automata, Data Science, Algebraic theory of languages and automata, Algebra, Algebra; Automata; Coalgebra; Duality; Theoretical Computer Science; Computer Science (all); Logic; Computational Mathematics, duality, Theory, coalgebra, Algorithms
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 27 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
