There are a wide variety of formalisms for defeasible reasoning that can be seen as implementing concrete argumentation on defeasible rules. However there has been little work on the relationship between such languages and Dung's abstract argumentation. In this paper we identify two small fragments on which many concrete defeasible formalisms agree. The two fragments are closely related, as we show. The fragments arise as ways to express abstract argumentation frameworks in the concrete formalisms. Our results enable us to transfer complexity lower bounds from abstract argumentation to concrete formalisms.
Argumentation and defeasible reasoning are essentially different names for the same thing:
resolving conflicting chains of reasoning in a principled way. In modern times,
argumentation has been structured through Dung’s introduction of abstract argumentation
An advantage of abstract argumentation is that it abstracts away details of an argument’s construction and how conflicting arguments are resolved. As a consequence, results proved on abstract argumentation have the potential to be applicable to a number of concrete instances. On the other hand, this advantage is largely moot for concrete defeasible reasoning systems that are not developed within the abstract argumentation discipline. The problem is that the relationship between abstract argumentation and the individual concrete systems is unclear.
Indeed, there is relatively little work relating abstract argumentation to such concrete
defeasible reasoning formalisms, despite the fact that there are clear commonalities.
In this paper we exploit the common logic programming underpinnings of abstract argumentation and a concrete framework for defeasible reasoning to identify a relationship between the two. We extend this relationship to a wide variety of other concrete defeasible reasoning systems. We demonstrate the usefulness of these results by showing how complexity results for abstract argumentation frameworks can be transferred to concrete systems.
The paper is structured as follows. The next section provides brief background on abstract argumentation, formalisms for defeasible reasoning, and semantics of logic programs. The following section introduces a small fragment of defeasible languages that is capable of expressing abstract argumentation frameworks, and investigates its properties. It is shown that the arguments constructed from this fragment in the ASPIC-style are isomorphic to an abstract argumentation framework. It is also shown that the fragment represents a common core of defeasible reasoning in the sense that a wide range of formalisms for defeasible reasoning agree on the conclusions that should be drawn from such fragments.
The next section establishes general relationships between abstract argumentation
frameworks under completist semantics1 and the fragment in logics in the framework DL. It
follows a similar pattern to results in
Then a second small fragment is introduced and shown to be equivalent to the first fragment. Nevertheless, the second fragment is able to be expressed in languages that cannot express the first fragment. It is used to show that several concrete formalisms are able to express the stable semantics of abstract argumentation formalisms.
Finally, there is a brief discussion of the use of these results to transfer complexity results about abstract argumentation to the concrete formalisms. The paper concludes with a summary and brief discussion of future work.
This work involves abstract argumentation in the sense of
Given an argumentation framework, an argument a is said to be accepted in an extension E if a 2 E, and said to be rejected in E if some b 2 E attacks a. The set of arguments rejected in E will be denoted E . An argument that is neither accepted nor rejected in E is said to be undecided in E. An extension E is conflict-free if the restriction of to E is empty. An argument a is defended by E if every argument that attacks a is attacked by some argument in E. An extension E of A is complete if it is conflict free and, a 2 E iff a is defended by E. The smallest complete extension exists and is called the grounded extension. The maximal (under the set containment ordering) complete extensions are called the 1 Completist semantics are semantics defined in terms of complete extensions. preferred extensions. An extension E of A is stable if it is complete and for every argument a 2 SnE there is an argument in E that attacks a. An extension E of A is semi-stable if it is a complete extension such that E [ E is maximal wrt set containment (or, equivalently, the set of undecided arguments is minimal).
Each extension can be considered a potential outcome of evaluating an argumentation framework: classifying arguments as accepted, rejected or undecided. Each class of extensions (complete, preferred, . . . ) expresses a criterion for an extension to be a “reasonable” outcome; thus each class expresses a semantics of an argumentation framework: the set of reasonable extensions. From these extensions, conclusions about individual arguments can be drawn. Each of these semantics consist only of complete extensions; we call such semantics completist.
There are several logical systems that provide for the construction of arguments, which
can then be evaluated according to one of the semantics of abstract argumentation. They
include the structured argumentation systems ASPIC
However, there are numerous systems for defeasible reasoning that provide concrete
mechanisms for drawing conclusions from defeasible rules, without formulating the
problem as the construction and then evaluation of arguments. Among such systems are:
various systems for non-monotonic inheritance
Common to most of these systems is the expression of defeasible rules and priorities among such rules. Syntax varies in these systems, but we will use ) uniformly to express defeasible rules. In general these systems support a variety of additional features such as strict rules, defeaters, conflict sets, mutex, . . . . Furthermore, many systems admit several variants that treat the interaction of conflicting rules and priorities differently.
Some of these systems draw only positive conclusions, but the defeasible logics draw both positive and negative conclusions. For example, in the defeasible logic DL(@ ) we may derive +@ q, meaning that q can be proved, or derive @ q, meaning that it can be established within the proof system that q cannot be proved. Of course, it is also possible that neither conclusion can be drawn.
The framework of
Many of the systems identified above can be seen as based on a semantics for negation
in logic programs, even though their original formulation was not in those terms. In
particular, logics in the DL framework were explicitly shown to employ Kunen’s semantics
The logic programming semantics we will focus on can be seen to be derived from
the 3-valued stable models
We begin by addressing the representation of abstract argumentation frameworks in concrete defeasible reasoning systems. Such systems may have many features, with complex interactions, but only a small fragment of these formalisms is needed to mimic the behaviour of an abstract argumentation framework.
For any abstract argument framework A, the corresponding set of canonical defeasible rules CDR(A) is defined as follows:
For each argument A, there is a proposition pA, and a defeasible rule rA0: For each argument A, attacked by arguments B1; : : : ; Bn, there is the corresponding defeasible rule rA: :pB1 ; : : : ; :pBn ) Finally, we must express that each rule for :pA is overruled by (or has lower priority than) the rule for pA whenever the latter is applicable. Different concrete systems may express pA ) :pA this requirement in different ways, but most commonly it is expressed directly as a relation on rules.
A set of defeasible rules that has the form CDR(A), for some A, is canonical. Canonical
defeasible rules are a defeasible rule counterpart of the logic programs defined by
The class of canonical defeasible rules is very simple, involving only defeasible rules and a priority relation on these rules. More complex features that concrete systems might support, such as strict rules, defeaters, conflict sets, mutex, etc. are not present. Hence, a quite wide range of formalisms are able to express canonical defeasible rules.
We first show that a concrete argumentation system applied to arguments constructed from CDR(A) in the ASPIC style comes to the same conclusions as the abstract system.
Define the arguments in the concrete argumentation system to be proof trees constructed from the rules for the propositions pA and :pA, for all arguments A. Hence, the proof trees for pA are trees with root labelled pA and n children labelled :pB1 ; : : : ; :pBn respectively, and proof trees for :pA consist of a single node labelled by :pA. Thus arguments have height of at most 1. The attack relation is defined as follows: the argument for pA is attacked by the argument for pB iff the argument for :pB is a subargument of the argument for pA. Such an attack relation arises in any concrete argumentation system that employs undercutting (sometimes called undermining) attacks and can express that each argument for pA has priority over the argument for :pA. If we ignore the arguments for :pA, which in any case do not attack any other argument, the concrete argument system is isomorphic to the abstract argumentation framework from which it was derived.
Let A be an abstract argumentation framework and consider CDR(A). The concrete argument system derived from CDR(A), restricted to arguments for propositions pA, is isomorphic to A.
As a result, for every common argumentation semantics, A and the argumentation framework derived from CDR(A) derive the same conclusions. This result assures us that the canonical defeasible rules accurately represent the argumentation framework.
Among the formalisms that can represent canonical defeasible rules are: the defeasible logics NDL and ADL, the defeasible logics in the DL framework, the extended defeasible logics of Billington, courteous logic programs and its more recent incarnations LDPA, ASPDA and Rulelog, Ordered Logic and LPwNF. Similarly, structured argumentation systems in the ASPIC style and assumption-based argumentation can express canonical defeasible rules.
Furthermore, many of these concrete systems infer the same consequences from canonical defeasible rules. Thus canonical defeasible rules form a core on which these defeasible reasoning systems agree.
The positive conclusions drawn from a set of canonical defeasible rules are the same, whether the rules are interpreted in any of the following formalisms: the defeasible logics NDL and ADL, the logics in the frameworks DL and W F DL, Billington’s defeasible logics, and the formalisms Ordered Logic, LPwNF, courteous logic programs and LPDA2.
Furthermore, for those formalisms that support negative conclusions, the negative conclusions drawn from a set of canonical defeasible rules are also the same.
This result is a consequence of the particularly simple form of canonical defeasible rules: there is one rule for :pA and at most one rule for pA, which has the higher priority. Consequently, the many variations in how conflicting rules and priorities interact converge on the same behaviour.
There are some defeasible reasoning systems that seem unable to represent canonical
defeasible rules. Traditional non-monotonic inheritance systems are unable to express rules
with multiple body atoms and rules with negative literals in the body. Logics where
priorities cannot be given independently have an obvious problem. Such logics include a
defeasible logic in
In
Here sup(R; S) expresses that the rule R is superior to (i.e. has priority over) the rule
S, rule(R; X; [Y1; : : : ; Yn]) represents a defeasible rule called R with head X and body
Y1; : : : ; Yn, and expresses negation in the object language. defeasibly(X) expresses
2 We assume that the LPDA theory has the overriding property
Using this meta-program, we can establish the relationship between an abstract argumentation framework and ambiguity blocking logics in the DL framework.
Let M be the meta-program for DL(@ ; ) or DL(@; ). Let A be an abstract argumentation framework. Then there is an isomorphism between complete extensions of A and partial stable models of M (CDR(A)) grounded extension of A and well-founded model of M (CDR(A)) stable extensions of A and stable models of M (CDR(A)) preferred extensions of A and regular models of M (CDR(A)) semi-stable extensions of A and L-stable models of M (CDR(A)) where we restrict the models to defeasibly atoms.
In particular, the conclusions derivable from A under a semantics S are the same as those derived in the logic DL(@ ; S0) from CDR(A), where S0 is the semantics in the above theorem corresponding to S.
This result is the counterpart, for defeasible rules in the DL framework, of Table 5 of
Using the above theorem and Proposition 2, we can extend Theorem 3 to argumentationbased formalisms under the grounded semantics.
Let A be an abstract argumentation framework. Then an argument A is accepted in the grounded extension of A iff the argument for pA is accepted under the grounded semantics of CDR(A) by ABA or any of the ASPIC variants iff pA is a positive conclusion from CDR(A) in any of the formalisms mentioned in Theorem 3.
Similarly, A is rejected in the grounded extension of A iff the argument for pA is rejected under the grounded semantics of CDR(A) by ABA or any of the ASPIC variants iff pA is a negative conclusion from CDR(A) in any of the formalisms mentioned in Theorem 3 that draw negative conclusions.
Thus we see that not only can the grounded semantics can be represented by defeasible formalisms based around the well-founded semantics, it can also be represented by those based on the Fitting/Kunen semantics.
Although the canonical defeasible rules fragment provides a common core for many defeasible languages, there are some languages that cannot express it, while others require significant distortions to represent it (for example, DEFLOG). This motivates the investigation of a different fragment that can represent abstract argumentation frameworks.
An alternative representation of an abstract argumentation framework is as follows.
For any argument framework A, the corresponding set of alternative canonical defeasible rules ACDR(A) is defined as follows: For each argument A, there is a proposition pA and a rule rA:
For each attack by argument B on argument A, there is the corresponding defeasible rule rBA:
) pA pB
) :pA Finally, we must express that each rule for :pA overrules (or has higher priority than) the rule for pA whenever the former is applicable. Different concrete systems may express this requirement in different ways.
This definition is similar to the mapping of argumentation frameworks to logic programs
by
Again we can construct ASPIC-style arguments from these rules: an argument for pA consists of the rule rA, while there may be several arguments for :pA, each consisting of rB and rBA. Every argument for :pA attacks the argument for pA.
However, the constructed arguments are not isomorphic to A.
Consider an abstract argumentation framework A consisting of arguments A, B, and C, where A attacks both B and C. The arguments constructed from ACDR(A) are arguments for each of the literals pA, pB, pC , :pB and :pC . Then the argument for :pB attacks the argument for pB, and similarly for C, but the argument for pA is not involved in an attack. Furthermore, there is no single argument that attacks both pB and pC , the way A attacks both B and C in A. Hence the constructed arguments are not isomorphic to A.
Nevertheless, the alternative canonical defeasible rules do characterize the conclusions of an argumentation framework under the semantics we consider, as we now establish. First, we need two lemmas.
Consider the transformation of logic programs which replaces a rule
A :- not B1; : : : ; notBn: by the rules
A :- not C: C :- B1:
: : :
C :- Bn: where C is a new symbol. Let P be the original program and P 0 be the transformed program. Then P and P 0 have the same partial stable models, ignoring C.
Applying the above transformation and other transformations to M (CDR(A)), we can obtain M (ACDR(A)) (up to renaming of introduced symbols), where M is a metaprogram for an ambiguity blocking logic in DL. Thus
Let M be the meta-program for an ambiguity blocking logic in the DL framework. M (CDR(A)) and M (ACDR(A)) have the same partial stable models, when restricted to literals involving defeasibly.
Consequently, Theorem 4 also applies to the alternate canonical defeasible rules.
Let M be a meta-program for an ambiguity blocking logic in the DL framework. Let A be an abstract argumentation framework. Then there is an isomorphism between complete extensions of A and partial stable models of M (ACDR(A)) grounded extension of A and well-founded model of M (ACDR(A)) stable extensions of A and stable models of M (ACDR(A)) preferred extensions of A and regular models of M (ACDR(A)) semi-stable extensions of A and L-stable models of M (ACDR(A)) where we restrict the models to defeasibly atoms.
Similarly, we can obtain a counterpart of Theorem 3 for ACDR.
Furthermore, we can establish a similar result for the stable semantics. Relatively few
concrete defeasible languages support the stable semantics, although the DL framework
supported this semantics and recently further proposals have been made
Let M be a meta-program for an ambiguity blocking logic in the DL framework. Let A be an abstract argumentation framework. Then there are isomorphisms between stable extensions of A dialectical interpretations of ACDR(A) in DEFLOG stable models of M (ACDR(A)) restricted to defeasibly atoms stable models of M (CDR(A)) restricted to defeasibly atoms stable models of CDR(A) in ASPDA stable models of ACDR(A) in ASPDA -stable sets of CDR(A) -stable sets of ACDR(A) where we assume that the ASPDA theory has the overriding property.
The proof uses results of
Theorem 4 and the results in this section apply only to the ambiguity blocking logics in DL; they do not extend to the ambiguity propagating logics. The following example demonstrates the situation.
Consider an argumentation framework A with two arguments, A and B, where A attacks B and B attacks A. Under the stable semantics there are two stable extensions: one in which A is accepted and B is rejected, and one in which B is accepted and A is rejected.
The canonical defeasible rules corresponding to A are
) :pB )
) :pA ) After substantial simplification, the application of the meta-program for DL( ; ) – an ambiguity propagating logic – results in the following rules, among others: :pA
pA :pB
pB defeasibly(pA) : defeasibly(pB) : support(pA) : support(pB) : not support(pB) not support(pA) not defeasibly(pB) not defeasibly(pA) These rules admit a stable model containing fdefeasibly(pA); defeasibly(pB)g. Consequently, the stable models of M (CDR(A)) are not isomorphic to the stable extensions of A.
For comparison, the corresponding logic program for DL(@ ; ) contains defeasibly(pA) : defeasibly(pB) : not defeasibly(pB) not defeasibly(pA) which has the two stable models corresponding the stable extensions of A.
The isomorphism fails because, in the meta-program for ambiguity propagating logics in DL, two mutually recursive predicates – defeasibly and support – are used, rather than a single predicate. As a result, there is no dependency relation between defeasibly(pA) and defeasibly(pB) corresponding to the attack relation between A and B. The results in this paper allow us to transfer complexity lower bounds for problems on abstract argumentation frameworks to the corresponding concrete formalisms.
For example, consider the problem of adding additional arguments to an argumentation
framework (called expansion by
In general, concrete systems have extra features – beyond defeasible rules and priorities – that can add extra complexity to inference in those systems. Consequently, tight complexity lower bounds at the abstract level do not necessarily imply tight bounds for a concrete system.
We have identified two complementary fragments of defeasible rule systems that are each capable of representing abstract argumentation frameworks. We showed that canonical defeasible rules represent a core of defeasible reasoning in that a wide variety of concrete formalisms agree on the meaning of this fragment. In doing so, we demonstrated that the majority of concrete formalisms for defeasible reasoning reflect the grounded semantics of argumentation.
We showed that several completist semantics for abstract argumentation are represented in the DL framework under various corresponding logic programming semantics. Several concrete formalisms, including DL(@ ) under the stable model semantics, were shown to reflect the stable semantics of argumentation.
Some formalisms, notably non-monotonic inheritance, have no obvious way to represent abstract argumentation frameworks. Despite the introduction of the second fragment, which is more amenable to the syntactic restrictions of these formalisms, there is no direct way to represent priorities. Some semantics of inheritance might permit the encoding of priorities so it would be interesting, for completeness, to understand the status of the different semantics of non-monotonic inheritance.
Theorem 3 and Corollary 5 apply to both ambiguity blocking and ambiguity propagating
formalisms. However, Theorems 4 and 10 apply only to the ambiguity blocking logics in
the DL framework. These results do not extend to the ambiguity propagating logics in the
framework, but this appears to be a consequence of how they are represented in the DL
framework, rather than a reflection of ambiguity propagation. Similarly, the formalisms in
Theorem 11 are ambiguity blocking. It will be interesting to see whether the -stable sets
(the extension of ADL, an ambiguity propagating logic)
It seems likely that semantics of logic programs can be designed to correspond to other
completist argumentation semantics, such as the ideal
An abstract, and