A taxonomy of finite automata minimization algorithms
Bruce W. Watson · TU/e Research Portal · 1993
This paper presents a taxonomy of finite automata minimization algorithms.Brzozowski's elegant minimization algorithm differs from all other known minimization algorithms, and is derived separately.All of the remaining algorithms depend upon computing an equivalence relation on states.We define the equivalence relation, the partition that it induces, and its complement.Additionally, some useful properties are derived.It is shown that the equivalence relation is the greatest fixed point of an equation, providing a useful characterization of the required computation.We derive an upperbound on the number of approximation steps required to compute the fixed point.Algorithms computing the equivalence relation (or the partition, or its complement) are derived systematically in the same framework.The algorithms include Hopcroft's, several algorithms from text-books (including Hopcroft and Ullman's [HU79], Wood's [Wood87], and Aha, Sethi, and Ullman's [ASU86]), and several new algorithms or variants of existing algorithms.