Finite State Methods for String Matching

Event type: 
Guest lecture
Event time: 
15.09.2011 - 14:15 - 15:00
Lecturer : 
Emanuele Giaquinta
Place: 
Exactum B120
Description: 

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.

09.09.2011 - 13:17 Leena Salmela
09.09.2011 - 13:17 Leena Salmela