Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Computing All ℓ-Cover Automata Fast
verfasst von : Artur Jeż, Andreas Maletti
Erschienen in: Implementation and Application of Automata
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathcal{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
$\mathcal{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.