Efficient automata constructions and approximate automata

B.W. Watson, D.G. Kourie, E.K. Ngassam, T. Strauss, L.G.W.A. Cleophas

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    1 Downloads (Pure)


    In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at least L. Such automata can be used in a variety of practical applications, including network security pattern matching, in which false-matches are only a performance nuisance. The construction algorithm is particularly efficient, and is tunable to yield more or less exact automata.
    Original languageEnglish
    Pages (from-to)185-193
    JournalInternational Journal of Foundations of Computer Science
    Issue number1
    Publication statusPublished - 2008


    Dive into the research topics of 'Efficient automata constructions and approximate automata'. Together they form a unique fingerprint.

    Cite this