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

DOI10.1007/978-3-642-18098-9_26zbMATH Open1297.68165OpenAlexW1686574681MaRDI QIDQ3073643FDOQ3073643

Authors Daniel Reidenbach, Markus L. Schmid

Publication date 11 February 2011

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.04097

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• scientific article; zbMATH DE number 1962812
• scientific article; zbMATH DE number 2080996
• Extended Regular Expressions: Succinctness and Decidability
• A fast bit-parallel algorithm for matching extended regular expressions
• Efficient testing and matching of deterministic regular expressions

Cites work

• scientific article; zbMATH DE number 1084695 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Finding a homomorphism between two words is NP-complete
• Finding patterns common to a set of strings
• On two-way multihead automata
• Pattern languages with and without erasing
• Reversal-Bounded Multicounter Machines and Their Decision Problems

Cited in

(9)

• Pattern matching with variables: a multivariate complexity analysis
• A note on the complexity of matching patterns with variables
• Patterns with bounded treewidth
• Finding shuffle words that represent optimal scheduling of shared memory access
• Extended regular expressions: succinctness and decidability
• Automata with modulo counters and nondeterministic counter bounds
• On the parameterised complexity of string morphism problems
• Efficient testing and matching of deterministic regular expressions
• Automata with modulo counters and nondeterministic counter bounds

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)