  In the present paper, we study the match test for extended regular
expressions. We approach this NP-complete problem by introducing a novel
variant of two-way multihead automata, which reveals that the complexity of the
match test is determined by a hidden combinatorial property of extended regular
expressions, and it shows that a restriction of the corresponding parameter
leads to rich classes with a polynomial time match test. For presentational
reasons, we use the concept of pattern languages in order to specify extended
regular expressions. While this decision, formally, slightly narrows the scope
of our results, an extension of our concepts and results to more general
notions of extended regular expressions is straightforward.
