2 ms·
The problem is that the "constant" memory usage of a DFA may well be exponential in the size of the corresponding NFA/pattern.
by xyzzyz 11y ago
The problem is that the "constant" memory usage of a DFA may well be exponential in the size of the corresponding NFA/pattern.
- amalcon 11y agoSure. You want to do this when an attacker controls the input, and a benevolent but fallible actor controls the expression. It's not useful when the attacker controls the expression.
- nanolith 11y agoIt could be larger, but it would be a known constraint with known runtime characteristics. There is value in this, especially with regards to understanding the worst-case performance.