Search

A deterministic finite automaton (DFA) [formula] is called a cover automaton (DFCA) for a finite language L over some alphabet Σ if [formula], with l being the length of some longest word in L. Thus a word w ∈ Σ* is in L if and only if |w| ≤ l and [formula]. The DFCA [formula] is minimal if no DFCA for L has fewer states. In this paper, we present an algorithm which converts an n–state DFA for some finite language L into a corresponding minimal DFCA, using only O(n log n) time and O(n) space. The best previously known algorithm requires O(n[sup 2]) time and space. Furthermore, the new algorithm can also be used to minimize any DFCA, where the best previous method takes O(n[sup 4]) time and space. Since the required data structure is rather complex, an implementation in the common programming language C/C++ is also provided. [ABSTRACT FROM AUTHOR]