Investigations of Model-Preference Defaults
Mark Boddy, Robert P. Goldman, Keiji Kanazawa, Lynn Andrea Stein · 1989
Selman and Kautz's award-winning paper on the logic of modelpreference defaults introduced a new language and tractability results. This paper assesses the contributions of that work, including the properties of the logic itself, its relationship to some previous logics, and its applicability to some known tractable problems. Submitted to Fundamenta Informaticae Special Issue on Nonmonotonic Reasoning Boddy et al. --- Investigations of Model Preference Defaults 1 1 Introduction In an award-winning paper [11], Selman and Kautz presented the logic of model-preference defaults (MPD). MPD is a family of propositional default logics intended as a testbed for exploring nonmonotonic reasoning. Selman and Kautz define the search problem of finding a maximal model given an MPD axiomatization. They show that for general MPD axiomatizations this search problem is NP-hard. They describe a polynomial search algorithm for an MPD language limited to acyclic Horn-form defaults with a monotonic th...