Rule processing system for determining a result response

• US 7,809,669 B2
• Filed: 07/09/2008
• Issued: 10/05/2010
• Est. Priority Date: 03/21/2001
• Status: Expired due to Fees

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: Verde Sabor Assets LLC (Intellectual Ventures LLC)
• Inventors: Mair, Douglas M., Huelsman, David L., Love, Sharon E.
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): OLUDE AFOLABI, OLATOYOSI
• Application Number:
  US12/170,369
• Publication Number:
  US 20080270337A1
• Time in Patent Office: 818 Days
• Field of Search: 706/12, 706/14, 706/47, 707/101
• US Class Current: 706/47
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A rule processing apparatus includes modules for defining/entering attributes, enumerations, and/or relationships; packaging the definitions in a reduced canonical form suitable for propositional logic manipulation using zero-suppressed binary decision diagrams (Zdd) to produce a prime Zdd; and/or (iii) executing the rule by applying a series of user inputs to the prime Zdd to determine a result that preferably includes conflict and selection advice to guide the user to satisfaction. Elective events, such as but not limited to the display of messages or the performance of calculations, may optionally be packaged along with the prime rule or components thereof, and presented during execution to help guide the end user to satisfaction or compliancy when choosing among possible selections. The apparatus automates determination of a complex rule having a combinatorial exploded number of rule components, or a combinatorial number of possible outcomes, exceeding computational capacity of present day computing systems.

Claims

1. A system comprising:

means for storing a digital representation of a zero-suppressed binary decision diagram (ZDD) formed by manipulatively combining;

an Include ZDD rule component that indicates inclusive constraints of a rule model;

an Exclude ZDD rule component that indicates exclusive constraints of the rule model; and

an Attribute Relations ZDD constructed from the Include and Exclude rule components to indicate interrelations between the Include and Exclude ZDD rule components; and

means for determining a result responsive to an application of inputs to the ZDD, the inputs characterizing desired constraints of the rule model.

2. The system of claim 1

where the inclusive constraints comprise included or true relations between an attribute and an enumeration value of the rule model;

and

where the exclusive constraints comprise excluded or false relations between an attribute and an enumeration value of the rule model.

3. The system of claim 2 where the ZDD is formed by manipulatively combining an Elective Events ZDD component with the rule model to invoke a data processing event responsive to a predetermined combination of constraints of the rule model.

4. The system of claim 3 where the data processing event includes communicating a message.

5. The system of claim 3 where the data processing event includes performing a calculation.

6. The system of claim 2 where the Include and Exclude ZDD rule components have associated attributes and enumeration values.

7. The system of claim 6

where the associated attributes and enumeration values have an assigned indexed order;

where the ZDD includes ordered indices of attributes and enumeration values; and

where the means for storing is configured to store the ZDD in a reduced canonical form according to ordered indices.

8. The system of claim 7 where the ZDD has an initial size defined by a number of nodes, which nodes are subsequently reordered to reduce the size of the ZDD.

9. The system of claim 8 where the number of nodes of the Include and Exclude ZDD components of the ZDD are separately reduced prior to manipulatively combining.

10. A tangible computer readable medium having instructions stored thereon, the instructions comprising:

instructions to provide a cross-reference table of attributes and enumeration values indicative of rule components of the rule;

instructions to define components of the rule by selecting an inclusive or exclusive relation between the attributes and enumeration values in respective rows and columns of the table;

instructions to form an Include ZDD rule component from the inclusive relations;

instructions to form an Exclude ZDD rule component from exclusive relations;

instructions to produce an Attribute Relations ZDD rule component based on the Include and Exclude rule components;

instructions to construct the ZDD rule model based on the Include, Exclude, and Attribute Relations rule components; and

instructions to store the ZDD rule model in a memory.

11. The tangible computer readable medium of claim 10 further comprising:

instructions to assign an order to elements of the Include and Exclude rule components to established ordered indices; and

instructions to store the rule model in reduced canonical form according to the ordered indices.

12. The tangible computer readable medium of claim 11 where the table comprises a cross-reference matrix of attributes and related enumeration values.

13. The tangible computer readable medium of claim 11 further comprising:

instructions to define elective events according to a predetermined combination of attribute and enumeration values, which events are operative to invoke data processing to effect display of a message or performance of a calculation.

14. The tangible computer readable medium of claim 10

where the Include and Exclude rule components each have a number of nodes in their respective ZDD representations indicative of complexity;

and

further comprising instructions to reorder the nodes to reduce the complexity of the ZDD representations.

15. The tangible computer readable medium of claim 14 further comprising instructions to reorder the nodes prior to manipulatively combining the components to construct the ZDD rule model.