Failure deterministic finite automata

D.G. Kourie, B.W. Watson, L.G.W.A. Cleophas, F. Venter

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

    10 Citations (Scopus)
    283 Downloads (Pure)

    Abstract

    Inspired by failure functions found in classical pattern matching algorithms, a failure deterministic finite automaton (FDFA) is defined as a formalism to recognise a regular language. An algorithm, based on formal concept analysis, is proposed for deriving from a given deterministic finite automaton (DFA) a language-equivalent FDFA. The FDFA’s transition diagram has fewer arcs than that of the DFA. A small modification to the classical DFA’s algorithm for recognising language elements yields a corresponding algorithm for an FDFA.
    Original languageEnglish
    Title of host publicationProceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012)
    EditorsJ. Holub, J. Zdarek
    Place of PublicationPrague
    PublisherCzech Technical University in Prague
    Pages28-41
    ISBN (Print)978-80-01-05095-8
    Publication statusPublished - 2012

    Fingerprint Dive into the research topics of 'Failure deterministic finite automata'. Together they form a unique fingerprint.

    Cite this