Tractable Inference Relations
Abstract
This paper considers the concept of local sets of inference rules. Locality is a syntactic condition on rule sets which guarantees that the inference relation defined by those rules is polynomial time decidable. Unfortunately, determining whether a given rule set is local can be difficult. In this paper, the authors define inductive locality, a strengthening of locality. They also give a procedure which can automatically recognize the locality of any inductively local rule set. Inductive locality seems to be more useful that the earlier concept of strong locality. There are many natural examples of inductively local rule sets that are not strongly local. They have not found any natural examples of local rule sets that fail to be inductively local. However, they show here that locality, as a property of rule sets, is undecidable in general.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1991
- Accession Number
- ADA260169
Entities
People
- David Mcallester
- Robert Givan
Organizations
- Massachusetts Institute of Technology