Polynomial-time Computation via Local Inference Relations

Robert Givan, David McAllester

We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial…