Bottom up logic programming as an inference tool

It is well known that complete logical inference is computationally intractable. However, I take the position here that inference is a principle tool in improving efficiency in a wide variety of computations. My case for the pragmatic value of inference is based on technical results concerning bottom up logic programming. The basic intuition behind the value of inference involves the notion of “obvious consequence”. In many domains there is a class of questions which can be answered quickly. Pragmatically one is interested in constructing systems that can answer a useful class of questions quickly. Bottom up logic programming provides a flexible paradigm for doing this. I give one particularly startling result which states that a simple syntactic restriction on logic programs yields a simple programming language in which one can define all and only polynominal time decision procedures