AN EFFICIENT ALGORITHM FOR CONSTRUCTING MINIMAL COVER AUTOMATA FOR FINITE LANGUAGES
Cezar Câmpeanu, Andrei Păun, Sheng Yü · International Journal of Foundations of Computer Science · 2002
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(n4), 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(n2), which is a significant improvement from the previous algorithm.