A Polynomial Time Match Test for Large Classes of Extended Regular Expressions

DOI10.1007/978-3-642-18098-9_26zbMath1297.68165arXiv1707.04097OpenAlexW1686574681MaRDI QIDQ3073643

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

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

Related Items (8)

On the parameterised complexity of string morphism problems ⋮ Automata with Modulo Counters and Nondeterministic Counter Bounds ⋮ Extended regular expressions: succinctness and decidability ⋮ 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 ⋮ Unnamed Item ⋮ Pattern matching with variables: a multivariate complexity analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Finding a homomorphism between two words is NP-complete
• Finding patterns common to a set of strings
• On two-way multihead automata
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Pattern languages with and without erasing
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS

This page was built for publication: A Polynomial Time Match Test for Large Classes of Extended Regular Expressions