A polynomial time match test for large classes of extended regular expressions

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...

Full description

Bibliographic Details

Main Authors:	Daniel Reidenbach, Markus L. Schmid
Format:	Default Conference proceeding
Published:	2011
Subjects:	Other information and computing sciences not elsewhere classified untagged Information and Computing Sciences not elsewhere classified
Online Access:	https://hdl.handle.net/2134/7957
Tags:	Add Tag No Tags, Be the first to tag this record!