Computing All ?-Caver Automata Fast

摘要

Given a language L and a number ?, an ?-cover automaton for L is a DFA M such that its language coincides with L on all words of length at most ?. It is known that an equivalent minimal ?-cover automaton can be constructed in time O(n log n), where n is the number of states of M. This is achieved by a clever and sophisticated variant of Hopcroft's algorithm, which computes the ?-similarity inside the main algorithm. This contribution presents an alternative simple algorithm with running time O(n log n), in which the computation is split into three phases. First, a compact representation of the gap table is created. Second, this representation is enriched with information about the length of a shortest word leading to the states. These two steps are independent of the parameter ?. Third, the ?-similarity is extracted by simple comparisons against ?. In particular, this approach allows the calculation of all the sizes of minimal ?-cover automata (for all valid ?) in the same time bound.