|Abstract of Paper|
An Automata-based Recognition Algorithm for Semi-extended Regular Expressions
by Hiroaki Yamamoto
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.