[Haskell-cafe] Regular Expression Simplification

Johannes Waldmann waldmann at imn.htwk-leipzig.de
Fri Mar 21 16:43:09 UTC 2014

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

for more recent results on (non)approximability, 
cf. Gramlich and Schnitger 1995

- J.W.

More information about the Haskell-Cafe mailing list