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

* Eugene Kirpichov [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/