Agenda

Speaker:
Philip Bille, Inge Li Gørtz, DTU Copenhagen

Abstract:
An extended regular expression $R$ specifies a set of strings formed by characters from an alphabet combined with concatenation, union, intersection, complement, and star operators. Given an extended regular expression $R$ and a string $Q$, the extended regular expression matching problem is to decide if $Q$ matches any of the strings specified by $R$. Extended regular expressions are a basic concept in formal language theory and a basic primitive for searching and processing data. Extended regular expression matching was introduced by Hopcroft and Ullman in the 1970s [\textit{Introduction to Automata Theory, Languages and Computation}, Addison-Wesley, 1979], who gave a simple dynamic programming solution using $O(n^3m)$ time and $O(n^2m)$ space, where $n$ is the length of $Q$ and $m$ is the length of $R$. Since then, several solutions have been proposed, but few significant asymptotic improvements have been obtained. The current state-of-the-art solution, by Yamamoto and Miyazaki [COCOON, 2003], uses $O(\frac{n^3k + n^2m}{w} + n + m)$ time and $O(\frac{n^2k + nm}{w} + n + m)$ space, where $k$ is the number of intersection and complement operators in $R$ and $w$ is the number of bits in a machine word. This roughly replaces the $m$ factor with $k$ in the dominant terms of both the space and time bounds of the classical Hopcroft and Ullman algorithm. In this paper, we revisit the problem and present a new solution that significantly improves the previous time and space bounds. Our main result is a new algorithm that solves extended regular expression matching in \[ O\left(n^\omega k + \frac{n^2m}{\max(w/\log w, \log (n + m))} + m\right) \] time and $O(\frac{n^2 \log k}{w} + n + m) = O(n^2 +m)$ space, where $\omega \approx 2.3716$ is the exponent of matrix multiplication. Essentially, this replaces the dominant $n^3k$ term with $n^\omega k$ in the time bound, while simultaneously improving the $n^2k$ term in the space to $O(n^2)$. We also consider the interval operator (also known as the counting operator) and show how to easily and efficiently extend our algorithms to this case. Our results are based on a surprisingly simple combination of techniques and insights, including a compact representation to store and efficiently combine substring matches, a clustering technique for parse trees of extended regular expressions, and a new efficient combination of finite automaton simulation with our substring match representation to speed up the classic dynamic programming solution.