Model-preference default theories

Most formal theories of default inference have very poor computational properties, and are easily shown to be intractable, or worse, undecidable. We are therefore investigating limited but efficiently computable theories of default reasoning. This paper defines systems of propositional model-preference defaults, which provide a model-theoretic account of default inference with exceptions. The most general system of model-preference defaults is decidable but still intractable. Inspired by the very good (linear) complexity of propositional Horn theories, we consider systems of Horn defaults. Surprisingly, finding a most preferred model in even this very limited system is shown to be NP-hard. Tractability can be achieved in two ways: by eliminating the “specificity ordering” among default rules and by restricting our attention to systems of acyclic Horn defaults. These acyclic theories can encode acyclic defeasible inheritance hiearchies, but are more general.

Authors

• Bart Selman
• Henry A. Kautz Michael J. Kearns

Keywords

No keywords are indexed for this paper.