3 ms·
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 th
by pjscott 8y ago
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.
- Dylan16807 8y agoSo 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.