On Regular Expression Matching and Deterministic Finite Automata
Philip Bille · Tiny Trans. Comput. Sci. · 2015
Given a regular expression R and a string T the regular expression matching problem is to determine if T matches any string in the language generated by R. The best known solution to the problem uses linear space and O nm log logn