I mention the same trick, without the theoretical underpinnings, in https://branchfree.org/2018/05/25/say-hello-to-my-little-friend-sheng-a-small-but-fast-deter

I mention the same trick, without the theoretical underpinnings, in https://branchfree.org/2018/05/25/say-hello-to-my-little-friend-sheng-a-small-but-fast-deterministic-finite-automaton/ https://branchfree.org/2018/05/25/say-hello-to-my-little-fri... in my notes, although the parallelism here serves no practical purpose on modern hardware at this time. I do this stuff with permutes and of course permutes are associative. The limitation is that you can do this only on DFAs that are the size of your biggest usable permute (currently 16, but will be 64 once AVX512VBMI comes out - looking dicey now with the logjam on 10nm Cannonlake :-( ). The idea also appears in Guy Blelloch's parallel prefix paper https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf. To my knowledge actual practical regex matching using this technique is thin on the ground. For a start, detecting not just the fact that something accepts but that it accepts at a particular state at a particular offset (not part of the formal regular expression definition, but very useful) is less straightforward in these parallel formulations.