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.
Theoretical Computer Science 679, 69–82 (2017)
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
representative citing papers
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
-
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.