[Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)

Roman Cheplyaka roma at ro-che.info
Wed Sep 14 08:32:46 CEST 2011

* Eugene Kirpichov <ekirpichov at gmail.com> [2011-09-14 08:38:10+0400]
> Hi,
> I don't see how fallback to NFA simulation is really a failure wrt DoS
> attacks. It's not exponential in time or memory, just linear memory
> (in size of regex) instead of constant, and slower than DFA.

Hi Eugene, thanks for pointing that out.

Indeed, I now see that he uses breadth-first rather than depth-first
search. Then he has the same problem as I do. I shall study his code
more closely.

Roman I. Cheplyaka :: http://ro-che.info/

More information about the Haskell-Cafe mailing list