2 papers
cs.PL2026
On the computational complexity of JavaScript regex matching
Victor Deng, Aurèle Barrière, Clément Pit-Claudel
Despite widespread use, the complexity of the matching problem for modern regular expressions languages remains unclear. Previous work proved that an idealized regular expression l…
cs.PL2025
Formal Verification for JavaScript Regular Expressions: a Proven Semantics and its Applications (Extended Version)
Aurèle Barrière, Victor Deng, Clément Pit-Claudel
We present the first mechanized, succinct, practical, complete, and proven-faithful semantics for a modern regular expression language with backtracking semantics. We ensure its fa…