EFFICIENT AUTOMATA CONSTRUCTIONS AND APPROXIMATE AUTOMATA
Bruce W. Watson, Derrick G. Kourie, Tinus Strauss, ERNEST KETCHA, Loek Cleophas · International Journal of Foundations of Computer Science · 2008
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 leastL. 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.