An Improved Algorithm for the Membership
Problem for Extended Regular Expressions
========================================

Extended regular expressions (EREs) define regular languages using
union, concatenation, repetition, intersection, and complementation
operators. The fact ERE allow intersection and complementation makes
them exponentially more succinct than regular expression.  The
membership problem for extended regular expressions is to decide,
given an expression $r$ and a word $w$, whether $w$ belongs to the
language defined by $r$. Since regular expressions are useful for
describing patterns in strings, the membership problem has numerous
applications. In many such applications, the words $w$ are very long
and patterns are conveniently described using EREs, making efficient
solutions to the membership problem of great practical interest.

In this paper we introduce alternating automata with synchronized
universality and negation, and use them in order to obtain a simple
and efficient algorithm for solving the membership problem for EREs. 
Our algorithm runs in time $O(m\cdot n^2)$ and space $O(m\cdot
n+k\cdot n^2)$, where $m$ is the length of $r$, $n$ is the length
of $w$, and $k$ is the number of intersection and complementation
operators in $r$. This improves the best known algorithms for the
problem.