In this work we use a framework of finite-state automata constructions based on equivalences over words to provide new insights on the relation between well-known methods for computing the minimal deterministic automaton of a language.
@cite_9: a b s t r a c t We here propose a polynomial-time deterministic finite automaton minimization algorithm directly derived from Brzozowski’s double reversal algorithm. To do so, we take into account the framework by Brzozowski and Tamm, to propose an atomization algorithm that allows us to achieve polynomial time complexity.
@cite_10: Coalgebra offers a unified theory of state based systems, including infinite streams, labelled transition systems and deterministic automata. In this paper, we use the coalgebraic view on systems to derive, in a uniform way, abstract procedures for checking behavioural equivalence in coalgebras, which perform (a combination of) minimization and determinization. First, we show that for coalgebras in categories equipped with factorization structures, there exists an abstract procedure for equivalence checking. Then, we consider coalgebras in categories without suitable factorization structures: under certain conditions, it is possible to apply the above procedure after transforming coalgebras with reflections. This transformation can be thought of as some kind of determinization. We will apply our theory to the following examples: conditional transition systems and (non-deterministic) automata.
@cite_3: 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_8: 
Some of these connections have already been studied in order to offer a better understanding of Brzozowski's double-reversal method @cite_10 @cite_3 @cite_8 @cite_9 . In particular, @cite_10 and @cite_3 offer an alternative view of minimization and determinization methods in a uniform way from a category-theoretical perspective. In contrast, our work revisits these well-known minimization techniques relying on simple language-theoretical notions.