On: Solving SAT via Positive Supercompilation

[kazinator]

Conversion of an NFA graph to DFA (in regex processing) seems to be a kind of supercompilation. The NFA is treated as a process, and is simulated for all possible input symbols at every step. The supercompiler makes note of what states it goes into and turns sets of them into DFA states.

[gbacon → kazinator]

Without backreferences, it has a worst-case exponential blow up due to the DFA possibly needing to simulate that many simultaneous NFA states.

Regex matching with backreferences is NP-hard.

- https://perl.plover.com/NPC/NPC-3SAT.html

- https://perl.plover.com/NPC/NPC-3COL.html