LFA: a linear forward-chaining algorithm for AI production systems

Abstract: The LFA algorithm is a linear forward-chaining algorithm for AI production systems. It finds all the possible solutions for each given problem in a time proportional to the number of rules in a knowledge base, after all the possible evidence about the problem has been given. This paper presents the algorithm in detail. Another new technique, the'rule schema + rule body'representation, which is coupled with the chaining algorithm to support high efficiency of production system interpreters, is also described here.