k-REWB matching cannot be solved in O(n to the 2k minus epsilon) time under SETH, is W[2]-hard parameterized by expression length, and 2-use 2-REWBs require superlinear time unless triangle detection does; 1-use REWBs admit an O(n log squared n) algorithm.
Title resolution pending
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
representative citing papers
A Rocq-mechanized semantics for JavaScript regex with backtracking, proven equivalent to an ECMAScript embedding, then used to verify contextual equivalence of rewrites and to prove correctness of the PikeVM algorithm.
Introduces MFN selective memoization based on minimum feedback vertex set for linear-time backtracking regex matching and relates it to prior schemes under Thompson and Glushkov automata constructions.
citing papers explorer
-
On the Complexity of the Matching Problem of Regular Expressions with Backreferences
k-REWB matching cannot be solved in O(n to the 2k minus epsilon) time under SETH, is W[2]-hard parameterized by expression length, and 2-use 2-REWBs require superlinear time unless triangle detection does; 1-use REWBs admit an O(n log squared n) algorithm.
-
Formal Verification for JavaScript Regular Expressions: a Proven Semantics and its Applications (Extended Version)
A Rocq-mechanized semantics for JavaScript regex with backtracking, proven equivalent to an ECMAScript embedding, then used to verify contextual equivalence of rewrites and to prove correctness of the PikeVM algorithm.
-
Selective Memoization for Efficient Backtracking Regular Expression Matching
Introduces MFN selective memoization based on minimum feedback vertex set for linear-time backtracking regex matching and relates it to prior schemes under Thompson and Glushkov automata constructions.