Reidenbach_Schmid_CIAA_2010_Final_Version.pdf (192.04 kB)
Download fileA polynomial time match test for large classes of extended regular expressions
conference contribution
posted on 2011-02-07, 14:35 authored by Daniel Reidenbach, Markus L. SchmidIn 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.
History
School
- Science
Department
- Computer Science