[Haskell-cafe] Regular Expression Simplification
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
More information about the Haskell-Cafe