TU/e Research Portal · 1993 · 59 citations · 10 references
Open access
ComputingComputer ScienceAlgorithmsTheory Of ComputationAutomata TheoryFinite AutomataFinite State Machine ModelingFinite-state MachinesAutomata MinimizationDfa MinimizationFinite Automata Theory
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 Aho, Sethi, and Ullman's [ASU86]), and several new algorith...
10
Finite Automata and Their Decision Problems
M. O. Rabin, D. Scott · IBM Journal of Research and Development · 1959 · 1.9K citations
Derivatives of Regular Expressions
Janusz Brzozowski · Journal of the ACM · 1964 · 931 citations · Full text
Linear automaton transformations
Anil Nerode · Proceedings of the American Mathematical Society · 1958 · 478 citations