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

From FSL

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
, LNCS 4423, pp 332-345, 2007**FOSSACS'07**

*Abstract.*By adding the complement operator (), extended regular expressions (ERE) can encode regular languages non-elementarily more succinctly than regular expressions. The ERE membership problem asks whether a word of size belongs to the language of an ERE of size . Unfortunately, the best known membership algorithms are either non-elementary in or otherwise require space and time ; since in many practical applications 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 and time . The presented algorithm outperforms the best known algorithms when is exponentially larger than .

- PDF, FOSSACS'07, BIB

## Technical report

**An Effective Algorithm for the Membership Problem for Extended Regular Expressions**- Grigore Rosu
UIUCDCS-R-2005-2694, August 2005**Technical Report**

*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.