Loop detection in rule-based expert systems

Details Loop detection in rule-based expert systems Loop detection in rule-based expert systems

2005-10-04

2005-10-04

Davis, George (Department: 2121)

Data processing: artificial intelligence

Knowledge processing system

Knowledge representation and reasoning technique

Reexamination Certificate

active

06952690

ABSTRACT:
This invention describes a method to verify non-looping properties of programs implemented as rule-based expert systems. Our method detects conditions under which the expert system enters erroneous infinite program loops, which lead to non-terminating or oscillating computations, or otherwise proves the absence of such conditions. Our automatic procedure also gives advice on how to correct these errors. The expert systems considered consist of condition-action rules (IF-THEN-statements), where the conditions are logical expressions (formulas of a propositional finite domain logic), and the actions modify the value of a single variable which in turn can be part of other logical expressions. There may be additional (external) variables not controlled by the expert system, and each rule may have an associated evaluation priority.

REFERENCES:
patent: 5228116 (1993-07-01), Harris et al.
patent: 5559718 (1996-09-01), Baisuck et al.
patent: 5592590 (1997-01-01), Jolly
patent: 5596752 (1997-01-01), Knudsen et al.
patent: 5751595 (1998-05-01), Beatty, III et al.
patent: 5826250 (1998-10-01), Trefler
patent: 5963739 (1999-10-01), Homeier
patent: 6063132 (2000-05-01), DeCamp et al.
patent: 6078737 (2000-06-01), Suzuki
patent: 6108670 (2000-08-01), Weida et al.
patent: 6175946 (2001-01-01), Ly et al.
patent: 6182020 (2001-01-01), Fairbanks
patent: 2003/0217133 (2003-11-01), Ostrup et al.
Park et al, “A Logic Based Expert System (LBES) for Fault Diagnosis of Power System”, IEEE Transaction on Power System, Feb. 1997.
Garone et al, “Capturing, Reusing, and Applying Knowledge for Competitive Advantage”, An IDC White Paper Sponsored by Computer Associates, pp. 1-12.
J. Horl et al “Formal Specification of a Voice Communication System Used in Air Traffic Control”, An industrial application of light-weight formal methods using VDM++, FM'99, vol. II, vol. 1709 of Lecture Notes in Computer Science, pp. 1868, 1999.
D. Harel, “Dynamic Logic”, Gabbay & Guenthner, editors, Handbook of Philosophical Logic, vol. II: Extensions of Classical Logic, pp. 507-544, Kluwer, 1984.
D. Harel et al, “Looping vs. Repeating in Dynamic Logic”, Information and Control, 55(1-3): pp. 175-192, 1982.
A. Kaiser, “A SAT-Based Propositional Prover for Consistency Checking of Automotive Product Data”, Technical Report, Wilhelm-Schickard-Institut fur Informatik, Eberhard-Karls-Universitat Tubingen, Sand 13, 72076 Tubingen, Germany, 2001. Technical Report WSI-2001-16.
Kautz et al, “Encoding Plans in Propositional Logic”, In Proc. Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR '96), pp. 374-384, Cambridge, MA, Nov. 1996.
Spreeuwenberg et al, “VALENS: A Knowledge Based Tool to Validate and Verify An Aion Knowledge Base”, In ECAI 2000, 14th European Conf. On Artificial Intelligence, pp. 731-735, IOS Press, 2000.
F. Somenzi, CUDD: CU Decision Diagram Package, Rel. 2.3.0, University of Colorado, Boulder, 1998.
R. Streett, “Propositional Dnamic Logic of Looping and Converse is Elementarily Decidable”, Information and Control, 54(1/2): pp. 121-141, 1982.
Grumberg et al, “A Proof Rule for Fair Termination of Guarded Commands”, Information and Control 66(1/2):pp. 83-102, 1985.
Gamble et al, “Applying Formal Verification Methods to Rule-Based Programs”, International Journal of Expert Systems: Research and Applications 7(3), pp. 203-237, 1994.
Preece et al, “Validating Dynamic Properties of Rule-Based Systems”, International Journal of Human ComputerStudies, 44(2): pp. 145-169, 1996.
Laffey et al, “Knowledge Base Verification”, AL Magazine, AAAI Press, Summer 1987, PP. 69-75.

Affiliated with

Also associated with

Rating

Loop detection in rule-based expert systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Loop detection in rule-based expert systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Loop detection in rule-based expert systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3447994