Hardness of Regular Expression Matching with Extensions

Taisei Nogami, Yoshiki Nakamura, Tachio Terauchi

The regular expression matching problem asks whether a given regular expression of length $m$ matches a given string of length $n$. As is well known, the problem can be solved in $…