Paper Info
Title
Description and analysis of a bottom-up DFA minimization algorithm
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.
Year
DOI
Venue
2008
10.1016/j.ipl.2008.01.003
Inf. Process. Lett.
Keywords
Field
DocType
minimization,linear-time reduction,formal languages.,connected dfa,linear time,algorithms,. finite automaton,isomorphism problem,deterministic finite automaton,strongly connected component,bottom up,formal language,finite automaton,formal languages
Discrete mathematics,Combinatorics,Deterministic automaton,Deterministic finite automaton,Algorithm,Finite-state machine,Minification,Isomorphism,DFA minimization,Time complexity,Strongly connected component,Mathematics
Journal
Volume
Issue
ISSN
107
2
0020-0190
Citations 
PageRank 
References 
8
0.69
10
Authors
2
Name
Order
Citations
PageRank
J. Almeida16115.24
Marc Zeitoun228824.51