Abstract of Paper

An Automata-based Recognition Algorithm for Semi-extended Regular Expressions
by Hiroaki Yamamoto

Abstract:

This paper is concerned with the recognition problem for semi-extended
regular expressions: given a semi-extended regular expression
$r$ of length $m$ and an input string $x$ of length $n$, determine if $x\in
L(r)$, where $L(r)$ denotes the language denoted by $r$. Although the
recognition algorithm based on nondeterministic finite automata (NFAs) for
regular expressions is widely known, a similar algorithm based on finite
automata is currently not known for semi-extended regular expressions. The  
existing algorithm is based on dynamic programming. We here present an 
efficient automata-based recognition algorithm by introducing a new model of
alternating finite automata called partially input-synchronized alternating
finite automata (PISAFAs for short). Our algorithm based on PISAFAs runs in
$O(mn^2)$ time and $O(mn+kn^2)$ space, though the existing algorithm based
on dynamic programming runs in $O(mn^3)$ time and $O(mn^2)$ space, where $k$
is the number of intersection operators occurring in $r$. Thus our algorithm
significantly improves the existing one. In addition, if $r$ is a regular
expression, then our algorithm exactly agrees with the standard recognition
algorithm based on NFAs, which runs in $O(mn)$ time and $O(m)$ space.