Brzozowski Derivatives stuck on a simple input

execute "(x y z + y z x + z x* y*)* + (x y)*" | string::Parse @RegExp - | ToAutomatonDerivation -

Noticed that in webui logs. It ran for over 3m on my debug build then I terminated it. Probably something to do with regexp optimizations. This should result in a ca. 11-state DFA.

added C-algorithm P-medium T-bug labels

changed the description

assigned to @travnja3

changed title from Brzozowski Derivatives stucks on a simple input to Brzozowski Derivatives stuck on a simple input

It might be that we are missing a needed simplification, I'll look at that today evening.

It seems even simpler input makes the algorithm loop indefinitely:

execute "(x y z + y z x + x* y*)*" | string::Parse @RegExp - | ToAutomatonDerivation -

I think this is the smallest variation of the original input with the same behaviour.

So the issue is that the regexp parsing "chose" FormalRegExp and optimizations of formal regexps are less capable than optimisations of unbounded regexps. I can force the regexp parsing to chose unbounded regexp and call it a day.

I'll try to figure out what happened in the regexp optimizations algorithm. I have a hunch, something that also affects the unbounded regexp optimization algorithm however not that extremely.

The optimization algorithm is not able to simplify (x + y* z*)* to (x + y + z)*.

Right now the best action is to disable the formal regexp string parser. With the change, only unbounded regexps are produced and it hides the issue. I have to figure out which optimization is missing in the RegExpOptimize of formal regexps...

I'll leave this open before I find it.

mentioned in issue #215 (closed)

V4 and V10 are not implemented completely for Formal RegExps if the pattern is deeper, they fail to optimize the RegExp.

mentioned in commit 257badef

mentioned in commit 228a24c4

closed via merge request !218 (merged)

closed via commit 228a24c4