NRF IR Repository

An assessment of selected algorithms for generating failure deterministic finite automata

Show simple item record

dc.contributor.advisor Kourie, Derrick G.
dc.contributor.advisor Cleophas, L.G.W.A. (Loek) Nxumalo, Madoda, A. 2017-09-01T08:46:59Z 2017-09-01T08:46:59Z 2016 2017-09 2016 2016-04-19
dc.description.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. en_US
dc.description.sponsorship National Research Foundation en_US
dc.format.extent 146 p. en_US
dc.format.medium pdf en_US
dc.language.iso en en_US
dc.publisher University of Pretoria en_US
dc.relation.requires Adobe Acrobat Reader en_US
dc.relation.uri en_US
dc.rights University of Pretoria en_US
dc.subject Failure deterministic finite automata en_US
dc.subject Random FDFA algorithm en_US
dc.subject Aho-Corasick en_US
dc.subject Failure transitions en_US
dc.title An assessment of selected algorithms for generating failure deterministic finite automata en_US
dc.type Thesis en_US
dc.rights.holder University of Pretoria en_US
dc.contributor.orcid 0000-0002-4091-9156 en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record