JavaScript Regular Expression Matching is PSPACE-Complete
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 AugDisplayed time zone: Eastern Time (US & Canada) change
14:45 - 15:15 | |||
14:45 6mPoster | 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 6mPoster | Coverage Types Modulo Equivalences ICFP SRC | ||
14:57 6mPoster | JavaScript Regular Expression Matching is PSPACE-Complete ICFP SRC | ||
15:03 6mPoster | 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 6mPoster | Incremental Property-Based Testing ICFP SRC | ||