Finite State Methods for String Matching
Tapahtuman tyyppi:
Vierailuluento
Aika:
15.09.2011 - 14:15 - 15:00
Luennoija:
Emanuele Giaquinta
Paikka:
Exactum B120
Kuvaus:
Abstract:
I review some recent contributions to methods based on finite automata for the String Matching problem and for some of its variants. In particular, I shall present a novel technique, suitable for bit-parallelism, to represent both the nondeterministic automaton and the nondeterministic suffix automaton of a given string in a more compact way. This new approach is based on a particular factorization of strings which, on the average, allows to reduce the size of the bit-vectors needed to encode the automaton. If one restricts to a single machine word of w bits, this method makes it possible to encode automata of strings longer than w.
This talk is part of a series of meetings for string algorithms researchers in the Helsinki area.