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 class of modern regular expression matching was not well-understood. Previous work proved that regular expression matching with backreference…
cs.LO2025
Verified and Optimized Implementation of Orthologic Proof Search
Simon Guilloud, Clément Pit-Claudel
We report on the development of an optimized and verified decision procedure for orthologic equalities and inequalities. This decision procedure is quadratic-time and is used as a…