Loughborough University
Browse
Reidenbach_Schmid_CIAA_2010_Final_Version.pdf (192.04 kB)

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

Download (192.04 kB)
conference contribution
posted on 2011-02-07, 14:35 authored by Daniel Reidenbach, Markus L. Schmid
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.

History

School

  • Science

Department

  • Computer Science

Citation

REIDENBACH, D. and SCHMID, M.L., 2011. A polynomial time match test for large classes of extended regular expressions. IN: Domaratzki, M. and Salomaa, K. (eds.). Lecture Notes in Computer Science, 6482: Implementation and Application of Automata. 15th International Conference, CIAA 2010, Winnipeg, Canada, 12th-15th August, pp. 241-250.

Publisher

© Springer-Verlag

Version

  • AM (Accepted Manuscript)

Publication date

2011

Notes

This is a conference paper. Further details of the conference can be found at: http://www.cs.umanitoba.ca/~ciaa2010/

ISBN

9783642180972

Language

  • en

Usage metrics

    Loughborough Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC