A polynomial time match test for large classes of extended regular expressions
From MaRDI portal
Publication:3073643
DOI10.1007/978-3-642-18098-9_26zbMATH Open1297.68165arXiv1707.04097OpenAlexW1686574681MaRDI QIDQ3073643FDOQ3073643
Daniel Reidenbach, Markus L. Schmid
Publication date: 11 February 2011
Published in: Implementation and Application of Automata (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1707.04097
Cites Work
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Finding patterns common to a set of strings
- Pattern languages with and without erasing
- Finding a homomorphism between two words is NP-complete
- A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
- Title not available (Why is that?)
- On two-way multihead automata
- Title not available (Why is that?)
Cited In (9)
- Pattern matching with variables: a multivariate complexity analysis
- Title not available (Why is that?)
- Automata with Modulo Counters and Nondeterministic Counter Bounds
- Efficient testing and matching of deterministic regular expressions
- Patterns with bounded treewidth
- On the parameterised complexity of string morphism problems
- A note on the complexity of matching patterns with variables
- Extended regular expressions: succinctness and decidability
- Finding shuffle words that represent optimal scheduling of shared memory access
Recommendations
This page was built for publication: A polynomial time match test for large classes of extended regular expressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073643)
