International Journal of Foundations of Computer Science · 2002 · 28 citations · 1 references
ComputingComputer ScienceMathematicsAlgorithmsRepresentation TheoryTheory Of ComputationAutomata TheoryComputational ComplexityFinite AutomataFinite-state MachinesTime ComplexityAutomata ConstructionAutomata SynthesisDeterministic Finite AutomataFinite Automata TheoryPolynomial Time ComplexityState Complexity
The concept of cover automata for finite languages was formally introduced in [3]. Cover automata have been studied as an efficient representation of finite languages. In [3], an algorithm was given to transform a DFA that accepts a finite language to a minimal deterministic finite cover automaton (DFCA) with the time complexity O(n 4 ), where n is the number of states of the given DFA. In this paper, we review the basic concept of cover automata and describe a new efficient transformation algorithm with the time complexity O(n 2 ), which is a significant improvement from the previous algorithm.
1