Wed 26 Aug 2026 14:57 - 15:03 at IP126 Auditorium - SRC Presentations

Modern regular expressions (called regexes) depart significantly from traditional regular expressions, due to the addition of new features such as capture groups, lookarounds and backreferences. Different regex languages have different features with potentially different matching complexities, and complexity results for real-world regex languages are scarce. Our work focuses on JavaScript regexes, and provides an answer to the question of their matching complexity. We prove that JavaScript regex matching with expanded counted repetitions is PSPACE-complete, even without negative lookarounds. We are also in the process of proving that JavaScript regex matching without lookarounds (but still with expanded counted repetitions) is OptP-complete. Our results rely on core proofs mechanized in the Rocq proof assistant.

Wed 26 Aug

Displayed time zone: Eastern Time (US & Canada) change

14:45 - 15:15
SRC PresentationsICFP SRC at IP126 Auditorium
14:45
6m
Poster
Better Safe and Sorry: Tabular Types for Dynamic Languages
ICFP SRC
Vincent H. Chan University at Buffalo, SUNY, Matías Toro University of Chile, Qianchuan Ye University at Buffalo, SUNY
14:51
6m
Poster
Coverage Types Modulo Equivalences
ICFP SRC
Aaryan Prakash Purdue University, Benjamin Delaware Purdue University
14:57
6m
Poster
JavaScript Regular Expression Matching is PSPACE-Complete
ICFP SRC
15:03
6m
Poster
QuickerChick
ICFP SRC
Ivan Mladenov University of Maryland, College Park, Alperen Keles University of Maryland at College Park, Leonidas Lampropoulos University of Maryland at College Park
15:09
6m
Poster
Incremental Property-Based Testing
ICFP SRC
Pablo Benario Figueroa University of Chile, Éric Tanter University of Chile