A Dichotomy for Regular Expression Membership Testing

Karl Bringmann, Allan Grønlund, Kasper Green Larsen

We study regular expression membership testing: Given a regular expression of size $m$ and a string of size $n$, decide whether the string is in the language described by the regul…