Re:Monoid machines: a O(log n) parser for regular languages ...
by pjscott on Thursday July 12, 2018 @09:14PM
(#17519859)
The part you do in parallel is computing the function "If the DFA is in state x, and it sees the whole input string, where will it end up?" You can represent that function as a table, one entry for each state. Once you've got that table, just look in the entry for the start state.
[ Parent
| on HN ]
Re:Monoid machines: a O(log n) parser for regular languages ...
by Dylan16807 on Friday July 13, 2018 @12:52AM
(#17520593)
So each thread might have to do up to m times the work, where m is the number of states? That sounds like it might be a pretty bad hit on the number of processors you need just to break even.