[Haskell-cafe] Regular Expression Simplification

[Johannes Waldmann]

> >  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.