The Prague Stringology Conference 2006

Bruce W. Watson, Derrick G. Kourie, Ernest Ketcha Ngassam, Tinus Strauss and Loek Cleophas

Efficient Automata Constructions and Approximate Automata

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.

Download article: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference