Method for parallel computation of a finite state machine

摘要

A method for operating a plurality of processor to determine a sequence of states traversed by a finite state machine in processing an input stream that includes a plurality of characters. The method divides the input stream into a plurality of contiguous sections characterized by a beginning character and an end character. Each section is assigned to a different processor. Each processor determines an end state that the finite state machine would traverse after the end character in the section assigned to that processor has been processed. That end state is provided to a processor that did not process the section associated with that end state. Each processor determines a sequence of states that the finite state machine would traverse if the finite state machine processed the section assigned to that processor using one of said received end states.