Patent US3177879A successfully refreshed from Google Patents.
Patent US5276776A successfully refreshed from Google Patents.
US5276776A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for building a computer-based Rete pattern matching network
Assignee: International Business Machines Corp
•
Filing: 1992-07-27
•
Granted: 1994-01-04
•
Expires: 2012-07-27
Abstract
Abstract A computer-based system and method for building a Rete based network. The computer-based system comprises a first module for inputting rules into the computer-based system, wherein each of the rules may have arbitrary specified tests therein. The computer-based system further comprises a second module responsive to the first module for generating a data structure indicative of each of the inputted rules. The computer-based system further comprises a third module, responsive to the second module, for storing each of the inputted rules and a fourth module responsive to said third means for constructing a Rete network for the rules. Further disclosed is system and method for allowing an expert system developer to enter rules that are formatted in conjunctive, disjunctive and or negated form.
Inventors
- 👤 Charles R. Grady
- 👤 Frederic D. Highland
- 👤 Christine T. Iwaskiw
- 👤 Michael Pfeifer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 15:42
CPC Classifications
G; G06; G06N; G06N5/00; G06N5/04; G06N5/046; G06N5/047
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
111 words
A computer-method for organizing a set of inputted rules into an efficient RETE network, each rule having at least one test condition, wherein the test condition or test conditions can be arbitrarily specified in conjunctive, negated, and/or disjunctive form, which computer-method comprises the steps of: (a) building a data structure for each rule and storing the data structure in a storage device; (b) transforming the data structure into at least one other modified data structure that is in conjunctive form; (c) building a flow list for the unique objects of the data structure; and (d) building at least one test node on the flow list for each of the unique objects.
Claim 2
Dependent Claim
111 words
A computer-method for organizing a set of inputted rules into an efficient RETE network, each rule having at least one test condition, wherein the test condition or test conditions can be arbitrarily specified in conjunctive, negated, and/or disjunctive form, which computer-method comprises the steps of: (a) building a data structure for each rule and storing the data structure in a storage device; (b) transforming the data structure into at least one other modified data structure that is in conjunctive form; (c) building a flow list for the unique objects of the data structure; and (d) building at least one test node on the flow list for each of the unique objects.
Claim 3
Dependent Claim
42 words
The computer-method of claim 1, wherein the step of building a data structure for each rule comprises the step of storing information about each test condition of the rule, wherein the stored information includes all the unique objects for a given test.
Claim 4
Dependent Claim
27 words
The computer-method of claim 2, wherein said step of storing information about each test condition comprises the step of generating a symbol list for each test condition.
Claim 5
Dependent Claim
42 words
The computer-method of claim 1, wherein said transformation step comprises the steps of: (a) examining the data structure for each rule and removing negation from the rule; and (b) examining the data structure for each rule and removing disjunctions from the rule.
Claim 6
Dependent Claim
19 words
The computer-method of claim 4, wherein said step of removing disjunctions comprises the step of building an additional rule.
Claim 7
Dependent Claim
27 words
The computer-method of claim 1, wherein said step of building a flow list comprises the steps of building a positive flow list and a negative flow list.
Claim 8
Dependent Claim
89 words
The computer-method of claim 6, wherein said step of building a flow list further comprises the steps of: (a) adding objects to the negative flow list which are involved in a purely negative multi-input test; (b) adding objects to the positive flow list which are involved in a purely positive multi-input test; (c) adding objects to the positive or negative flow list which are involved in a mixed quantification multi-input test; and (d) adding objects to the positive or negative flow list which are only specified in alpha tests.
Claim 9
Dependent Claim
85 words
The computer-method of claim 1, wherein the step of building at least one test node on the flow list for each of the unique objects comprises the steps of: (a) examining each test condition of the rule; (b) building beta nodes for purely negatively quantified test conditions first; and (c) building beta nodes or beta -- not nodes depending on whether test condition is purely positive or mixed quantification, and connecting purely negative beta nodes to the flow list with an and -- not node.
Claim 10
Dependent Claim
16 words
The computer-method of claim 1 further comprising the step of adding implicit conditions to the rules.
Claim 11
Dependent Claim
109 words
The computer-method of claim 9, wherein said step of adding implicit conditions comprises the steps of: (a) examining the right hand side of the rule to determine an unique list of objects; (b) examining the left hand side of the rule to determine which objects on the right hand side are not present on the left hand side of the rule; (c) determining whether the objects not present on the left hand side of the rule are created by the firing of the rule; and (d) adding the objects to the left hand side of the rule if the objects are not created by the firing of the rule.
References Cited (Backward Citations)
US4761746A
Cited
US4928236A
Cited
US4965882A
Cited
US4849905A
Cited
US4924408A
Cited
US4882691A
Cited
US4890240A
Cited
US5023807A
Cited
US5072405A
Cited
US4956791A
Cited
US4951225A
Cited
US5155803A
Cited
US5129037A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-03 | 1997-07-05 | 1998-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-03 | 2001-07-05 | 2002-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-03 | 2005-07-05 | 2006-01-04 | $7700.00 | Window Closed / Lapsed |