Patent ID: 8666925

Claim:
A method for operating a plurality of processors to determine a sequence of states traversed by a finite state machine in processing an input stream comprising a plurality of characters, said method comprising: dividing said input stream into a plurality of sections characterized by a beginning character and an end character; assigning each section to a different processor; defining a seed vector having one component for each state of said finite state machine; determining a set of vectors that can be generated by said finite state machine starting from said seed vector; causing each processor to determine an end state that said finite state machine would traverse after said end character in said section assigned to that processor has been processed for each possible initial state that could be present as input to said section, each processor implementing a transition function that maps each of said vectors to a corresponding one of said vectors in said set of vectors, said corresponding one of said vectors in said set of vectors being defined for each possible input character, wherein each of said vectors mapped by said transition function is a vector that could be reached from said seed vector; providing that end state to a processor that did not process said section associated with that end state; and causing each processor to determine a sequence of states that said finite state machine would traverse if said finite state machine processed said section assigned to that processor.