An assessment of algorithms for deriving failure deterministic finite automata

M. Nxumalo, D.G. Kourie, L.G.W.A. Cleophas, B.W. Watson

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    1 Citaat (Scopus)
    76 Downloads (Pure)


    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.

    Originele taal-2Engels
    Pagina's (van-tot)43-68
    Aantal pagina's26
    TijdschriftSouth African Computer Journal
    Nummer van het tijdschrift1
    StatusGepubliceerd - 2017

    Vingerafdruk Duik in de onderzoeksthema's van 'An assessment of algorithms for deriving failure deterministic finite automata'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit