05360164

j

05360164 Watson, Bruce W. Kourie, Derrick G. Strauss, Tinus Ketcha, Ernest Cleophas, Loek Efficient automata constructions and approximate automata. Int. J. Found. Comput. Sci. 19, No. 1, 185-193 (2008). 2008 World Scientific, Singapore EN memory efficiency hash functions

doi:10.1142/S0129054108005619

Summary: 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.