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 paper: |  |
 |
 |
| PostScript | BibTeX reference |