# An Effective Algorithm for the Membership Problem for Extended Regular Expressions

This work has been published in a conference proceedings and in a technical report.

## FOSSACS'07

An Effective Algorithm for the Membership Problem for Extended Regular Expressions
Grigore Rosu
FOSSACS'07, LNCS 4423, pp 332-345, 2007
Abstract. By adding the complement operator ($\neg$), extended regular expressions (ERE) can encode regular languages non-elementarily more succinctly than regular expressions. The ERE membership problem asks whether a word $w$ of size $n$ belongs to the language of an ERE $R$ of size $m$. Unfortunately, the best known membership algorithms are either non-elementary in $m$ or otherwise require space $\Omega(n^2)$ and time $\Omega(n^3)$; since in many practical applications $n$ can be very large, these space and time requirements could be prohibitive. In this paper we present an ERE membership algorithm that runs in space $O(n \cdot (\log n + m) \cdot 2^{m})$ and time $O(n^2 \cdot (\log n + m) \cdot 2^m)$. The presented algorithm outperforms the best known algorithms when $n$ is exponentially larger than $m$.
PDF, FOSSACS'07, BIB

## Technical report

An Effective Algorithm for the Membership Problem for Extended Regular Expressions
Grigore Rosu
Technical Report UIUCDCS-R-2005-2694, August 2005
Abstract. By adding the complement operator ($\neg$), extended regular expressions ({\ERE}) can encode regular languages non-elementarily more succinctly than regular expressions. The {\ERE} membership problem asks whether a word $w$ of size $n$ belongs to the language of an {\ERE} $R$ of size $m$. Unfortunately, the best known membership algorithms are either non-elementary in $m$ or otherwise require space $\Omega(n^2)$ and time $\Omega(n^3)$; since in many practical applications $n$ can be very large (in the order of billions, e.g., in testing where $w$ represents the execution trace of some system), these space and time requirements could be prohibitive. In this paper we present a simple to implement {\ERE} membership algorithm that runs in space $O(n \cdot (m + \log n) \cdot 2^{m} \cdot k)$ and in time $O(n^2 \cdot (m + \log n)^2 \cdot 2^m \cdot k)$, where $k$ is the number of complement operators in $R$. The presented algorithm outperforms the best known algorithms when $n$ is large.
PDF, Technical Report @ UIUC, BIB