Description and analysis of a bottom-up DFA minimization algorithm

• Type: Article in International Scientific Journal
• Date: 2008

Authors

Jorge Almeida (Author) FCUP; Marc Zeitoun (Author) Other

Journal

Title: Information Processing Letters

Vol. 107

Pages: 52-59

ISSN: 0020-0190

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 11 Citations

Scopus - 14 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-003-XR3

DOI: 10.1016/j.ipl.2008.01.003

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific