In this paper we define a class of nested logic programs, nested logic programs with ordered disjunction (LP ODs + ), which allows to specify qualitative preferences by means of nested preference expressions. For doing this we extend the syntax of logic programs with ordered disjunction (LPODs) to capture more general expressions. We define the LP ODs + semantics in a simple way and we extend most of the results of logic programs with ordered disjunction showing how our approach effectively is a proper generalisation of LPODs.
Logic programs with ordered disjunction (LPODs) [2] are extended logic programs based on answer set semantics which combine some of the ideas underlying Qualitative Choice Logic [3] with logic programming. Indeed LPODs augment the traditional syntax of logic programs with a new ordered disjunction logic connective × to express preferences among literals in rules head. One distinctive characteristic of the × connective is its ability to induce an order among the answer sets of a logic program since each answer set is associated with a rule satisfaction degree which can be used to specify preference relations for answer sets selection [2]. In this ways LPODs represent a good candidate for the specification of problem solving methods targeting applications where preferences and conflicts between problem solutions are involved, such as configuration management, policy monitoring and user preference representation and reasoning [2].
The syntax of an LPOD allows the writing of rules of the kind A 1 ×. . .×A k ← B 1 , . . . , B m , not B m+1 , . . . , not B m+n , where each of the A i (with 1 ≤ i ≤ k) and B j 's (with 1 ≤ j ≤ m + n) are literals (elementary formulas), to express context-dependent preferences. Hence, they can encode simple preferences such as: In the night I prefer going to a pub over going to a cinema over watching tv (encoded as pub × cinema × tv ← night [2]), but their syntax is limited when other type of preference statements have to be formulated. For example, the preference concerning the activities for a night may want to express that in case pub is not possible, both cinema and tv are equally preferred. This case of preference indifference has been covered by Kärger et al. by means of logic programs with ordered and unordered disjunction (DLPODs) [8]. DLPODs extend LPODs combining the semantics of the ordered disjunction to express preferences and the disjunction to express indifferences. In this way their syntax allows to express preference equalities in ordered disjunction rules by means of combinations of literals connected by ∨. For example the indifference preference statement about cinema and tv in the night scenario can be encoded as pub × (cinema ∨ tv) ← night [8].
However, they may exist more complex preference statements that neither LPODs nor DLPODs are able to express. For instance, in the night preferences above, we can be instead concerned of having both options at the same time, expressing that in case pub is not possible we do mind watching a movie in the cinema and not in the tv, i.e. expressions such as pub × (cinema ∧ ¬tv) ← night, or that we even want to have equality and indifferences at the same time, i.e. expressions such as (pub ∨ bar) × (cinema ∧ ¬tv) ← night, or even more complex preference expression such as (pub ∧ (expensive × cheap)) × bar × (not pub ∧ not bar) ← night ∨ (not busy ∧ af ternoon). These examples suggest to explore for a less restricted syntax language.
For this reason, in this paper we present a more general syntax which allows the writing of nested (or non-flat) preferences expressions built by means of connectives {∨, ∧, ¬, not, ×}. To represent these formulas and to capture their semantics we define an extension of logic programs with ordered disjunction called nested logic programs with ordered disjunction (LP ODs + ).
The syntax of LP ODs + is based on a language which allows nested formulas that can provide a richer syntax at the moment of writing conditional preferences. The language we use is constructed using as a basis the propositional language of Qualitative Choice Logic [3], extended to consider negation as failure not, a typical connective which characterises non-monotonic reasoning in Answer Set Programming (ASP) [1].
To define the semantics of our LP ODs + we consider and extend some of the results in [9] where the semantics for nested logic programs is presented. In this way we can capture the semantics of an LP ODs + in a simple way and we show how when the formulas in an LP OD + are × free, the LP ODs + semantics and the semantics of nested logic programs coincide. Moreover, when an LP OD + syntactically corresponds to an LPOD the two semantics coincide as well.
In the presence of nested expression in the head of preference rules, the determination of the degree of satisfaction of an answer set of an LP OD + can be sometimes more involved in our approach. For this reason we propose a recursive function to calculate the optionality of complex preference formulas in order to determine the rule satisfaction degree. The optionality function is a generalisation of the rule satisfaction degree in LPODs, as a consequence, we can directly use the preference relations in [2] for comparing the answer sets of an LP OD + .
Our paper is structured as follows: after introducing the language we adopt to define our logic programs (Section 2), in Section 3 we present the syntax and the semantics of LP ODs + , and the optionality function for answer sets selec-tion. Finally Section 4 provides some prelimary discussions about related works, LP OD + complexity and sketches an implementation design of an LP OD + solver. Along the paper we present a running example which exemplifies the definitions of our approach. Due to space reasons we are not able to provide an extensive comparison with related approaches and we leave proofs' results out of the paper. It is our intention to cover these missings in an extended version.
The language we will consider to define the syntax of our logic programs is based on the language of Qualitative Choice Logic (QCL) extended with negation as failure not.
QCL is a propositional logic for representing alternatives for problem solutions defined by Brewka et al. in [3] which adds to classical propositional logic [6] a new connective × called ordered disjunction. 1The language we consider consists with: (i) an enumerable set L of elements called atoms (denoted a, b, c, . . .), (ii) connectives ∧, ∨, ×, ¬, not, ⊥, where {∧, ∨, ×}, {not, ¬}, { ,⊥} are 2-place, 1-place and 0-place connectives respectively and (iii) auxiliary symbols "(", ")", ".". If an atom a is negated by ¬ is known as negative literal, and a is known as positive literal if it is not preceded by ¬.
Literals, ⊥ and are considered elementary formulas, while formulas (denoted A, B, C) are constructed from elementary formula using the connectives {∨, ∧, ¬, not, ×} arbitrarily nested. 2A theory is a set of formulas and a logic program corresponds to a finite theory, i.e. a finite set of formula.
Based on this language we will define in Section 3 the syntax of nested logic programs with ordered disjunction. In the tradition of logic programming we write conditional expressions as the formula B ← A. We will consider two types of negation in our logic programs: strong negation ¬ and negation as failure not. Intuitively not a is true whenever there is no reason to believe a, whereas ¬a requires a proof of the negated atom. In this paper we assume that L is a finite set and we restrict our attention to finite propositional theories, since the semantics can be extended to programs with variables by grounding. Function symbols are, however, not allowed to ensure the ground program to be finite. This is a standard procedure in ASP.
This section presents the syntax of nested logic programs with ordered disjunction (LP OD + ) and their semantics which is characterised in terms of a recursive
Nested rule [9] reduction. We also define a recursive function for calculating the rule satisfaction degree of an answer set of an LP OD + for comparing answer sets.
Earlier in the paper we have pointed out how the syntax of existent logic programming approaches able to express qualitative preferences is usually quite restricted and for this reason we define a more expressive syntax. Let L be a set of atoms, then a nested ordered disjunction rule (rule for short) is an expression of the form H ← B., where H is either an elementary formula or a {∨, ∧, ¬, not, ×} formula (known as the head) and B is either an elementary formula or a {∨, ∧, ¬, not} formula (known as the body) built using the atoms in L. Some particular cases are facts, of the form H ← (written as H) and constraints, ⊥ ← B (written as ← B.). If no occurrences of not appear in a rule, the rule is a definite nested ordered disjunction rule (similarly a definite nested ordered disjunction formula). If no occurrences of × appear in a rule, the rule is a nested rule (similarly a nested formula). If no occurrences of × and not appear in a rule, then the rule is known as a definite nested rule (similarly a definite nested formula). Different formulas combinations can lead to different rules (some of them already defined in the literature) as shown in Table 1.
A nested logic program with ordered disjunction (LP OD + ) is a finite set of nested ordered disjunction rules and/or constraints and/or facts. If the program does not contain not the program is called a definite LP OD + . The set of all the atoms which appear in an LP OD + P is denoted by L P .
In our logic programs we will manage the strong negation ¬ as it is done in ASP [1]. Basically, each negative literal ¬a is replaced by a new atom symbol a which does not appear in L P and we add the constraint ← a, a to the program. For managing the constraints in our logic programs, we will replace each rule of the form ← B by a new rule of the from f ← B, not f such that f is a new atom symbol which does not appear in L P .
The use of {∨, ∧, ¬, not, ×} formulas in the head of nested ordered disjunction rules, rather than elementary formulas or disjunctive formulas only (as in [2,8]), provides a richer expressiveness in specifying qualitative preferences in our logic programs. Using ∨, and ∧ we can express for instance that certain options are equally preferred or that certain combinations are preferred over other combinations. The following program exemplifies some preference statements we can express by means of an LP OD + .
Example 1. Let P be an LP OD + representing the user preferences of the form:
Briefly, the intuitive reading of each of the rules of the program P is the following: r 1 expresses that we generally prefer to have italian over peruvian food and we prefer to have one of the options over not having any of them; r 2 tells that in the night we prefer to go to a pub or a bar, but if it not possible then we wish to see a movie in the cinema and not in the tv and r 3 just tells that we imperatively want to do something in the night time.
In the next section we define the semantics for inferring the answer set of an LP OD + .
Keeping in mind that the definition of answer sets semantics [7] consists of two parts (a syntactic reduction and a semantics for definite programs), the extension of this definition to LP OD + follows the same strategy. Thus, to define the semantics of our LP ODs + we consider and extend some of the results in [9] where a semantics for nested logic programs is presented. The first definitions are simply reported as they represent some basic results we reuse for achieving our scope. Instead, Definition 4 and 5 extend the original ones for nested programs to consider the × connective which characterizes our approach. Definition 1. [9] Let M be a set of atoms. M satisfies a definite nested formula A (denoted by M |= A), recursively as follows: M is called an answer set for P if M is minimal among the sets of atoms closed under P . Definition 4. The reduct of a nested ordered disjunction formula with respect a set of atoms M is defined recursively as follows:
Definition 5. The reduct P M × + of a nested logic program with ordered disjunction with respect to a set of atoms M is defined recursively as follows:
Clearly, M is an answer set of P {b,d,g} × + and so M is an answer set of P . Similarly, it can be proved that the sets of atoms {a, c, g}, {a, d, g}, {a, e, f , g}, {b, c, g}, {b, e, f , g}, {c, g}, {d, g} and {e, f , g} are valid answer sets of P as well.
It can be noticed that there is an interesting property of our LP OD + semantics. Besides the fact that LP OD + has a richer syntax they show to have a richer semantics as well. When all the rules of an LP OD + P are ordered disjunction rules (according to the syntax of LPODs in [2]), the LP OD + semantics and the LPODs semantics in fact coincide.
Proposition 1. Let P be an LP OD + such that ∀r ∈ P , r = A 1 × . . . × A k ← B 1 , . . . , B m , not B m+1 , . . . , not B m+n each A i (with 1 ≤ i ≤ k) and B j 'a (with 1 ≤ j ≤ m + n) are literals (or elementary formulas), and M be a set of atoms. M is answer set of P M × + if and only if M is answer set of P M × . 4
3 Due to representation issues we have changed the signature of the program from {italian, peruvian, pub, bar, cinema, tv, tv night} to {a, b, c, d, e, f, f g} respectively. 4 The P M × reduction is defined as S r∈P r M × , where r M × := {Ai ← B1, . . . , Bm|Ai ∈ M and M ∩ ({A1, . . . , Ai−1} ∪ {Bm+1, . . . , Bm+n}) = ∅} (see [2] for details).
Another interesting property is that when the formulas in our LP ODs + are formulas without the × connective, then the LP ODs + semantics and the semantics for nested logic programs defined in [9] coincide.
Proposition 2. Let P be an LP OD + such that ∀r ∈ P , r = H ← B, H and B are well-formed formulas × free, and M be a set of atoms. M is answer set of P M × + if and only if M is answer set of Π M .5
At the beginning of the paper we have pointed out how an LP OD + is a specification to express preferences about certain conditions inducing a preference order among its answer sets. Thus, the key question now is how such ordering can be achieved. In the simplest case where each rule of an LP OD + corresponds to an ordered disjunction rule, a satisfaction degree k (with 1 ≤ i ≤ k) can be associated to an answer set M w.r.t. a rule (deg M (r)) which corresponds to the position of the best satisfied literal [2]. However, when we consider a nested ordered disjunction rule r = H × B where H and B can be formulas built from {∨, ∧, ¬, not, ×} and {∨, ∧, ¬, not} respectively, the assignation of a satisfaction degree is not so trivial. Let us assume in fact that M is an answer set of an LP OD + P . How is possible to determine the satisfaction degree of M w.r.t. each rule r in P ? This degree may depend on how many options H admits. For this reason we first define the optionality of an answer set M w.r.t. a nested ordered disjunction formula H as follows:
Definition 7. Let H be a {∨, ∧, ¬, not, ×} formula, and M be an answer set of an LP OD + P . Then the optionality of M w.r.t. H, denoted by opt M (H) is recursively defined as follows:
Based on this function, the satisfaction degree of an answer set M w.r.t. a nested ordered disjunction rule r = H ← B can be defined as: Definition 8. Let M be an answer set of an LP OD + P . Then the satisfaction degree M w.r.t. a rule r = H ← B, denoted by deg + M (r) is:
The degrees can be viewed as penalties, in fact a higher degree expresses a lesser satisfaction. Thus, if the body of a rule is not satisfied, then there is no reason to be dissatisfied and the best possible degree 1 is obtained [2,3].
We can observe that there is a direct property w.r.t. the optionality function we defined for the answer sets of an LP OD + . The optionality function clearly generalises the satisfaction degree of answer sets of an LPOD. Proposition 3. Let P be an LP OD + such that ∀r ∈ P , r = A 1 × . . . × A k ← B 1 , . . . , B m , not B m+1 , . . . , not B m+n each A i (with 1 ≤ i ≤ k) and B j 's (with 1 ≤ j ≤ m + n) are literals (or elementary formulas), and M be an answer set of P . Then deg + M (r) = deg M (r). 6Therefore our approach also generalises in a consistent way the preference relation between answer sets of LPODs.
The case of M 2 looks more interesting as it shows how determining the degree of satisfaction can be sometimes more involved. As M 2 satisfies only the third condition in the head of rule r 1 , its optionality w.r.t. this rule has to take into account that the first two conditions are not satisfied, i.e.
The simplest case of r 3 is not represented as r 3 is clearly satisfied by degree 1 by both answer sets. Once the degrees are calculated the preference relation can be used to compare M 1 and M 2 . It is easy to see how M 1 is preferred to M 2 since M 1 satisfies the rules of the program in a better way (M 2 ≯ M 1 from Definition 9 as well).
The main scope of this paper has been to define the syntax and the semantics for nested logic programs with ordered disjunction. The syntax of an LP OD + is based on well-formed formulas built from connectives {∨, ∧, ¬, not} plus an ordered disjunction connective × which was first introduced in QCL and then used in logic programs with ordered disjunction. As a result, rules in LP ODs + are more general than rules which can be specified in related approaches of qualitative context-dependent preferences between literals such as LPODs [2] and DLPODs [8]. In fact compared to LPODs and DLPODs, the LP OD + syntax allows the specification of more complex formulas built by means of {∨, ∧, ¬, not, ×} formulas in the head of the rules and {∧, ∨, ¬, not} formulas in the body. In this respect we extend the syntax of LPODs and DLPODs rules where × and ×, ∨ literals' combinations are allowed. Among quantitative approaches to preference specification, it is worth to mention the work of Costantini et al. [5], where an extension of ASP is designed to model quantitative resources and enabling the specification of non-linear preferences (both in the heads and in the bodies).
We have shown how the LP OD + semantics can be defined in a lighter way (Definition 4, 5 and 6) than then LPODs semantics (which is based on split programs [2]) reusing and extending some definitions related to the semantics of nested logic programs [9]. We have also seen how when an LP OD + syntactically corresponds to an LPOD the two semantics coincide (Proposition 1) and when the formulas of an LP ODs + are × free, the LP OD + semantics coincide with the semantics of nested logic programs (Proposition 2). As LP ODs + allow complex formulas in their rules head, we have characterised the degree of satisfaction of an answer set w.r.t. a nested ordered disjunction rule (Definition 8) by means of a recursive optionality function (Definition 7). As the optionality function generalises the satisfaction degree defined for LPODs (Proposition 3) we have been able to reuse the preference relation criteria specified in [2] for comparing the answer sets of an LP OD + .
As far the complexity of reasoning is concerned, we have reasons to believe that the complexity of computing the answer sets of an LP OD + corresponds to the complexity of disjunctive logic programs. This can be informally motivated by the fact that by means of a transformation, we are currently investigating, which is able to convert nested ordered disjunction rules to × free ones (i.e. nested rules), we can reuse the polynomial translation for nested logic programs into disjunctive ones presented by Sarsakov et al. in [10]. Therefore, the implementation of an LP OD + solver can be sketched as follows: after extending the compiler for nested logic programming (nlp 7 ) to treat the × connector, the answer sets of an LP ODs + are computable by a disjunctive logic programming system such as DLV 8 . These results are preliminary and we need to explore them in a more precise way in an extended version of this paper.
Beside these extensions, as future work we are considering to extend the LP OD + formalism to be able to reason under incomplete evidence and partially inconsistent knowledge associating to each rule of an LP OD + a certainty degree following the same spirit as in our framework of logic programs with possibilistic ordered disjunction (LPPODs) we presented in [4]. The work in this paper represents in fact the first step towards an extension of the LPPODs framework. Last but not least, we aim to look for several possible applications we can target with our specification. So far, LP ODs + seem prominent to model application domains such as qualitative decision making with preferences and preference queries to databases.
Acknowledgements The authors would like to thank the anonymous referees for their useful suggestions and comments. This research has been partially supported by ICT-ALIVE (FP7-215890).