Patent Document ID: 4450520
Application ID: 06242789

Base Claim:
1. A method, for detecting matches between strings of input characters and one or more patterns, each pattern comprising elements consisting of tokens, employing a finite state automaton, responsive to said strings of input characters, comprising a plurality of character matchers acting in concert; each character matcher being characterized as capable of existing in one of a plurality of states, each such state having (a) one token from a pattern, to be compared against a current input character, (b) first instructions, which govern transitions to the next state of said character matcher, and (c) second instructions, which force other character matchers into specified states; each character matcher being further characterized as having at least an initial state, to be occupied by said character matcher at the start of the matching procedure, and an idle state, to be occupied by said character matcher after an unsuccessful comparison between the token specified in the current state of said character matcher and the current input character; the respective states being partitioned among said character matchers to avoid any sequence of input characters requiring any character matcher to be simultaneously in more than one state; said method, for each string of input characters to be matched and for each character matcher, comprising: (a) comparing, with the character matcher in its initial state, a first input character against the token specified in the initial state of the character matcher, whereby said comparison is either successful or unsuccessful; (b) transitioning, in consequence of an unsuccessful comparison, to the idle state of the character matcher; (c) transitioning, in consequence of a successful comparison, to a succeeding state, in accordance with instructions contained in the current state of the character matcher; (d) forcing other character matchers into new states specified in the instructions of the current state of the character matcher of step (c); (e) comparing a succeeding input character against the token specified in the succeeding state and transitioning to a further succeeding state in accordance with steps (b), (c), and (d); and (f) repeating step (e) until all input characters have been compared.

---

Claim 3:
3. The method of claim 1 wherein the plurality of character matchers are disposed in a ring configuration wherein each character matcher is capable of forcing only the two neighboring character matchers into a specified state.