An assessment of algorithms for deriving failure deterministic finite automata

Simple item page
dc.contributor.authorNxumalo, Madodaen_ZA
dc.contributor.authorKourie, Derrick G.en_ZA
dc.contributor.authorCleophas, Loeken_ZA
dc.contributor.authorWatson, Bruce W.en_ZA
dc.date.accessioned2018-11-30T13:56:27Z
dc.date.available2018-11-30T13:56:27Z
dc.date.issued2017
dc.descriptionCITATION: Nxumalo, M., et al. 2017. An assessment of algorithms for deriving failure deterministic finite automata. South African Computer Journal, 29(1):43-68, doi:10.18489/sacj.v29i1.456.en_ZA
dc.descriptionThe original publication is available at http://sacj.cs.uct.ac.zaen_ZA
dc.description.abstractFailure deterministic finite automata (FDFAs) represent regular languages more compactly than deterministic finite automata (DFAs). Four algorithms that convert arbitrary DFAs to language-equivalent FDFAs are empirically investigated. Three are concrete variants of a previously published abstract algorithm, the DFA-Homomorphic Algorithm (DHA). The fourth builds a maximal spanning tree from the DFA to derive what it calls a delayed input DFA. A first suite of test data consists of DFAs that recognise randomised sets of finite length keywords. Since the classical Aho-Corasick algorithm builds an optimal FDFA from such a set (and only from such a set), it provides benchmark FDFAs against which the performance of the general algorithms can be compared. A second suite of test data consists of random DFAs generated by a specially designed algorithm that also builds language-equivalent FDFAs, some of which may have non-divergent cycles. These random FDFAs provide (not necessarily tight) lower bounds for assessing the effectiveness of the four general FDFA generating algorithms.en_ZA
dc.description.urihttp://sacj.cs.uct.ac.za/index.php/sacj/article/view/456
dc.description.versionPublisher's versionen_ZA
dc.format.extent26 pages : illustrations (some colour)en_ZA
dc.identifier.citationNxumalo, M., et al. 2017. An assessment of algorithms for deriving failure deterministic finite automata. South African Computer Journal, 29(1):43-68, doi:10.18489/sacj.v29i1.456en_ZA
dc.identifier.issn2313-7835 (online)
dc.identifier.otherdoi:10.18489/sacj.v29i1.456
dc.identifier.urihttp://hdl.handle.net/10019.1/104762
dc.language.isoen_ZAen_ZA
dc.publisherSouth African Institute of Computer Scientists and Information Technologistsen_ZA
dc.rights.holderAuthors retain copyrighten_ZA
dc.subjectFinite automataen_ZA
dc.subjectSequential machine theoryen_ZA
dc.subjectAlgorithmsen_ZA
dc.titleAn assessment of algorithms for deriving failure deterministic finite automataen_ZA
dc.typeArticleen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
nxumalo_assessment_2017.pdf
Size:
263.13 KB
Format:
Adobe Portable Document Format
Description:
Download article
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Research Articles (Computer Science)