Abstract:
A Failure Deterministic Finite Automaton (FDFA) o ers a deterministic
and a compact representation of an automaton that is used by various algorithms
to solve pattern matching problems e ciently. An abstract, concept
lattice based algorithm called the DFA - Homomorphic Algorithm (DHA) was
proposed to convert a deterministic nite automata (DFA) into an FDFA.
The abstract DHA has several nondeterministic choices. The DHA is tuned
into four decisive and specialized variants that may potentially remove the
optimal possible number of symbol transitions from the DFA while adding
failure transitions. The resulting specialized FDFA are: MaxIntent FDFA,
MinExtent FDFA, MaxIntent-MaxExtent FDFA and MaxArcReduncdancy
FDFA. Furthermore, two output based investigations are conducted whereby
two speci c types of DFA-to-FDFA algorithms are compared with DHA variants.
Firstly, the well-known Aho-Corasick algorithm, and its DFA is converted
into DHA FDFA variants. Empirical and comparative results show
that when heuristics for DHA variants are suitably chosen, the minimality
attained by the Aho-Corasick algorithm in its output FDFAs can be closely
approximated by DHA FDFAs. Secondly, testing DHA FDFAs in the general
case whereby random DFAs and language equivalent FDFAs are carefully
constructed. The random DFAs are converted into DHA FDFA types and
the random FDFAs are compared with DHA FDFAs. A published non concept
lattice based algorithm producing an FDFA called D2FA is also shown
to perform well in all experiments. In the general context DHA performed
well though not as good as the D2FA algorithm. As a by-product of general
case FDFA tests, an algorithm for generating random FDFAs and a language
equivalent DFAs was proposed.
