Course Notes on Inference Rules
This node contains one installment of the course notes for
MIT's graduate
course on the foundations of artificial intelligence.
This installment presents technical properties of inference
rules which I find to be most significant.
postscript.
Historical Comments
The basic idea of using forward chaining inference rules as a
programming language has a long history. It was used in early AI
languages such as AMORD (Sussman et al. circa 1978). It underlies the
OPS5 programming language for AI expert systems. The order theorem
presented in these notes, which allows the order of run time of a rule
set to be easily determined, is original and has not appeared
elsewhere. However, the proof of the theorem (which is not given
here) involves methods similar to those used in the Rete matching
algorithm for OPS5. The magic sets transformation was developed in
the database community. An overview of this and related techniques
can be found in the chapter "Bottom-UP Evaluation of Logic Programs"
by Jeffery Naughton and Raghu Ramakrishnan in the book "Computational
Logic: Essays in Honor of Alan Robinson" edited by Lassez and Plotkin,
MIT Press. The bounds predicate used in these notes is similar to
constructions introduced by Zaniolo and others and presented in PODS
(Principles of Database systems), 1992. The order theorem
for bounds assertions is original here. The characterization of the
complexity class P as the class of term languages recognized by
syntactically local rule sets was presented in the paper "New Results on Local Inference Relations" .
Related Nodes
The
relationship between the characterization of P given in these notes and
similar earlier results by
Immerman, Vardi, and others is discussed in my node on descriptive complexity .
More discussion of inference rules can be found
my personal node on inference rules.
David McAllester, February, 1995