=Paper=
{{Paper
|id=Vol-1335/wlp2014_paper1
|storemode=property
|title=Embedding Defeasible Logic Programs into
Generalized Logic Programs
|pdfUrl=https://ceur-ws.org/Vol-1335/wlp2014_paper1.pdf
|volume=Vol-1335
|dblpUrl=https://dblp.org/rec/conf/wlp/BalazFHSF14
}}
==Embedding Defeasible Logic Programs into
Generalized Logic Programs==
https://ceur-ws.org/Vol-1335/wlp2014_paper1.pdf
Embedding Defeasible Logic Programs
into Generalized Logic Programs
Martin Baláž1 , Jozef Frtús1 , Martin Homola1 , Ján Šefránek1 , and Giorgos
Flouris2
1
Comenius Unversity in Bratislava, Slovakia
2
FORTH-ICS, Greece
Abstract. A novel argumentation semantics of defeasible logic pro-
grams (DeLP) is presented. Our goal is to build a semantics, which
respects existing semantics and intuitions of “classical” logic program-
ming. Generalized logic programs (GLP) are selected as an appropriate
formalism for studying both undermining and rebutting. Our argumenta-
tion semantics is based on a notion of conflict resolution strategy (CRS),
in order to achieve an extended flexibility and generality. Our argumen-
tation semantics is defined in the frame of assumption-based framework
(ABF), which enables a unified view on different non-monotonic for-
malisms. We present an embedding of DeLP into an instance of ABF.
Consequently, argumentation semantics defined for ABF are applicable
to DeLP. Finally, DeLP with CRS is embedded into GLP. This trans-
formation enables to commute argumentation semantics of a DeLP via
semantics of the corresponding GLP.
1 Introduction
Defeasible Logic Programs (DeLPs) [8] combine ideas from Defeasible Logic
[13,12] and Logic Programming. While classically, logic programs (LPs) feature
default negation, which enables to express default assumptions (i.e., propositions
which are supposed to hold unless we have some hard evidence against them),
DeLPs additionally introduce defeasible rules (i.e., rules which are supposedly
applicable unless we have some hard evidence opposing them). Strict rules (i.e.,
regular LP rules) are denoted by → and defeasible rules by ⇒. Let us illustrate
this with an example.
Example 1. Brazil is the home team, and has a key player injured. Home teams
tend to work the hardest, and who works the hardest usually wins. The team
who has a key player injured does not usually win. The program is formalized
into the DeLP:
→ home r1 : home ⇒ works_hard r2 : works_hard ⇒ wins
→ key_player _injured r3 : key_player _injured ⇒ not wins
In the program from Example 1 there are two strict and three defeasible
rules. The strict rules are facts, hence home and key_player _injured should
always be true. Based on the first fact we are able to derive that Brazil should
win, using the two defeasible rules r1 and r2 , while based on the second fact we
are able to derive that Brazil should not win, again relying on a defeasible rule,
in this case r3 . Hence there is a conflict which somehow should be resolved.
Various approaches to DeLP typically rely on argumentation theory in or-
der to determine which rules should be upheld and which should be defeated.
However, as it can be perceived from Example 1, it is not always immediately
apparent how this should be decided.
According to García and Simari [8], both rules immediately causing the con-
flict (r2 and r3 ) would be undecided, accepting home, key_player _injured and
works_hard as valid derivations while taking both wins and not wins as un-
decided. ASPIC+ [14,11], on the other hand, allows two additional solutions,
one with r2 undefeated, r3 defeated, and wins valid; and the other one with r2
defeated, r3 undefeated, and not wins valid.
Some approaches, like ASPIC+ , allow to specify a preference relation on
rules. In such a case conflict resolution may take this into account. Specifically,
ASPIC+ has two built-in conflict resolution strategies, weakest-link principle by
which the rule with smallest preference is defeated among those involved in each
conflict, and last-link principle by which only the rules immediately causing the
conflict are considered and the least preferred is defeated.
We observe that more ways to resolve conflicts may be needed. This is due to
the fact that defeasible rules are domain specific, a different conflict resolution
strategy may be needed for a different domain, or in distinct application. We
therefore argue that the conflict resolution strategy should be a user-specified
parameter of the framework, and any DeLP framework should allow a generic
way how to specify it (alongside some predefined strategies).
Some of the semantics proposed for DeLP satisfy the well accepted rationality
properties for defeasible reasoning, such as consistency (extensions should be
conflict-free) and closure (extensions should be closed w.r.t. the strict rules),
as defined by Caminada and Amgoud [4]. While these properties are important,
DeLP is an extension of LP, and some attention should be also devoted to keeping
it in line with it. Specifically, we would like to have the semantics backward-
compatible with the underlying language of logic programs – if no defeasible
rules are present, the extensions should be in line with the respective class of
models.
In our previous work [2] we have formalized the notion of conflict resolution
strategy (CRS) and we have proposed a DeLP framework which allows to use
any such strategy. The relationship with the underlying class of LPs was not
investigated though. In the current paper we extend this work as follows:
– We rebuild the argumentation semantics (including the notion of conflict
resolution strategy) using the Assumption Based Framework (ABF), an ar-
gumentation formalism very close in spirit to logic programming.
– We show that the semantics satisfies the closure and consistency properties
[4], and we also show two additional properties which govern the handling
of defeasible rules.
– We provide an alternative transformational semantics, which translates the
DeLP and the given CRS into a regular logic program. We show that both
semantics are equivalent. Thanks to the transformational semantics we also
show full backward compatibility with the underlying class of generalized
logic programs. What is more, the semantics of DeLP can now be computed
using existing LP solvers.
All proofs can be found in a technical report which appears at http://
kedrigern.dcs.fmph.uniba.sk/reports/download.php?id=58.
2 Preliminaries
Generalized logic programs and assumption-based frameworks provide a back-
ground for our investigation. We are aiming at a computation of our argumenta-
tion semantics of DeLP in the frame of classical logic programs. Generalized logic
programs (with default negations in the heads of rules) are selected as a simplest
LP-formalism, which enables to consider both undermining and rebutting.
Assumption-based frameworks are used in our paper as a basis for building a
semantics of DeLP. ABF is a general and powerful formalism providing a unified
view on different non-monotonic formalisms using argumentation semantics.
2.1 Generalized Logic Programs
We will consider propositional generalized logic programs (GLPs) in this paper.
Let At be a set of atoms and not At = {not A | A ∈ At} be a set of default
literals. A literal is an atom or a default literal. The set of all literals is denoted
by LAt . If L = not A and A ∈ At, then by not L we denote A. If S ⊆ LAt , then
not S = {not A | A ∈ S }.
A rule over LAt is an expression r of the form L1 , . . . , Ln → L0 where 0 ≤ n
and Li ∈ LAt for each 0 ≤ i ≤ n. The literal head (r ) = L0 is called the head of
r and the set of literals body(r ) = {L1 , . . . , Ln } is called the body of r .
A generalized logic program is a finite set of rules. We will often use only the
term program. If At is the set of all atoms used in a program P, it is said that
P is over At. If heads of all rules of a program P are atoms, it is said that P is
normal. A program P is called positive if the head of every rule is an atom and
the body of every rule is a set of atoms or propositional constants t, u, f .
Note that a GLP P can be viewed as consisting of two parts, a normal logic
program P + = {r ∈ P | head (r ) ∈ At} (also called the positive part of P) and
a set of “constraints” P − = P \ P + (also called the negative part of P).
Our definitions of some basic semantic notions follow the ideas of Przymusin-
ski [17] (see also [6]); however, an adaptation to the case of rules with default
negations in head is needed. In our approach we will use the positive part P + of
the program as a generator of a broad set of candidate models and consecutively
we will use the negative part P − to filter out some of the models.
Definition 1 (Partial and Total Interpretation). A set of literals S is con-
sistent, if it does not contain a pair A, not A where A ∈ At. A partial interpreta-
tion is a consistent set of literals. A total interpretation is a partial interpretation
I such that for every A ∈ At either A ∈ I or not A ∈ I .
Each interpretation can be viewed as a mapping I : At 7→ {0, 21 , 1} where
I (A) = 0 if not A ∈ I , I (A) = 12 if A 6∈ I and not A 6∈ I , and I (A) = 1 if A ∈ I .
A valuation given by an interpretation I is a mapping Î : LAt 7→ {0, 21 , 1} where
Î (A) = I (A) and Î (not A) = 1 − I (A) for each atom A ∈ At, and Î (t) = 1,
Î (u) = 21 , Î (f ) = 0. An interpretation I satisfies a rule r (denoted I |= r ) iff
Î (head (r )) ≥ Î (body(r )) = min{Î (L) | L ∈ body(r )}.
Definition 2 (Model). An interpretation I is a model of a generalized logic
program P iff I satisfies each rule in P.
As usual in logic programming, “classical” model, as defined above, are too
broad and a number of more fine-grained semantics, based on certain notion
of minimality are used. We proceed by defining these semantics summarily for
GLPs. Not all of them were thoroughly investigated in literature, however we use
analogy with other classes of logic programs, especially normal logic programs.
The notions of truth ordering and knowledge ordering on partial interpreta-
tions will be needed. For a partial interpretation I , let T (I ) = {A ∈ At | I (A) =
1} and F (I ) = {A ∈ At | I (A) = 0}.
Definition 3 (Truth and Knowledge Ordering). If I , J are partial inter-
pretations, then
– I ≤t J iff T (I ) ⊆ T (J ) and F (I ) ⊇ F (J ),
– I ≤k J iff T (I ) ⊆ T (J ) and F (I ) ⊆ F (J ).
Definition 4 (Program Reduct). Let I be an interpretation. The reduct of
a normal logic program P is a positive logic program P I obtained from P by
replacing in every rule of P all default literals which are true (resp. unknown,
resp. false) in I by propositional constant t (resp. u, resp. f ).
Finally a fixed-point condition is expressed on a reduced program, which is
formally captured by the operator ΓP .
Definition 5 (Operator ΓP ). Let P be a normal logic program and I be an
interpretation. By ΓP (I ) we denote the t-least model of P I .
Definition 6 (Semantics Family for GLPs). Let P be a generalized logic
program and I be a model of P. Then
– I is a partial stable model of P iff ΓP + (I ) = I
– I is a well-founded model of P iff I is a k-minimal partial stable model of P
– I is a maximal stable model of P iff I is a k-maximal partial stable model
of P
– I is a least-undefined stable model of P iff I is a partial stable model of P
with subset-minimal {A ∈ At | I (A) = 12 }
– I is a total stable model of P iff I is a partial stable model of P which is
total
The produced semantics properly generalize existing semantics for normal
logic programs.
Proposition 1. If P is a normal logic program, the notion of partial stable
model in Definition 6 coincides with the definition of partial stable models in [17],
the notion of total stable model in Definition 6 coincides with the definition of
stable models in [10], the notion of well-founded model in Definition 6 coincides
with the definition of well-founded model in [9], and the notions of maximal
and least-undefined stable model in Definition 6 coincides with the definition of
maximal and least-undefined stable models in [18].
If P is a generalized logic program, the definition of stable models in Defini-
tion 6 coincides with the definition of stable models in [1].
2.2 Assumption-based Framework
Assumption-based frameworks (ABF) [3] enable to view non-monotonic reason-
ing as a deduction from assumptions. Argumentation semantics of [7,5] were
applied to sets of assumptions. As a consequence, a variety of semantic charac-
terizations of non-monotonic reasoning has been provided.
An ABF is constructed over a deductive system. A deductive system is a pair
(L, R) where L is a language and R is a set of inference rules over L. A language
is a set L of all well-formed sentences. Each inference rule r over L is of the
form ϕ1 , . . . , ϕn → ϕ0 where 0 ≤ n and ϕi ∈ L for each 0 ≤ i ≤ n. The
sentence head (r ) = ϕ0 is called the head of r and the set of sentences body(r ) =
{ϕ1 , . . . , ϕn } is called the body of r .
A theory is a set S ⊆ L of sentences. A sentence ϕ is an immediate conse-
quence of a theory S iff there exists an inference rule r ∈ R with head (r ) = ϕ
and body(r ) ⊆ S . A sentence ϕ is a consequence of a theory S iff there is a se-
quence ϕ1 , . . . , ϕn , 0 < n, of sentences such that ϕ = ϕn and for each 0 < i ≤ n
holds ϕi ∈ S or ϕi is an immediate consequence of {ϕ1 , . . . , ϕi−1 }. By Cn R (S )
we denote the set of all consequences of S .
An assumption-based framework is a tuple F = (L, R, A, ) where (L, R) is
a deductive system, A ⊆ L is a set of assumptions, and : A 7→ L is a mapping
called contrariness function. We say that α is the contrary of an assumption α.
A context is a set ∆ ⊆ A of assumptions. We say that ∆ is conflict-free
iff {α, α} * Cn R (∆) for each assumption α. A context ∆ is closed iff ∆ =
Cn R (∆) ∩ A, i.e., only such assumptions, which are members of ∆, are derivable
from ∆. A context ∆ attacks an assumption α iff α ∈ Cn R (∆). A context
∆ defends an assumption α iff each closed context attacking α contains an
assumption attacked by ∆.
ABFs enable to apply argumentation semantics to sets of assumptions and,
consequently, subtle and rich semantic characterizations of sets of assumptions
(and of their consequences) can be specified. A closed context ∆ is
– attack-free iff ∆ does not attack an assumption in ∆;
– admissible iff ∆ is attack-free and defends each assumption in ∆;
– complete iff ∆ is admissible and contains all assumptions defended by ∆;
– grounded iff ∆ is a subset-minimal complete context;
– preferred iff ∆ is a subset-maximal admissible context;
– semi-stable iff ∆ is a complete context such that ∆ ∪ {α ∈ A | ∆ attacks α}
is subset-maximal;
– stable iff ∆ is attack-free and attacks each assumption which does not belong
to ∆.
3 Defeasible Logic Programs
Our knowledge can be divided according to its epistemological status into two
categories: on the one hand, one that is gained by deductively valid reasoning
and on the other hand, knowledge that is reached by defeasible reasoning [13].
Defeasible logic programs (DeLPs) [15,8,14,11] consider two kinds of rules: strict
and defeasible. Strict rules represent deductive reasoning: whenever their pre-
conditions hold, we accept the conclusion. Defeasible rules formalize tentative
knowledge that can be defeated and validity of preconditions of a defeasible rule
does not necessarily imply the conclusion. Given a set of literals LAt , a strict
(resp. defeasible) rule is an expression L1 , . . . , Ln → L0 (resp. L1 , . . . , Ln ⇒ L0 )
where 0 ≤ n and Li ∈ LAt for each 0 ≤ i ≤ n. We will use to denote ei-
ther a strict or a defeasible rule. Each defeasible rule r has assigned its name
name(r ). The name of r is a default literal from separate language LN . The
intuitive meaning of name(r ) = not A is “by default, the defeasible rule r can
be used”, and consequently, the intuitive meaning of not name(r ) = A is “the
defeasible rule r can not be used”. In the following, we will denote the defeasible
rule r = L1 , . . . , Ln ⇒ L0 with name(r ) = not A as A : L1 , . . . , Ln ⇒ L0 .
Definition 7 (Defeasible Logic Program). Let At be a set of atoms, N be
a set of names, and At ∩ N = ∅. A defeasible logic program is a tuple P =
(S, D, name) where S is a set of strict rules over LAt , D is a set of defeasible
rules over LAt , and name : D 7→ not N is an injective naming function.
3.1 From Arguments to Conflict Resolutions
The argumentation process usually consists of five steps [15,16,8,14,11]. At the
beginning, a knowledge base is described in some logical language. The notion of
an argument is then defined within this language. Then conflicts between argu-
ments are identified. The resolution of conflicts is captured by an attack relation
(also called “defeat relation” in some literature) among conflicting arguments.
The status of an argument is then determined by the attack relation. In this
paper, conflicts are not resolved by attacking some of the conflicting arguments,
but by attacking some of the weak parts of an argument called vulnerabilities.
This helps us to satisfy argumentation rationality postulates [4] and to keep the
semantics aligned with LP intuitions.
Two kinds of arguments can usually be constructed in the language of defea-
sible logic programs. Default arguments correspond to default literals. Deductive
arguments are constructed by chaining of rules.
We define several functions prems, rules and vuls denoting premises (i.e. de-
fault literals) and rules occurring in an argument. Intended meaning of vuls(A) is
a set of vulnerabilities of an argument A (i.e., weak parts which can be defeated)
consisting of premises and names of defeasible rules of an argument A.
Definition 8 (Argument). Let P = (S, D, name) be a defeasible logic pro-
gram. An argument A for a literal L is
1. a default argument L where L is a default literal.
prems(A) = {L}
rules(A) = ∅
2. a deductive argument [A1 , . . . , An L] where 0 ≤ n, each Ai , 0 < i ≤ n, is
an argument for a literal Li , and r = L1 , . . . , Ln L is a rule in P.
prems(A) = prems(A1 ) ∪ · · · ∪ prems(An )
rules(A) = rules(A1 ) ∪ · · · ∪ rules(An ) ∪ {r }
For both kinds of an argument A,
vuls(A) = prems(A) ∪ name(rules(A) ∩ D)
Example 2. Consider a defeasible logic program consisting of the only defeasi-
ble rule r : not b ⇒ a. Two default arguments A1 = [not a], A2 = [not b] and
one deductive argument A3 = [A2 ⇒ a] can be constructed. We can see that
vuls(A1 ) = {not a}, vuls(A2 ) = {not b}, vuls(A3 ) = {not b, not r }.
The difference between a default and a deductive argument for a literal not A
is in the policy of how the conflict is resolved. Syntactical conflict between ar-
guments is formalized in the following definition. As usual in the literature [14],
we distinguish two kinds of conflicts: undermining 3 and rebutting. While an un-
dermining conflict is about a falsification of a hypothesis (assumed by default),
a rebutting conflict identifies a situation where opposite claims are derived.
Definition 9 (Conflict). Let P be a defeasible logic program. The pair of ar-
guments C = (A, B ) is called a conflict iff
– A is a deductive argument for a default literal not L and B is a deductive
argument for the literal L; or
3
Also called undercutting in [15].
– A is a default argument for a default literal not L and B is a deductive
argument for the literal L.
The first kind is called a rebutting conflict and the second kind is called an
undermining conflict.
The previous definition just identifies the conflict, but does not say how to
resolve it; the notion of conflict resolution (to be formalized below) captures a
possible way to do so. In our paper, conflicts are not resolved through attack be-
tween arguments as in [8,15,14,11], but by attacking some of the vulnerabilities
in the conflicting arguments. Since our goal is to define semantics for DeLP re-
specting existing semantics and intuitions in LP, we assume that all undermining
conflicts are resolved in a fixed way as in LP: by attacking the default argument.
On the other hand, rebutting conflict is resolved by attacking some defeasible
rule. Since, in general, there can be more reasonable ways how to choose which
defeasible rules to attack, resolving of all rebutting conflicts is left as domain
dependent for the user as an input. Note, that an attack on a defeasible rule r
is formalized as an attack on the default literal name(r ) which is interpreted as
“a defeasible rule r can be used”.
Definition 10 (Conflict Resolution). Let P be a defeasible logic program. A
conflict resolution is a tuple ρ = (A, B , V ) where C = (A, B ) is a conflict, A is
an argument for not L, and V is a default literal
– not L if C is an undermining conflict; or
– name(r ) where r is a defeasible rule in rules(A)∪rules(B ) if C is a rebutting
conflict.
A conflict resolution strategy of P is a set R of conflict resolutions.
Let ρ = (A, B , V ) be a conflict resolution. The contrary of V is called the
resolution of ρ, and denoted by res(ρ). The set of vulnerabilities of ρ, denoted
by vuls(ρ), is defined as:
(vuls(A) ∪ vuls(B )) whenever V ∈ vuls(A) ∩ vuls(B )
vuls(ρ) =
(vuls(A) ∪ vuls(B )) \ {V } otherwise
Usually, there may be more ways how to resolve a conflict and a conflict
resolution may resolve other conflicts as well, thus causing other conflict resolu-
tions to be irrelevant or inapplicable. Intuitively, if all vulnerabilities in vuls(ρ)
are undefeated (i.e. true), then in order to resolve the conflict in ρ, the contrary
res(ρ) of the chosen vulnerability in ρ should be concluded (i.e. true). Notions
of vuls(ρ) and res(ρ) will be used for definition of the argumentation semantics
in the next subsection.
Example 3. Consider the defeasible logic program P = {not a → a} and under-
cutting arguments A = [not a] and B = [[not a] → a]. Then ρ = (A, B , not a)
is a conflict resolution with res(ρ) = a and vuls(ρ) = {not a}. Please note that
although not a has to be removed to resolve conflict between A and B , it remains
a vulnerability of ρ since not a is self-attacking.
Example 4. Consider the following defeasible logic program P
r1 : ⇒ a r2 : ⇒ b a → not c b→c
and arguments A = [[ ⇒ a] → not c] and B = [[ ⇒ b] → c]. The rebutting conflict
(A, B ) can be resolved in two different ways, namely ρ1 = (A, B , not r1 ) is a con-
flict resolution with res(ρ) = r1 and vuls(ρ) = {not r2 }, and ρ2 = (A, B , not r2 )
is another conflict resolution with res(ρ) = r2 and vuls(ρ) = {not r1 }.
The previous example shows that there are more reasonable ways how to
resolve rebutting conflicts. We show two examples of different conflict resolu-
tion strategies – the weakest-link and the last-link strategy inspired by ASPIC+
[14]. In both strategies, a user-specified preference order ≺ on defeasible rules is
assumed. In the last-link strategy, all last-used defeasible rules of conflicting ar-
guments are compared and ≺-minimal defeasible rules are chosen as resolutions
of the conflict. In the weakest-link strategy, each ≺-minimal defeasible rule of
conflicting arguments is a resolution of the conflict.
Example 5. Given the defeasible logic program
r1 : ⇒ b
r2 : b ⇒ a
r3 : ⇒ not a
and the preference order r1 ≺ r3 , r1 ≺ r2 , r2 ≺ r3 , deductive arguments are
A1 = [ ⇒ b] A2 = [A1 ⇒ a] A3 = [ ⇒ not a]
Then R1 = {(A3 , A2 , not r3 )} is the last-link strategy and R2 = {(A3 , A2 , not r1 )}
is the weakest-link strategy.
In the weakest-link strategy from Example 5, a non-last defeasible rule r1 is
used as a resolution of the conflict. Please note that in [15,8,14,11], such conflict
resolutions are not possible, which makes our approach more flexible and general.
3.2 Argumentation Semantics
In the previous subsection, definition of an argument structure, conflicts iden-
tification and examples of various conflict resolutions were discussed. However,
the status of literals and the actual semantics has not been stated.
Argumentation semantics for defeasible logic programs will be formalized
within ABF – a general framework, where several existing non-monotonic for-
malisms have been embedded [3]. In order to use some of the existing argumen-
tation semantics, we need to specify ABF’s language L, set of inference rules
R, set of assumptions A, and the contrariness function . Since ABF provides
only one kind of inference rules (i.e. strict), we need to transform defeasible rules
into strict. We transform defeasible rule r by adding a new assumption name(r )
into the preconditions of r . Furthermore, chosen conflict resolutions R determin-
ing how rebutting conflicts will be resolved are transformed into new inference
rules. Intuitively, given a conflict resolution ρ, if all assumptions in vuls(ρ) are
accepted, then, in order to resolve the conflict in ρ, the atom res(ρ) should be
concluded. To achieve this, an inference rule vuls(ρ) → res(ρ) for each conflict
resolution ρ ∈ R is added to the set of inference rules R.
Definition 11 (Instantiation). Let P = (S, D, name) be a defeasible logic
program built over the language LAt and R be a set of conflict resolutions. An
assumption based framework respective to P and R is (L, R, A, ) where
– L = LAt ∪ LN ,
– R = S ∪ {body(r ) ∪ {name(r )} → head (r ) | r ∈ D} ∪ {vuls(ρ) → res(ρ) | ρ ∈
R},
– A = not At ∪ not N ,
– not A = A for each atom A ∈ At ∪ N .
Example 6. Consider the defeasible logic program P and the conflict resolution
strategy R = {ρ1 , ρ2 } from Example 4. Assumption-based framework respective
to P and R is following:
– L = {a, not a, b, not b, c, not c} ∪ {r1 , not r1 , r2 , not r2 }
– R = {b → not c, a → c} ∪ {not r1 → b, not r2 → a} ∪ {not r1 → r2 , not r2 →
r1 }
– A = {not a, not b, not c} ∪ {not r1 , not r2 }
– not A = A for each A ∈ {a, b, c} ∪ {r1 , r2 }
Now we define the actual semantics for defeasible logic programs. Given an
ABF F = (L, R, A, ), by F + we denote its flattening – that is, F + is the ABF
(L, {r ∈ R | head (r ) ∈
/ A}, A, ).
Definition 12 (Extension). Let P = (S, D, name) be a defeasible logic pro-
gram, R be a set of conflict resolutions, and F = (L, R, A, ) an assumption-
based framework respective to P and R. A set of literals E ⊆ L is
1. a complete extension of P with respect to R iff E is a complete extension of
F + with Cn R (E ) ⊆ E and Cn R (E 0 ) ⊆ E 0 ;
2. a grounded extension of P with respect to R iff E is a subset-minimal com-
plete extension of P with respect to R;
3. a preferred extension of P with respect to R iff E is a subset-maximal com-
plete extension of P with respect to R;
4. a semi-stable extension of P with respect to R iff E is a complete extension
of P with respect to R with subset-minimal E 0 \ E ;
5. a stable extension of P with respect to R iff E is a complete extension of P
with respect to R and E 0 = E .
where E 0 = L \ not E .
Example 7. Consider the assumption-based framework from Example 6. Then
E1 = ∅, E2 = {not r1 , r2 , not a, b, not c}, and E3 = {r1 , not r2 , a, not b, c} are
complete extensions of P with respect to R. Furthermore, E1 is the grounded
extension and E2 , E3 are preferred, semi-stable and stable extensions of P with
respect to R.
3.3 Transformational Semantics
The argumentation semantics defined above allows us to deal with conflict-
ing rules and to identify the extensions of a DeLP, given a CRS, and hence
it constitutes a reference semantics. This semantics is comparable to existing
argumentation-based semantics for DeLP, and, as we show below, it satisfies
the expected desired properties of defeasible reasoning. In this section we in-
vestigate on the relation of the argumentation-based semantics and classical
logic programming. As we show, an equivalent semantics can be obtained by
transforming the DeLP and the given CRS into a classical logic program, and
computing the respective class of models.
In fact the transformation that is required is essentially the same which
we used to embed DeLPs with CRS into ABFs. The names of rules become
new literals in the language, intuitively if name(r ) becomes true it means that
the respective defeasible rule is defeated. By default name(r ) holds and so all
defeasible rules can be used unless the program proves otherwise. The conflict
resolution strategy R to be used is encoded by adding rules of the form vuls(ρ) →
res(ρ) for each conflict resolution ρ ∈ R, where the head of such rules is always
an atom and the body is a set of default literals.
Formally the transformation is defined as follows:
Definition 13 (Transformation). Let P = (S, D, name) be a defeasible logic
program and R be a set of conflict resolutions. Transformation of P with respect
to R into a generalized logic program, denoted as T (P, R), is defined as
T (P, R) = S ∪ {body(r ) ∪ {name(r )} → head (r ) | r ∈ D} ∪
{vuls(ρ) → res(ρ) | ρ ∈ R}
Thanks to the transformation, we can now compute the semantics of each
DeLP, relying on the semantics of generalized logic programs. Given a DeLP P
and the assumed CRS R, the extensions of P w.r.t. R corresponds to the respec-
tive class of models. Complete extensions correspond to partial stable models,
the grounded extension to the well-founded model, preferred extensions to max-
imal stable models, semi-stable extensions to least-undefined stable models, and
stable extensions to total stable models.
Proposition 2. Let P be a defeasible logic program and R be a set of conflict
resolutions. Then
1. E is a complete extension of P with respect to R iff E is a partial stable
model of T (P, R).
2. E is a grounded extension of P with respect to R iff E is a well-founded
model of T (P, R).
3. E is a preferred extension of P with respect to R iff E is a maximal partial
stable model of T (P, R).
4. E is a semi-stable extension of P with respect to R iff E is a least-undefined
stable model of T (P, R).
5. E is a stable extension of P with respect to R iff E is a total stable model of
T (P, R).
A remarkable special case happens when the input program P does not
contain defeasible rules, and hence it is a regular GLP. In such a case our
argumentation-based semantics exactly corresponds to the respective class of
models for the GLP. This shows complete backward compatibility of our seman-
tics with the underlying class of logic programs.
Proposition 3. Let S be a generalized logic program and P = (S, ∅, ∅) a defea-
sible logic program with the empty set of conflict resolutions. Then
1. E is a complete extension of P iff E is a partial stable model of S.
2. E is a grounded extension of P iff E is a well-founded model of S.
3. E is a preferred extension of P iff E is a maximal partial stable model of S.
4. E is a semi-stable extension of P iff E is a least-undefined partial stable
model of S.
5. E is a stable extension of P iff E is a total stable model of S.
4 Properties
In this section we will have a look on desired properties for defeasible reason-
ing, and show that our semantics satisfies these properties. The properties are
formulated in general, that is, they should be satisfied for any a defeasible logic
program P, any set of conflict resolutions R, and any extension E of P w.r.t. R.
The first two properties formulated below are well known, they were pro-
posed by Caminada and Amgoud [4]. The closure property originally requires
that nothing new can be derived from the extension using strict rules. We use
a slightly more general formulation, nothing should be derived using the conse-
quence operator Cn which applies all the strict rules and in addition also all the
defeasible rules which are not defeated according to R. The original property [4]
is a straightforward consequence of this.
Property 1 (Closure). Let R0 = S ∪ {body(r ) ∪ {name(r )} → head (r ) | r ∈ D}.
Then Cn R0 (E ) ⊆ E .
The consistency property [4] formally requires that all conflicts must be re-
solved in any extension.
Property 2 (Consistency). E is consistent.
In addition we propose two new desired properties which are concerned with
handling of the default assumptions. Reasoning with default assumptions is a
fixed part of the semantics of GLPs (and most other classes of logic programs),
and therefore in DeLPs it should be governed by similar principles. The first
property (dubbed positive defeat) requires that for each default literal not A,
this literal should be always defeated in any extension E such that there is a
conflict resolution ρ ∈ R whose assumptions are all upheld by E ; and, in such a
case the opposite literal A should be part of the extension E .
Property 3 (Positive Defeat). For each atom A ∈ LN , if there exists a conflict
resolution ρ ∈ R with res(ρ) = A and vuls(ρ) ⊆ E then A ∈ E .
The previous property handles all cases when there is an undefeated evidence
against not A and requires that A should hold. The next property (dubbed nega-
tive defeat) handles the opposite case. If there is no undefeated evidence against
not A, in terms of a conflict resolution ρ ∈ R whose assumptions are all upheld
by E , then not A should be part of the extension E .
Property 4 (Negative Defeat). For each default literal not A ∈ LN , if for each
conflict resolution ρ ∈ R with res(ρ) = A holds not vuls(ρ) ∩ E 6= ∅ then not A ∈
E.
Closure and consistency trivially hold for our semantics, as the semantics
was designed with these properties in mind. They are assured by the definition
of complete extension of a DeLP (Definition 12).
Proposition 4. Each complete extension E of a defeasible logic program P with
respect to a set of conflict resolutions R has the property of closure.
Proposition 5. Each complete extension E of a defeasible logic program P with
respect to a set of conflict resolutions R is consistent.
Satisfaction of a positive and a negative defeat properties follow from the
instantiation of an ABF (Definition 11), where an inference rule vuls(ρ) → res(ρ)
is added for every conflict resolution ρ ∈ R.
Proposition 6. Each complete extension E of a defeasible logic program P with
respect to a set of conflict resolutions R has the property of positive defeat.
Proposition 7. Each complete extension E of a defeasible logic program P with
respect to a set of conflict resolutions R has the property of negative defeat.
5 Related Work
There are two well-known argumentation-based formalisms with defeasible in-
ference rules – defeasible logic programs [8] and ASPIC+ [14,11]. It is known
that the semantics in [8] does not satisfy rationality postulates formalized in [4],
especially the closure property. Although ASPIC+ satisfies all postulates in [4],
it uses transposition or contraposition which violate directionality of inference
rules [2] and thus violating LP intuitions. It also does not satisfy positive or
negative defeat property introduced in this paper.
Francesca Toni’s paper [19] describes a mapping of defeasible reasoning into
assumption-based argumentation framework. The work takes into account the
properties [4] that we also consider (closedness and consistency), and it is for-
mally proven that the constructed assumption-based argumentation framework’s
semantics is closed and consistent. However no explicit connection with existing
LP semantics is discussed in [19].
The paper [20] does not deal with DeLP, but on how to encode defeasible
semantics inside logic programs. The main objective is on explicating a preference
ordering on defeasible rules inside a logic program, so that defeats (between
defeasible logic rules) are properly encoded in LP. This is achieved with a special
predicate defeated with special semantics.
Caminada et al. [6] investigated how abstract argumentation semantics and
semantics for normal logic programs are related. Authors found out that abstract
argumentation is about minimizing/maximizing argument labellings, whereas
logic programming is about minimizing/maximizing conclusion labellings. Fur-
ther, they proved that abstract argumentation semantics cannot capture the
least-undefined stable semantics for normal logic programs.
6 Conclusion
In this paper we investigated the question of how to define semantics for defeasi-
ble logic programs, which satisfies both the existing rationality postulates from
the area of structured argumentation and is also aligned with LP semantics and
intuitions. To achieve these objectives, we diverged from the usual argumentation
process methodology. Most importantly, conflicts are not resolved by attacking
some of the conflicting arguments, but by attacking some of the weak parts of
an argument called vulnerabilities. Main contributions are as follows:
– We presented an argumentation semantics of defeasible logic programs, based
on conflict resolution strategies within assumption-based frameworks, whose
semantics satisfies desired properties like consistency and closedness under
the set of strict rules.
– We constructed a transformational semantics, which takes a defeasible logic
program and a conflict resolution strategy as an input, and generates a cor-
responding generalized logic program. As a consequence, a computation of
argumentation semantics of DeLP in the frame of GLP is enabled.
– Equivalence of a transformational and an argumentation semantics is pro-
vided.
Acknowledgements
This work resulted from the Slovak–Greek bilateral project “Multi-context Rea-
soning in Heterogeneous environments”, registered on the Slovak side under no.
SK-GR-0070-11 with the APVV agency and co-financed by the Greek General
Secretariat of Science and Technology and the European Union. It was further
supported from the Slovak national VEGA project no. 1/1333/12. Martin Baláž
and Martin Homola are also supported from APVV project no. APVV-0513-10.
References
1. Alferes, J.J., Leite, J.A., Pereira, L.M., Przymusinska, H., Przymusinski, T.C.:
Dynamic logic programming. In: APPIA-GULP-PRODE 1998. pp. 393–408 (1998)
2. Baláž, M., Frtús, J., Homola, M.: Conflict resolution in structured argumentation.
In: LPAR-19 (Short Papers). EPiC, vol. 26, pp. 23–34. EasyChair (2014)
3. Bondarenko, A., Dung, P.M., Kowalski, R.A., Toni, F.: An abstract, argumentation
theoretic approach to default reasoning. Artif. Intell. 93(1-2), 63–101 (1997)
4. Caminada, M., Amgoud, L.: On the evaluation of argumentation formalisms. Artif.
Intell. 171(5-6), 286–310 (2007)
5. Caminada, M., Carnielli, W.A., Dunne, P.E.: Semi-stable semantics. J. Log. Com-
put. 22(5), 1207–1254 (2011)
6. Caminada, M., Sá, S., Alcântara, J.: On the equivalence between logic program-
ming semantics and argumentation semantics. In: ECSQARU 2014 (2013)
7. Dung, P.M.: On the acceptability of arguments and its fundamental role in non-
monotonic reasoning, logic programming and n-person games. Artif. Intell. 77,
321–357 (1995)
8. García, A.J., Simari, G.R.: Defeasible logic programming: an argumentative ap-
proach. TPLP 4(2), 95–138 (2004)
9. Gelder, A.V., Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic
programs. J. ACM 38(3), 619–649 (1991)
10. Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In:
ICLP/SLP. pp. 1070–1080. MIT Press (1988)
11. Modgil, S., Prakken, H.: Revisiting preferences and argumentation. In: IJCAI 2001.
pp. 1021–1026. AAAI Press (2011)
12. Nute, D.: Defeasible reasoning and decision support systems. Decision Support
Systems 4(1), 97–110 (1988)
13. Pollock, J.L.: Defeasible reasoning. Cognitive Science 11(4), 481–518 (1987)
14. Prakken, H.: An abstract framework for argumentation with structured arguments.
Argument & Computation 1(2), 93–124 (2010)
15. Prakken, H., Sartor, G.: Argument-based extended logic programming with defea-
sible priorities. Journal of Applied Nonclassical Logics 7(1), 25–75 (1997)
16. Prakken, H., Vreeswijk, G.: Logics for defeasible argumentation. In: Gabbay, D.,
Guenthner, F. (eds.) Handbook of Philosophical Logic, pp. 219–318. Springer
(2002)
17. Przymusinski, T.C.: The well-founded semantics coincides with the three-valued
stable semantics. Fundam. Inform. 13(4), 445–463 (1990)
18. Saccà, D.: The expressive powers of stable models for bound and unbound DATA-
LOG queries. J. Comput. Syst. Sci. 54(3), 441–464 (Jun 1997)
19. Toni, F.: Assumption-based argumentation for closed and consistent defeasible
reasoning. In: JSAI 2007. LNCS, vol. 4914, pp. 390–402. Springer (2008)
20. Wan, H., Grosof, B., Kifer, M., Fodor, P., Liang, S.: Logic programming with
defaults and argumentation theories. In: ICLP 2009. LNCS, vol. 5649, pp. 432–
448. Springer (2009)