Logic programs with ordered disjunction (s) combine ideas underlying Qualitative Choice Logic (Brewka, Benferhat, & Le Berre 2002) and answer set programming. Logic programming under answer set semantics is extended with anewconnective called ordered disjunction. The new connective allows us to represent alternative, ranked options for problem solutions in the heads of rules: intuitively means: if possible,butif is not possible then at least. The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets.

Logic programs with ordered disjunction (LPODs) combine ideas underlying Qualitative Choice Logic (Brewka, Benferhat, & Le Berre 2002) and answer set programming. Logic programming under answer set semantics is extended with a new connective called ordered disjunction. The new connective allows us to represent alternative, ranked options for problem solutions in the heads of rules: A B intuitively means: if possible A, butifA is not possible then at least B. The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. LPODs are useful for applications in design and configuration and can serve as a basis for qualitative decision making.

Several logical languages have been considered in AI for encoding compactly preference relations over a set of alternatives. In this paper, we analyze both the expressiveness and the spatial efficiency (succinctness) of such preference representation languages. The first issue is concerned with the nature of the preorders that can be encoded (for instance, all preorders, all complete preorders). The second issue is about how succinctly a preference relation can be expressed in those languages. We give polynomial-size translations in some cases, and prove the impossibility of such translations in other cases.

We give an overview of the multifaceted relationship between nonmonotonic logics and preferences. We discuss how the nonmonotonicity of reasoning itself is closely tied to preferences reasoners have on models of the world or, as we often say here, possible belief sets. Selecting extended logic programming with answer-set semantics as a generic nonmonotonic logic, we show how that logic defines preferred belief sets and how preferred belief sets allow us to represent and interpret normative statements. Conflicts among program rules (more generally, defaults) give rise to alternative preferred belief sets. We discuss how such conflicts can be resolved based on implicit specificity or on explicit rankings of defaults.

Brewka, Gerhard (University of Kentucky) | Niemela, Ilkka | Truszczynski, Miroslaw

We give an overview of the multifaceted relationship between nonmonotonic logics and preferences. We discuss how the nonmonotonicity of reasoning itself is closely tied to preferences reasoners have on models of the world or, as we often say here, possible belief sets. Selecting extended logic programming with the answer-set semantics as a "generic" nonmonotonic logic, we show how that logic defines preferred belief sets and how preferred belief sets allow us to represent and interpret normative statements. Conflicts among program rules (more generally, defaults) give rise to alternative preferred belief sets. We discuss how such conflicts can be resolved based on implicit specificity or on explicit rankings of defaults. Finally, we comment on formalisms which explicitly represent preferences on properties of belief sets. Such formalisms either build preference information directly into rules and modify the semantics of the logic appropriately, or specify preferences on belief sets independently of the mechanism to define them.