=Paper=
{{Paper
|id=None
|storemode=property
|title=Nested logic programs with ordered disjunction
|pdfUrl=https://ceur-ws.org/Vol-677/06_LANMR10.pdf
|volume=Vol-677
}}
==Nested logic programs with ordered disjunction==
https://ceur-ws.org/Vol-677/06_LANMR10.pdf
Nested Logic Programs with Ordered
Disjunction
Roberto Confalonieri and Juan Carlos Nieves
Universitat Politècnica de Catalunya
Dept. Llenguatges i Sistemes Informàtics
C/ Jordi Girona Salgado 1-3
E - 08034 Barcelona
{confalonieri,jcnieves}@lsi.upc.edu
Abstract 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.
1 Introduction
Logic programs with ordered disjunction (LPODs) [2] are extended logic pro-
grams 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 specifi-
cation of problem solving methods targeting applications where preferences and
conflicts between problem solutions are involved, such as configuration manage-
ment, policy monitoring and user preference representation and reasoning [2].
The syntax of an LPOD allows the writing of rules of the kind A1 ×. . .×Ak ←
B1 , . . . , Bm , not Bm+1 , . . . , not Bm+n , where each of the Ai (with 1 ≤ i ≤ k)
and Bj ’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
55
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 prefer-
ences. The language we use is constructed using as a basis the propositional
language of Qualitative Choice Logic [3], extended to consider negation as fail-
ure 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 de-
termination 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 generalisa-
tion 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-
56
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.
2 Language Considered
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 solu-
tions defined by Brewka et al. in [3] which adds to classical propositional logic
[6] a new connective × called ordered disjunction.1
The 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 (de-
noted A, B, C) are constructed from elementary formula using the connectives
{∨, ∧, ¬, not, ×} arbitrarily nested.2
A 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.
3 LP ODs+
This section presents the syntax of nested logic programs with ordered disjunc-
tion (LP OD+ ) and their semantics which is characterised in terms of a recursive
1 →
−
The original connective is denoted by × , however we write × for consistent notation
with ordered disjunction used in Answer Set Programming [2,4].
2
In the following we assume that the connectives ∧, ∨, and not have stronger bindings
than ×. We also assume that × is associative.
57
Table 1. Example of rules captured by LP OD+ syntax
Syntax Rule Type
(a ∧ (b × c)) × (d ∨ e) ← g ∨ (not i ∧ f ). Nested Ordered Disjunction rule
a ∨ (b × ¬c) ← d ∨ (e ∧ f ). Definite Nested Ordered Disjunction rule
a ∧ b ← p ∧ (¬q ∨ r). Definite Nested rule [9]
a × (b ∨ c) ← d ∧ not e. Ordered Disjunctive rule [8]
a × b ← c ∧ not d. Ordered Disjunction rule [2]
a ∨ b ← c ∧ not ¬e. Disjunctive rule [7]
a ∧ not b ← p ∧ not (¬q ∨ r). 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.
3.1 Syntax
Earlier in the paper we have pointed out how the syntax of existent logic pro-
gramming 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 LP .
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 a0
which does not appear in LP and we add the constraint ← a, a0 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 LP .
The use of {∨, ∧, ¬, not, ×} formulas in the head of nested ordered disjunc-
tion 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 op-
tions are equally preferred or that certain combinations are preferred over other
58
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:
r1 = italian × peruvian × (not italian ∧ not peruvian) .
r2 = (pub ∨ bar) × (cinema ∧ ¬tv) ← night.
r3 = night.
Briefly, the intuitive reading of each of the rules of the program P is the following:
r1 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; r2 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 r3 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+ .
3.2 Semantics
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:
– for elementary A, M |= A if A ∈ M ∨ A = >
– M |= A ∧ B if M |= A ∧ M |= B
– M |= A ∨ B if M |= A ∨ M |= B
Definition 2. [9] Let P be a definite nested logic program. A set of atoms M
is closed under P if, ∀r ∈ P , M |= H whenever M |= B.
Definition 3. [9] Let M be a set of atoms and P a definite nested logic program.
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:
– for elementary A, AM = A
– (A ∧ B)M = AM ∧ B M
– (A ∨ B)M = AM ∨ B M
59
(
M⊥, if M |= AM
– (not A)
>, otherwise
M M
A , if M |= A
M
– (A × B) B M , if M 6|= AM ∧ M |= B M
⊥, otherwise
Definition 5. The reduct P×M+ of a nested logic program with ordered disjunc-
tion with respect to a set of atoms M is defined recursively as follows:
– (H ← B)M = H M ← B M
– P×M+ = {(H ← B)M | H ← B ∈ P }
Please notice that P×M+ is a definite nested logic program, i.e. × and not free.
Hence, the following definition follows in a straightforward way from the answer
set definition for definite nested logic programs.
Definition 6. Let P be an LP OD+ and M a set of atoms. M is answer set of
P if it is an answer set of P×M+ .
Example 2. Let us consider the LP OD+ P in Example 13 and the set of atoms
{b,d,g}
M = {b, d, g}. Then P×+ can be obtained in three recursive steps applying
Definition 4 and 5:
(1) (2) (3)
(a × b × (not a ∧ not b)){b,d,g} . b{b,d,g} . b.
(c ∨ d) × (e ∧ f 0 ) ← g){b,d,g} . (c ∨ d){b,d,g} ← g {b,d,g} . c ∨ d ← g.
(g){b,d,g} . g. g.
(← f ∧ f 0 .){b,d,g} . ← f {b,d,g} ∧ f 0{b,d,g} . ← f ∧ f 0 .
{b,d,g}
Clearly, M is an answer set of P×+ 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 0 , g}, {b, c, g},
{b, e, f 0 , g}, {c, g}, {d, g} and {e, f 0 , g} are valid answer sets of P as well.
It can be noticed that there is an interesting property of our LP OD+ seman-
tics. 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 = A1 × . . . × Ak ←
B1 , . . . , Bm , not Bm+1 , . . . , not Bm+n each Ai (with 1 ≤ i ≤ k) and Bj ’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
0
{italian, peruvian, pub, bar, cinema,
S tv, tvMnight} to M {a, b, c, d, e, f, f 0 g} respectively.
4 M
The P× reduction is defined as r∈P r× , where r× := {Ai ← B1 , . . . , Bm |Ai ∈
M and M ∩ ({A1 , . . . , Ai−1 } ∪ {Bm+1 , . . . , Bm+n }) = ∅} (see [2] for details).
60
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
3.3 Answer Sets Selection
At the beginning of the paper we have pointed out how an LP OD+ is a spec-
ification 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 (degM (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 optM (H) is
recursively defined as follows:
1,if H = A and A is an elementary formula
if H = (not P ) then k = optM (P )
if H = (P ∧ Q) then k = max{optM (P ), optM (Q)}
optM (H)
k if H = (P ∨ Q) then k(= max{optM (P ), optM (Q)}
M
if H = (P × Q) then k = optM (P ), if M |= P
k = optM (P ) + optM (Q), otherwise
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 degM (r) is:
(
+ 1, if M 6|= B M
degM (r)
optM (H), otherwise
5
The Π M reduction is defined as the P×M+ without the × case (see [9] for details).
61
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 = A1 × . . . × Ak ←
B1 , . . . , Bm , not Bm+1 , . . . , not Bm+n each Ai (with 1 ≤ i ≤ k) and Bj ’s (with
1 ≤ j ≤ m + n) are literals (or elementary formulas), and M be an answer set
+
of P . Then degM (r) = degM (r).6
Therefore our approach also generalises in a consistent way the preference
relation between answer sets of LPODs.
Definition 9. [2] M1 is preferred to M2 (denoted by M1 > M2 ) iff ∃ r ∈ P
+ + + +
such that degM 1
(r) < degM 2
(r), and @r0 ∈ P such that degM 2
(r0 ) < degM 1
(r0 ).
Example 3. Let P be the LP OD+ in Example 1 and M1 = {a, c, g}, M2 =
{e, f 0 , g} be two of the answer sets of P in Example 2. We want to show that
M1 > M2 . For doing this, we first have to calculate the satisfaction degrees of M1
and M2 w.r.t. all the rules in P . Applying Definition 7 and 8 we can see how the
+ +
degrees of M1 w.r.t. r1 and r2 correspond to degM 1
(r1 ) = 1 and degM 1
(r2 ) = 1
respectively since:
optM1 (a × b × (not a ∧ not b)) = 1 optM1 ((c ∨ d) × (e ∧ f 0 )) = 1
optM1 (a × b) = 1 optM1 (c ∨ b) = 1
optM1 (a) 1
1
The case of M2 looks more interesting as it shows how determining the de-
gree of satisfaction can be sometimes more involved. As M2 satisfies only the
third condition in the head of rule r1 , its optionality w.r.t. this rule has to take
+
into account that the first two conditions are not satisfied, i.e. degM 2
(r1 ) = 2
+ optM1 (not a ∧ not b). As shown below the degrees of M2 w.r.t. r1 and r2
+ +
correspond to degM 2
(r1 ) = 3 and degM 2
(r2 ) = 2 respectively since:
6
We refer to [2] for the definition of degM (r).
62
optM2 (a × b × (not a ∧ not b)) = 3 optM2 ((c ∨ d) × (e ∧ f 0 )) = 2
0
optM2 (a × b) = 2 . . . (not a ∧ not b) = 1 . . . (c ∨ d) = 1 optM2 (e ∧ f ) = 1
1 optM2 (e) optM2 (f 0 )
optM1 (a) optM2 (b) . . . (not a) . . . (not b)
1 1 . . . (a) . . . (b) 1 1
1 1
The simplest case of r3 is not represented as r3 is clearly satisfied by degree
1 by both answer sets. Once the degrees are calculated the preference relation
can be used to compare M1 and M2 . It is easy to see how M1 is preferred to
M2 since M1 satisfies the rules of the program in a better way (M2 ≯ M1 from
Definition 9 as well).
4 Conclusions, Discussions and Future Research
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 ap-
proaches 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
63
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 im-
plementation of an LP OD+ solver can be sketched as follows: after extending
the compiler for nested logic programming (nlp7 ) to treat the × connector, the
answer sets of an LP ODs+ are computable by a disjunctive logic programming
system such as DLV8 . 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 par-
tially 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 refer-
ees for their useful suggestions and comments. This research has been partially
supported by ICT-ALIVE (FP7-215890).
References
1. Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving.
Cambridge University Press (2003)
2. Brewka, G., Niemelä, I., Syrjänen, T.: Logic Programs with Ordered Disjunction.
Computational Intelligence 20(2) (2004) 333–357
3. Brewka, G., Benferhat, S., Le Berre, D.: Qualitative Choice Logic. Artificial
Intelligence 157(1-2) (2004) 203–237
4. Confalonieri, R., Nieves, J.C., Osorio, M., Vázquez-Salceda, J.: Possibilistic Se-
mantics for Logic Programs with Ordered Disjunction. In Link, S., Prade, H., eds.:
FoIKS 2010. Volume 5956 of LNCS., Berlin,Heidelberg, Springer-Verlag (2010)
7
http://www.cs.uni-potsdam.de/~torsten/nlp/
8
http://www.dbai.tuwien.ac.at/proj/dlv/
64
5. Costantini, S., Formisano, A.: Modeling preferences and conditional preferences on
resource consumption and production in ASP. Journal of Algorithms 64(1) (2009)
3–15
6. van Dalen, D.: Logic and Structure. Third, augmented edition edn. Springer-
Verlag, Berlin (1994)
7. Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive
Databases. New Generation Computing 9(3/4) (1991) 365–386
8. Kärger, P., Lopes, N., Olmedilla, D., Polleres, A.: Towards Logic Programs with
Ordered and Unordered Disjunction. Workshop on Answer Set Programming and
Other Computing Paradigms (ASPOCP), ICLP 2008, (2008) 46–60
9. Lifschitz, V., Tang, L.R., Turner, H.: Nested expressions in logic programs. Annals
of Mathematics and Artificial Intelligence 25(3-4) (1999) 369–389
10. Sarsakov, V., Schaub, T., Tompits, H., Woltran, S.: nlp: A Compiler for Nested
Logic Programming. In Lifschitz, V., Niemelä, I., eds.: LPNMR04. Volume 2923
of LNCS., Springer (2004) 361–364
65
66