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

Abstract:
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