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…