Copenhagen Programming Language Seminar

Faster Regular Expression Matching

Philip Bille, DTU

Tuesday 25 May 2010 at 15:00-16:00
DIKU, Universitetsparken, room N030

Regular expression matching is a key task (and often the computational
bottleneck) in a variety of widely used software tools and applications,
for instance, the \texttt{unix} \texttt{grep} and \texttt{sed} commands,
scripting languages such as \texttt{awk}
and \texttt{perl}, programs for analyzing massive data streams, etc.
We show how to solve this ubiquitous task in linear space and
$O(nm(\log \log n)/(\log n)^{3/2} + n + m)$ time where $m$ is the length of
the expression and $n$ the length of the string. This is
the first improvement for the dominant $O(nm/\log n)$ term
in Myers' $O(nm/\log n + (n + m)\log n)$ bound [JACM 1992].
We also get improved bounds for external memory.

Scientific host: Fritz Henglein Administrative host:Renée Korver Michan. All are welcome.
The Copenhagen Programming Language Seminar (COPLAS) is a collaboration between DIKU, ITU and RUC.
COPLAS is sponsored by the FIRST Graduate School.
To receive information about COPLAS talks by email, send a message to prog-lang-request@mail.it-c.dk with the word 'subscribe' as subject or in the body.

For more information about COPLAS, see http://www.coplas.org