Notions of Strong Equivalence for Logic Programs with Ordered Disjunction

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Contents

Ordered disjunctions have been introduced as a simple, yet expressive approach for representing preferential knowledge by means of logic programs. The semantics for the resulting language is based on the answer-set semantics, but comes in different variants, depending on the particular interpretation of preference aggregation associated to the ordered disjunction connective. While in standard answer-set programming the question of when a program is to be considered equivalent to another received increasing attention in recent years, this problem has not been addressed for programs with ordered disjunctions so far. In this paper, we discuss the concept of strong equivalence in this setting. We introduce different versions of strong equivalence for programs with ordered disjunctions and provide model-theoretic characterisations, extending well-known ones for strong equivalence between ordinary logic programs. Furthermore, we discuss the relationships between the proposed notions and study their computational complexity.