Efficient automata constructions and approximate automata

Bruce W. Watson, Derrick G. Kourie, Tinus Strauss, Ernest Ketcha Ngassam, Loek G. 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
Number of pages9
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