An assessment of algorithms for deriving failure deterministic finite automata

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

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)
    144 Downloads (Pure)

    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.

    Original languageEnglish
    Pages (from-to)43-68
    Number of pages26
    JournalSouth African Computer Journal
    Volume29
    Issue number1
    DOIs
    Publication statusPublished - 2017

    Keywords

    • Failure deterministic finite automata
    • Random automata

    Fingerprint

    Dive into the research topics of 'An assessment of algorithms for deriving failure deterministic finite automata'. Together they form a unique fingerprint.

    Cite this