Method of generating of DFA state machine that groups...

Details Method of generating of DFA state machine that groups... Method of generating of DFA state machine that groups...

2007-07-03

2007-07-03

Knight, Anthony (Department: 2121)

Data processing: artificial intelligence

Knowledge processing system

Knowledge representation and reasoning technique

C709S231000, C709S230000, C709S238000

Reexamination Certificate

active

10217592

ABSTRACT:
A method for generating look-up tables for a high speed multi-bit Real-time Deterministic Finite state Automaton (hereinafter RDFA). The method begins with a DFA generated in accordance with the prior art. For each state in the DFA, and for each of the bytes recognized in parallel the following occurs. First an n-closure list is generated. An n-closure list is a list of states reachable in n-transitions from the current state. Next an alphabet transition list is generated for each state. An “alphabet transition list” is a list of the transitions out of a particular state for each of the characters in an alphabet. Finally, the transitions are grouped into classes. That is, the transitions that go to the same state are grouped into the same class. Each class is used to identify the next state. The result is a state machine that has less states than the original DFA.

REFERENCES:
patent: 5151950 (1992-09-01), Hullender
patent: 5317509 (1994-05-01), Caldwell
patent: 6626960 (2003-09-01), Gillam
patent: 6742164 (2004-05-01), Gillam
patent: 6785677 (2004-08-01), Fritchman
patent: 2306364 (2000-10-01), None
patent: WO 88/01774 (1988-03-01), None
Hoshino et al., “Online Construction of Subsequence Automata for Multiple Texts”, IEEE Symposium on String Procerssing and Information Retrival, Sep. 2000.

Affiliated with

Also associated with

Rating

Method of generating of DFA state machine that groups... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of generating of DFA state machine that groups..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of generating of DFA state machine that groups... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3792178