Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
An assessment of selected algorithms for generating failure deterministic finite automata
Dissertation (MSc)--University of Pretoria, 2016.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
University of Pretoria
2016
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613623221747712 |
|---|---|
| access_status_str | Open Access |
| author2 | Kourie, Derrick G. |
| author_browse | Kourie, Derrick G. |
| author_facet | Kourie, Derrick G. |
| collection | Thesis |
| dc_rights_str_mv | © 2016 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. |
| description | Dissertation (MSc)--University of Pretoria, 2016. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/57216 |
| institution | University of Pretoria (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:39:05.410Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2016 |
| publishDateRange | 2016 |
| publishDateSort | 2016 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/57216 An assessment of selected algorithms for generating failure deterministic finite automata Kourie, Derrick G. mddnxml@gmail.com Cleophas, L.G.W.A. (Loek) Nxumalo, Madoda UCTD Deterministic Finite Automata (DFA) Failure automata Algorithm assessment Failure transit Corasick Random FDFA algorithm Engineering, built environment and information technology theses SDG-09 Dissertation (MSc)--University of Pretoria, 2016. 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. tm2016 bs2026 Computer Science MSc Unrestricted SDG-09: Industry, innovation and infrastructure 2016-10-14T07:32:16Z 2016-10-14T07:32:16Z 2016-04-14 2016 Dissertation Nxumalo, M 2016, An assessment of selected algorithms for generating failure deterministic finite automata, MSc Dissertation, University of Pretoria, Pretoria, viewed yymmdd <http://hdl.handle.net/2263/57216> A2016 http://hdl.handle.net/2263/57216 en © 2016 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. application/pdf University of Pretoria |
| spellingShingle | UCTD Deterministic Finite Automata (DFA) Failure automata Algorithm assessment Failure transit Corasick Random FDFA algorithm Engineering, built environment and information technology theses SDG-09 An assessment of selected algorithms for generating failure deterministic finite automata |
| title | An assessment of selected algorithms for generating failure deterministic finite automata |
| title_full | An assessment of selected algorithms for generating failure deterministic finite automata |
| title_fullStr | An assessment of selected algorithms for generating failure deterministic finite automata |
| title_full_unstemmed | An assessment of selected algorithms for generating failure deterministic finite automata |
| title_short | An assessment of selected algorithms for generating failure deterministic finite automata |
| title_sort | assessment of selected algorithms for generating failure deterministic finite automata |
| topic | UCTD Deterministic Finite Automata (DFA) Failure automata Algorithm assessment Failure transit Corasick Random FDFA algorithm Engineering, built environment and information technology theses SDG-09 |
| url | http://hdl.handle.net/2263/57216 |