21 Mar
2014
21 Mar
'14
12:43 p.m.
I'm slightly worried that the overhead of converting to an NFA is far too great for complicated regular expressions
that's not where the complication is. it is in minimizing NFA (or regexeps) - both PSPACE-complete. This is known for a long time. Check any text on formal languages, or read the original sources, e.g., Meyer and Stockmeyer, 1972 http://people.csail.mit.edu/meyer/resume.shtml#publications for more recent results on (non)approximability, cf. Gramlich and Schnitger 1995 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.5056 - J.W.