A Polynomial Time Match Test for Large Classes of Extended Regular Expressions

摘要

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