INFERENCE WITH RECURSIVE RULES

Recursive rules, such as "Your parents' ancestors are your ancestors", although very useful for theorem proving, natural language understanding, questions-answering and information retrieval systems, present problems for many such systems, either causing infinite loops or requiring that arbitrarily many copies of them be made. We have written an inference system that can use recursive rules without either of these problems. The solution appeared automatically from a technique designed to avoid redundant work. A recursive rule causes a cycle to be built in an AND/OR graph of active processes. Each pass of data through the cycle resulting in another answer. Cycling stops as soon as either the desired answer is produced, no more answers can be produced, or resource bounds are exceeded.