Return to search

Tractable Inference Relations

We consider 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 we define inductive locality, a strengthening of locality. We 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. We show that locality, as a property of rule sets, is undecidable in general.

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/5969
Date01 December 1991
CreatorsGivan, Robert, McAllester, David
Source SetsM.I.T. Theses and Dissertation
Languageen_US
Detected LanguageEnglish
Format14 p., 1309278 bytes, 1033613 bytes, application/postscript, application/pdf
RelationAIM-1344

Page generated in 0.0016 seconds