Hardness of Regular Expression Matching with Extensions

Taisei Nogami, Yoshiki Nakamura, Tachio Terauchi

Regular expression matching asks whether a given regular expression of length $m$ matches a given string of length $n$, and its time complexity is fairly well understood. Meanwhile…