An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

Madoda Nxumalo, Derrick G. Kourie, Loek Cleophas, Bruce W. Watson

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.

    Original languageEnglish
    Title of host publicationProceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France
    EditorsS. Ben Yahia, J. Konecny
    PublisherCEUR-WS.org
    Pages87-98
    Number of pages12
    ISBN (Print)9782954494807
    Publication statusPublished - 2015
    Event12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France - Campus des Cézeaux, Clermont-Ferrand, France
    Duration: 13 Oct 201516 Oct 2015
    http://cla2015.isima.fr/

    Publication series

    NameCEUR Workshop Proceedings
    Volume1466

    Conference

    Conference12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France
    Abbreviated titleCLA 2015
    CountryFrance
    CityClermont-Ferrand
    Period13/10/1516/10/15
    Internet address

    Keywords

    • Aho-Corasick algorithm
    • Failure deterministic finite automaton

    Fingerprint Dive into the research topics of 'An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata'. Together they form a unique fingerprint.

    Cite this