An assessment of algorithms for deriving failure deterministic finite automata
| dc.contributor.author | Nxumalo, Madoda | en_ZA |
| dc.contributor.author | Kourie, Derrick G. | en_ZA |
| dc.contributor.author | Cleophas, Loek | en_ZA |
| dc.contributor.author | Watson, Bruce W. | en_ZA |
| dc.date.accessioned | 2018-11-30T13:56:27Z | |
| dc.date.available | 2018-11-30T13:56:27Z | |
| dc.date.issued | 2017 | |
| dc.description | CITATION: 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.description | The original publication is available at http://sacj.cs.uct.ac.za | en_ZA |
| dc.description.abstract | Failure 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.uri | http://sacj.cs.uct.ac.za/index.php/sacj/article/view/456 | |
| dc.description.version | Publisher's version | en_ZA |
| dc.format.extent | 26 pages : illustrations (some colour) | en_ZA |
| dc.identifier.citation | 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.identifier.issn | 2313-7835 (online) | |
| dc.identifier.other | doi:10.18489/sacj.v29i1.456 | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/104762 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | South African Institute of Computer Scientists and Information Technologists | en_ZA |
| dc.rights.holder | Authors retain copyright | en_ZA |
| dc.subject | Finite automata | en_ZA |
| dc.subject | Sequential machine theory | en_ZA |
| dc.subject | Algorithms | en_ZA |
| dc.title | An assessment of algorithms for deriving failure deterministic finite automata | en_ZA |
| dc.type | Article | en_ZA |