| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429181 | Information Processing Letters | 2008 | 8 Pages |
Abstract
We establish linear-time reductions between the minimization of a deterministic finite automaton (DFA) and the conjunction of 3 subproblems: the minimization of a strongly connected DFA, the isomorphism problem for a set of strongly connected minimized DFAs, and the minimization of a connected DFA consisting in two strongly connected components, both of which are minimized. We apply this procedure to minimize, in linear time, automata whose nontrivial strongly connected components are cycles.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
