Which regular expression patterns are hard to match?

DOI10.1109/FOCS.2016.56MaRDI QIDQ6946452zbMATH OpenFDO

Authors Artūrs Bačkurs, Piotr Indyk

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2016.56

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(19)

• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• A general information extraction framework based on formal languages
• Reconstructing general matching graphs
• Depth-3 circuit lower bounds for k-OV
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Tensor ranks and the fine-grained complexity of dynamic programming
• Elastic-degenerate string comparison
• Genome assembly, from practice to theory: safe, complete and \textit{linear-time}
• Co-lexicographically ordering automata and regular languages. I
• A purely regular approach to non-regular core spanners
• Fine-grained complexity of regular path queries
• Fine-grained hardness for edit distance to a fixed sequence
• Genome assembly, from practice to theory: safe, complete and linear-time
• Compressed dictionary matching on run-length encoded strings
• Text indexing for simple regular expressions
• Compressed dictionary matching on run-length encoded strings
• Linear time subsequence and supersequence regex matching
• Efficient matching of some fundamental regular expressions with backreferences
• Fast pattern matching with epsilon transitions

This page was built for publication: Which regular expression patterns are hard to match?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946452)