LOOP DETECTION IN RULE-BASED EXPERT SYSTEMS

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.