You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Rationality and maximal consistent sets for a fragment of ASPIC+ without undercut

Abstract

Structured argumentation formalisms, such as ASPIC+, offer a formal model of defeasible reasoning. Usually such formalisms are highly parametrized and modular in order to provide a unifying framework in which different forms of reasoning can be expressed. This generality comes at the price that, in their most general form, formalisms such as ASPIC+ do not satisfy important rationality postulates, such as non-interference. Similarly, links to other forms of knowledge representation, such as reasoning with maximal consistent sets of rules, are insufficiently studied for ASPIC+ although such links have been established for other, less complex forms of structured argumentation where defeasible rules are absent.

Clearly, for a formal model of defeasible reasoning it is important to understand for which range of parameters the formalism (a) displays a behavior that adheres to common standards of consistency, logical closure and logical relevance and (b) can be adequately described in terms of other well-known forms of knowledge representation.

In this paper we answer this question positively for a fragment of ASPIC+ without the attack form undercut by showing that it satisfies all standard rationality postulates of structured argumentation under stable and preferred semantics and is adequate for reasoning with maximal consistent sets of defeasible rules. The study is general in that we do not impose any other requirements on the strict rules than to be contrapositable and propositional and in that we also consider priorities among defeasible rules, as long as they are ordered by a total preorder and lifted by weakest link. In this way we generalize previous similar results for other structured argumentation frameworks and so shed further light on the close relations between assumption-based argumentation and ASPIC+.

1.Introduction

Structured argumentation is a family of formal approaches for the handling of defeasible and potentially inconsistent information. For this, many models of structured argumentation distinguish between strict and defeasible inference rules. Defeasible rules guarantee the truth of their conclusion only provisionally: from the antecedents of the rules we can infer their conclusion unless and until we encounter convincing counter-arguments. These defeasible rules can come in varying strengths. For example, in an epistemic reasoning context considerations of plausibility, typicality or likelihood may play a role in determining the strength of a defeasible conditional. In contexts of normative reasoning (such as legal or moral reasoning), the strength of defeasible conditionals may be determined by deontic or legal urgency (e.g., in view of the authority which issued them or their specificity). Strict rules, in contrast, are beyond doubt and therefore considered maximally strong: the truth of the antecedents is carried over to the conclusion.

Arguments constructed on the basis of a combination of strict and defeasible rules can be in conflict with one another. For example, one argument may conclude the contrary of the conclusion of another argument or may conclude that the application of a defeasible rule in another argument is not warranted in the circumstances under consideration. To represent and resolve such conflicts, a formal argumentation framework is constructed on the basis of the strict and defeasible rules. Argumentative attacks represent conflicts between arguments. Preferences over the defeasible rules used in constructing the arguments can be used to resolve conflicts between assumptions by turning attacks into defeats. There are several design choices available when specifying how to construct such an argumentation framework, which often have a severe impact on the inferential behaviour of the resulting formalism. In this paper, we study one specific formalism known as ASPIC+. ASPIC+ is a well-established formalism which has been applied to e.g. decision-making [52], risk-assessment [55] and legal reasoning [54] and provides argumentative characterisations of prioritised default logic [16] (cf. [59,60]) and preferred subtheories [15] (cf. [50]).

Example 1.

Nicki and Mary will go to a garden party (g) and were asked to bring a potato-salad.1 In Nicki’s opinion a good potato-salad has pickles in it (g1p) but Mary has an allergy to pickles (g2¬p). Since an allergy for pickles has precedence over a preference in taste, the rule based on the former is stronger than the rule based on the latter (which we express in the formal language by having a subscript 2 for g2¬p and a subscript 1 for g1p). Mary thinks they should bring a bottle of Quadruple beer as a gift for the host (l1q) since the host likes beers (l). Since this is a very strong beer, in most cases, when handing over the gift, a warning should be issued (q1w). However, the host is a beer connoisseur (b), and thus the previous rule of thumb does not apply (b1¬n(q1w)).

In [1 ,19] several rationality postulates have been proposed, which can be seen as minimal requirements any well-behaved structured argumentation formalism should fulfill. These requirements all have to do with the basic role of formal argumentation as a formalism for handling (logical) conflicts. For instance, we can require that the output of the formalism is logically consistent: it should not be possible to derive both a formula and its contrary. As an illustration, in Example 1 no structured argumentation formalism should output both that pickles should be added (p) and kept out (¬p) of the salad. In [53], it was proven that ASPIC+ satisfies the rationality postulates of closure and consistency given some basic restrictions on the strict rule base.

However, as has been observed in [57], ASPIC+ does not satisfy other standards such as Crash-Resistance and Non-Interference. Ideally, a reasoning system should not lose consequences if irrelevant information is added to the knowledge base. In Example 1, the fact that Mary and Nicki bring a beer (q) and warn the party host about the strength of the beer (w) should not be influenced by any considerations of what to put in the potato-salad (i.e. by adding {g1p,g2¬p} to the knowledge base). As demonstrated in [57] for ASPIC+, the lack of Crash-Resistance and Non-Interference is especially threatening if the underlying strict rules are domain-independent. This is typically the case if the strict rules are induced by an underlying logic such as classical logic (in short, CL).2 Given an inconsistent knowledge base and strict rules such as logical explosion, for any formula an argument with a contrary conclusion can be constructed.

So far, there are not many results that establish Crash-Resistance and Non-Interference for ASPIC+ and related systems.3 Some examples are:

  • [57] established non-interference for complete semantics for ASPIC-lite, a sub-system of ASPIC+ where priorities over defeasible rules are not taken into account and inconsistent arguments are filtered out. The latter is arguably a limitation, since checking consistency can be computationally unfeasible and since the inconsistency is typically demonstrated dialectically in real-word argumentation [27].

  • In [36] a system with restricted rebut is introduced that avoids logical explosion by using a sub-classical logic as a base logic. For any completeness-based semantics a weakened version of Non-Interference and Closure are shown for total pre-orders expressing priority relations between the defeasible rules. For multi-extension semantics a counter-example for full non-interference is provided.

  • Recently ASPIC [11,39,41] has been proposed. It is the first member of the ASPIC-family that satisfies all standard rationality postulates (including non-interference and crash-resistance) even when taking into account preorders over defeasible rules. ASPIC does not require filtering out inconsistent arguments. However, the rationality postulates hold only for the single-state grounded semantics, as it makes use of the attack form of unrestricted rebut, which violates the rationality postulates of closure and indirect consistency for multi-extension semantics such as the preferred and stable semantics (see e.g. [18, Example 2]).

In conclusion, there have been some recent steps towards rational, prioritised structured argumentation with defeasible rules, but it is still an open question whether it is possible to obtain a formalism that satisfies the four rationality postulates for a multi-state semantics and prioritised defeasible rules. In this paper, we show that this is possible given some basic restrictions on the language of the knowledge base, using the weakest link lifting for a fragment of ASPIC+. In more detail, we consider ASPIC+ without undercut, defeasible premises and undermining attacks and we assume the preference order over the defeasible rules to be total. We restrict our attention to propositional instantiations. As such, this paper presents an important move towards a full solution to an open problem mentioned both in [51] and [18]. Furthermore, when these restrictions are met, it is not necessary to filter out inconsistent arguments, thus bringing the formalism closer to dialectical practices.

Moreover, we demonstrate that when these resctrictions are met, the stable and the preferred semantics coincide. This result is interesting from a computational perspective, since it means we can now use the computationally less demanding proof theories for admissible semantics to show membership of a stable extension [31].

For several systems of structured argumentation characterizations of the extensions of frameworks under some argumentation semantics in terms of maximal consistent sets of premises have been obtained (see [6] for an overview). Such results are useful since they provide a link between argumentation and knowledge representation and they provide a basic sanity check on the behavior of an argumentation system. For systems with defeasible rules, such as ASPIC+, such results have not been obtained. One difficulty is the question of how to define consistent subsets of the premises in such contexts. In this contribution we will generalize approaches that have been proposed in the context of knowledge bases with strict and defeasible assumptions such as default assumptions [47] and ABA [12] to systems with defeasible inference rules such as ASPIC+. In this way we obtain further insights into the relation of ASPIC+ to other argumentation formalisms, thus tackling another open question formulated in [51].

Outline of this paper: In Section 2, we present the necessary preliminaries on the structured argumentation formalism ASPIC+. In Section 3 we review the rationality postulates for structured argumentation. Expert readers in formal argumentation may skip these sections and jump directly to Section 4, which contains the main contributions of this paper, namely: when considering (a fragment of) ASPIC+ without undercut attacks, stable and preferred extensions coincide (Section 4.1), all four rationality postulates are satisfied for the stable and preferred semantics (Section 4.2) and central argumentation semantics are characterized in terms of maximally consistent sets of defeasible rules (Section 4.3). In Section 5 we discuss related work. In the final Section 6 we make some concluding remarks, pointing out a connection with assumption-based argumentation and setting out avenues for further work.

2.Structured argumentation

In structured argumentation, information is given in the form of a knowledge base or argumentation system. In ASPIC+, such an argumentation system is built up from a formal language L, which can be used to formulate strict rules S of the form ϕ1,,ϕnϕ, defeasible rules D of the form ϕ1,,ϕnϕ and strict premises K. Strict rules are deductive in the sense that the truth of their antecedents ϕ1,,ϕn necessarily implies the truth of their consequent ϕ, while defeasible rules allow for exceptions. In ASPIC+ arguments are modelled as derivations based on strict and defeasible rules and a set of premises.

Strict rules can have several classes of interesting instantiations. A first option is to use some logic L with an associated consequence relation L and require that ϕ1,,ϕnϕS iff {ϕ1,,ϕn}LA. Another option is to use what are often called domain dependent rules, as they are known from e.g. logic programming.

Unlike strict rules, a defeasible rule warrants the truth of its conclusion only provisionally: its application can be retracted in case counter-arguments are encountered. We assume that the defeasible rules D come with a naming function n:DL. Furthermore, conflicts between elements of the language can be specified using a contrariness function ϕ.4 Finally, the user can specify preferences over the defeasible rules using a preorder D×D. Formally, such an argumentation system is defined as follows:

Definition 1

Definition 1(Argumentation System).

An Argumentation System (AS) is a tuple (L,S,D,K,n,A,) consisting of:

  • (1) a formal language L based on a set of atoms A;

  • (2) a set of strict rules S of the form ϕ1,,ϕnϕ (where ϕ1,,ϕn,ϕL);

  • (3) a set of defeasible rules D of the form ϕ1,,ϕnϕ (where ϕ1,,ϕn,ϕL);

  • (4) an S-consistent5 set of strict premises KL;

  • (5) a naming function for the defeasible rules n:DL;

  • (6) a contrariness function A from L to 2L;

  • (7) a total preorder6 ⩽ over D.

Given a rule r=ϕ1,,ϕnϕ resp. r=ϕ1,,ϕnϕ, ϕ1,,ϕn are called the antecedents and ϕ is called the consequent or head. We write body(r)={ϕ1,,ϕn} and head(r)=ϕ. Where R is a set of rules we write body[R] for the set {body(r)rR} and head[R] for the set {head(r)rR}.

The naming function n will be important when considering the attack form undercut and the preorder ⩽ is important when considering different strengths of arguments (see Definition 4). Below we will sometimes consider argumentation systems without undercut and/or without priorities, in which case we omit n and/or ⩽ from the characterizing tuple.7

Example 2

Example 2(Example 1 continued).

To illustrate the above definitions, we illustrate how to capture the information from Example 1 in an argumentation system AS2=(L2,SCL,D2,K2,n2,A,2) where:8

  • L2 is the closure of the set of atoms {g,p,q,l,w,b,α,β,γ,δ,ϵ} and the constants ⊥ and ⊤ under {¬,,};

  • SCL is the set of strict rules capturing classical logic CL as follows: ϕ1,,ϕnϕSCL iff {ϕ1,,ϕn}CLϕ and ϕ,ϕ1,,ϕnL2;9

  • D2={g1p;g2¬p;l1q;q1w;b1¬δ};

  • K2={g,b,l};

  • n2(g1p)=α, n2(g2¬p)=β, n2(l1q)=γ, n2(q1w)=δ, n2(b1¬δ)=ϵ.

  • ϕψ iff ϕ=¬ψ or ψ=¬ϕ or ϕ=;10

  • ϕiψ2ϕjψ iff ij (where ⩽ is the canonical order over N).

2.1.Argument construction

In structured argumentation systems like ASPIC+, acceptable arguments are determined using the semantics of abstract argumentation. In order to apply these semantics, an argumentation graph has to be constructed on the basis of the argumentation system. This is done by building arguments using premises and inference rules and by specifying defeats between these arguments on the basis of the contrariness function and the preference order of the argumentation system. We first define how arguments are constructed.11

Definition 2.

Let AS=(L,S,D,K,n,A,) be an argumentation system. An argument a is one of the following:

  • (1) a=ϕ where ϕK

    Conc(a)=ϕ, Sub(a)={a}, D(a)=;12

  • (2) a=a1,,anϕ where a1,,an (with n0) are arguments such that there is a strict rule Conc(a1),,Conc(an)ϕS

    Conc(a)=ϕ, Sub(a)={a}i=1nSub(ai), and D(a)=i=1nD(ai);

  • (3) a=a1,,anϕ where a1,,an (with n0) are arguments such that there is a defeasible rule Conc(a1),,Conc(an)ϕD

    Conc(a)=ϕ, Sub(a)={a}i=1nSub(ai), and

    D(a)={Conc(a1),,Conc(an)ϕ}i=1nD(ai).

We lift the above notation as expected. E.g., where A is a set of arguments, Conc[A]={Conc(a)aA} and D[A]={D(a)aA}.

By Arg(AS) we denote the set of arguments that can be built from AS. An argument a will be called defeasible if D(a) and strict otherwise.

Example 3

Example 3(Example 2 continued).

The following arguments (among others) can be constructed from AS2:

a1:ga1:la2:a11pa3:a12¬pa4:a11qa5:a41wa6:ba7:a61¬δa8:a2,a3a9:a4,a5qw
a1, a1, and a6 are premise arguments. a2 is obtained by applying the defeasible rule g1p to the argument a1. a3, a4 and a7 are obtained in a similar way. a5 is obtained by applying the rule q1w to the defeasible rule argument a4 and thus is an example of how defeasible rules can be chained. a8 and a9 are two examples of the application of a strict rule: ex falso quodlibet in the case of a8 and conjunction introduction in the case of a9.

2.2.Attack and defeat

In ASPIC+ there are two ways in which arguments can conflict. The first type of attack, called rebut, is when an argument a concludes the contrary of the conclusion of an argument b. The second attack type is called undercut and occurs when an argument concludes that the application of a defeasible rule is not appropriate in the context at hand. More formally, an undercut from a on b occurs when a has as a conclusion n(r) where rD(b).

Definition 3.

Let a,bArg(AS) and b=b1,bnB:

  • a rebuts b iff Conc(a)Conc(b);

  • a undercuts b iff Conc(a)n(Conc(b1),Conc(bn)B).

a attacks b iff a,bArg(AS) and a rebuts13 b or a undercuts b.

To determine which rebuts result in a defeat we take into account the priorities over the rules used in constructing the arguments involved in the attack. For this we have to lift the order ⩽ over the defeasible rules D to a preference order ⪯ over the set of arguments Arg(AS) constructed on the basis of D. We will use the weakest link lifting (see e.g. [50]) according to which an argument is as strong as its weakest defeasible elements.

Exactly how the preference order ⪯ is taken into account when determining whether an attack is successful and results in a defeat depends on the nature of the attack that is being considered. When it comes to rebuttal, we follow [50] in assuming that a rebutting attack by argument a on argument b leads to defeat if a is not strictly weaker than b. Since in this paper we only work with total orders, this is equivalent to requiring that a is at least as strong as b. Concerning undercuts, the situation is a bit more complicated, as there is some debate as to what it means for an undercutter to be sufficiently strong for the attack to succeed. Are undercutting attacks successful independently of the strength of the arguments involved? Or should an undercutting attack by a on b lead to defeat only in case a is not strictly weaker (or even strictly stronger) than b? [50] works with a preference-independent notion of undercutting defeat according to which undercutting attacks always give rise to defeat. Their motivation, however, has been questioned by [10].14 In Definition 5 we follow what is the most frequent approach in the ASPIC-family, namely to assume that undercutting attacks are preference-independent. However, since our main results concern ASPIC-frameworks without undercut this choice is insignificant for this study.

Definition 4.

Where a,bArg(AS), ab iff there is an rD(a) such that for every rD(b), rr.

We are now ready to define defeat based on the weakest link lifting:

Definition 5.

Where a,bArg(AS), a defeats b (in symbols: (a,b)(AS)) iff:15

  • a rebuts some bSub(b) and ba;16

  • a undercuts some bSub(b).

We define the argumentation framework based on an argumentation system AS as (Arg(AS),(AS)).

Example 4

Example 4(Example 3 continued).

For the argumentation system AS2, we have the following argumentation framework:

aac--1-aac200903-g001.jpg

Given an argumentation framework consisting of arguments and defeats between these arguments, Dung [29] provides various semantics for determining the acceptability status of an argument in the framework, which we introduce in the next section.

2.3.Argumentation semantics

A Dung-style abstract argumentation framework (in short, AF) is a pair (Arg,) where Arg is a set of arguments and Arg×Arg is a binary relation of attack. Relative to an AF, Dung defines a number of extensions – subsets of Arg – on the basis of which we can evaluate the arguments in Arg.

Definition 6

Definition 6(Extensions).

Let (Arg,) be an argumentation framework and EArg:

  • Ea iff there is some bE such that ba.

  • E is conflict-free iff there are no a,bE for which ab.

  • E defends an argument a iff for every bArg such that ba then Eb.

  • E is a complete extension iff it is conflict-free and aE iff E defends a.

  • E is a preferred extension iff it is a set inclusion maximal complete extension.

  • E is the grounded extension iff it is the set inclusion minimal complete extension.17

  • E is a stable extension iff it is conflict-free and for every bArgE, Eb.

We will use pref((Arg,)) and stab((Arg,)) to denote the set of preferred respectively stable extensions of an argumentation framework (Arg,) and groun((Arg,)) to denote its grounded extension. Given an argumentation system AS, we will also use pref(AS), stab(AS) resp. groun(AS) to denote pref((Arg(AS),(AS))), stab((Arg(AS),(AS))) resp. groun(((Arg(AS),(AS))).

Example 5

Example 5(Example 4 continued).

The argumentation framework (Arg(AS2),(AS2)) has as grounded extension that contains a1, a1, a3, a4, a6, a7 but not a2, a5, a8 and a9. This extension is also the unique preferred extension. It is also stable as it attacks a2, a5, a8, a9, etc.

Based on these argumentation semantics, we define consequence relations:

Definition 7.

Where AF=(Arg(AS),(AS)) and sem{pref,stab}:

  • ASsemϕ if for some Esem(AS), there is some aE with Conc(a)=ϕ.

  • ASsemϕ if for every Esem(AS), there is some aE with Conc(a)=ϕ.

  • ASgrounϕ if there is some agroun(AS) with Conc(a)=ϕ.

3.Rationality postulates

The inferential behaviour of structured argumentation formalisms is often studied using so-called rationality postulates [19,20]. These properties ensure that argumentation-based inferences make sense from a logical and intuitive point of view.

In order to handle conflicts adequately, a minimal constraint on structured argumentation systems is that they do not allow for direct logical conflicts in any extension (selected according to some semantics sem). In other words, any extension should be consistent, i.e. there should be no two arguments a and b in the extension such that Conc(a)Conc(b).

Postulate 1

Postulate 1(Direct Consistency).

sem satisfies Direct Consistency for an argumentation system AS if there is no Esem(AS) such that there are some a,bE for which Conc(a)Conc(b).

The related (but stronger) postulate of indirect consistency requires not only that an extension does not contain two arguments that are in direct conflict, but requires that no conflict is derivable using the strict rules S from the conclusions of the arguments in the extension. In other words, indirect consistency requires that the set of conclusions of arguments in a given extension is consistent when closed under the strict rule base S.

Definition 8

Definition 8(R-proof).

Let Γ{ϕ} be a set of L-formulas and R a set of inference rules on L. An R-proof P of ϕ from Γ is a sequence ϕ1,,ϕn where for each 1in, ϕiΓ or ϕi is the head of a rule in R whose body only contains formulas in {ϕ1,,ϕi1}. We write ΓRϕ iff there is an R-derivation of ϕ based on Γ.

Fact 1.

Given a set of inference rules R, R is monotonic, reflexive and transitive.

Definition 9

Definition 9(S-consistency.).

Where S is a set of inference rules over L, a set Γ of formulas in L is S-inconsistent iff ΓSψ for some ϕL such that ΓSϕ and ψϕ. Otherwise it is S-consistent.

Postulate 2

Postulate 2(Indirect Consistency).

sem satisfies Indirect Consistency for an argumentation system AS=(L,S,D,K,n,A,) if for every Esem(AS), Conc[E] is S-consistent.

A third postulate is related to the interpretation of strict rules → as being truth preserving. Recall that a rule ϕ1,,ϕnϕ means that whenever ϕ1 and … and ϕn are the case, ϕ is necessarily the case as well. This licenses us to require closure under strict rules of any extension. What this means is that, whenever arguments with conclusions ϕ1,,ϕn are part of an extension (selected according to some semantics sem) and ϕ1,,ϕnϕ is a strict rule we should find an argument for ϕ in that same extension as well.

Postulate 3

Postulate 3(Closure).

sem satisfies Closure for an argumentation system AS=(L,S,D,K,n,A,) if for every Esem(AS), whenever Conc[E]Sϕ then ϕConc[E].

Fact 2.

Direct consistency together with closure imply indirect consistency.

In [20] the property of Non-Interference was defined. Roughly speaking, a formalism is non-interferent if syntactically disjoint sets of formulas do not influence each others consequences. In more detail, when Γ{ϕ} and Γ are two syntactically disjoint sets, a non-interferent system will allow one to infer ϕ from Γ iff ϕ is inferable from ΓΓ. A violation of non-interference thus means that syntactically disjoint knowledge bases influence each others outcomes. In most of the cases,18 a violation of non-interference is caused by an inadequate handling of inconsistencies (see Example 6 for a simple illustration): one inconsistency in the knowledge base can cause the whole system to crash since it contaminates the argumentation framework (i.e. the conflict spreads to all arguments, even to arguments which are syntactically disjoint from the inconsistent argument). A system crashing as the effect of an inconsistency is bad news, since it renders the formalism ineffective in extracting useful information from the knowledge base.

To give precise meaning to the notion of syntactic disjointedness (a crucial concept in the formulation of non-interference) we let Atoms(Δ) be the set of all atoms occurring in Δ (where Δ is a set of formulas and/or inference rules based on L). Two sets Δ and Δ are syntactically disjoint iff Atoms(Δ)Atoms(Δ)=. Finally, we define Θ=ϕΘϕ. We now define two notions of syntactic disjointedness for argumentations systems. The former (Definition 10) is intended to cover cases in which two argumentation systems share the same base logic, so cases in which the strict rules of both systems are induced by the same logical system. In contrast, Definition 11 is indented to cover cases in which two argumentation systems are based on domain-specific strict rules (see also Footnote 2).

Definition 10.

Two argumentation systems AS=(L,S,D,K,n,A,) and AS=(L,S,D,K,n,A,), based on the same strict rule set S, are syntactically disjoint iff DKhead[D]K and DKhead[D]K are syntactically disjoint.19

Definition 11.

Two argumentation systems, AS=(L,S,D,K,n,A,) and AS=(L,S,D,K,n,A,) are strictly syntactically disjoint iff DKhead[D]KShead[S] and DKhead[D]KShead[S] are syntactically disjoint.

Furthermore, given AS=(L,S,D,K,n,A,) and DD, we will denote the set of arguments that can be constructed on the basis of D by Args(D)={aArgs(AS)D(a)D}.

Postulate 4

Postulate 4(Non-Interference).

Non-Interference20 is satisfied for a semantics sem if for any two syntactically disjoint argumentation system AS=(L,S,D,K,n,A,) and AS=(L,S,D,K,n,A,), where KK is S-consistent, + is such that[] is the restriction of + to D×D [D×D], and AS+=(L,S,DD,KK,nn,A,+), we have:

sem(AS+)={Arg(D[E]D[E])Arg(AS+)Esem(AS),Esem(AS)}.21

Postulate 5

Postulate 5(Strict Non-Interference).

Strict Non-Interference is satisfied for a semantics sem if for any two strictly syntactically disjoint argumentation systems AS=(L,S,D,K,n,A,) and AS=(L,S,D,K,n,A,), where + is such that[] is the restriction of + to D×D [D×D], and AS+=(L,SS,DD,KK,nn,A,+), we have:

sem(AS+)={Arg(D[E]D[E])Arg(AS+)Esem(AS),Esem(AS)}.

As explained above, a violation of non-interference means that syntactically disjoint knowledge bases influence each other’s outcomes. We will first use the grounded extension to illustrate a violation of non-interference using a simplification of the argumentation system from Example 2.

Example 6.

AS 6=(LCL,SCL,D6,,A) where D6={q}. Clearly the argument a=q is in the grounded extension.

Suppose now we move to the knowledge base AS6=(LCL,SCL,D6,,A) where D6=D6{p;¬p}. Informally, AS6 consists of AS6 supplemented with the syntactically disjoint rule base {p;¬p}. We would expect to still have a in the grounded extension since we only added information that is irrelevant to q. However, this is not the case. To see this, notice we have, among others, the following arguments:

a:qb1:pb2:¬pb:b1,b2¬q

This gives rise to the following framework:

aac--1-aac200903-g002.jpg

We see that since CL satisfies ex falso quodlibet, the contradiction between p and ¬p can be used to construct an argument for ¬q that attacks a. Since there is no unattacked argument that defends a from b, a is no longer in the grounded extension of AS6. As such, non-interference is violated, since aac--1-aac200903-i001.jpg whereas aac--1-aac200903-i002.jpg.

To solve problems of this nature, [57,58] proposed to filter out inconsistent arguments like b. Indeed, if we restrict our attention to consistent arguments, a is unattacked and non-interference is satisfied for AS6 under the grounded extension. This is no coincidence since [57] showed that for any semantics subsumed by complete semantics and given an argumentation system with the trivial priority order =D×D, non-interference, closure and consistency are satisfied when inconsistent arguments are filtered out. [57] was the first work to investigate and solve the problem of interference.22 However, it has been argued in [27] that filtering out inconsistent arguments might be problematic for several reasons. First, checking the consistency of an argument might be computationally intractable. For example, when the strict rules are based on propositional classical logic CL, checking consistency of an argument is NP-complete. Secondly, [27] give several reasons against the appropriateness of filtering out inconsistent arguments for modelling real-life argumentation. They observe that there are many examples of real-life argumentation where inconsistency of an argument is shown dialectically.23

When looking back at Example 6, it seems that some of these shortcomings can be overcome for preferred and stable semantics. In fact, when considering the preferred extensions of Arg(AS6) (which coincide with the stable extensions), namely {a,b1} and {a,b2}, we see that a is part of both of these extensions and thus there is no interference problem. In more detail, every preferred extension contains a defeater of b (i.e. b1 respectively b2) that defends a from the inconsistent argument b. Thus, the question can be raised: is it even necessary to filter out inconsistent arguments when using semantics like the preferred or stable semantics? For argumentation systems without any restrictions on the language, this question has to be answered negatively:

Example 7.

AS7=(LCL,SCL,D7,,n,A) where

D7=p;p¬n(p);pq;p¬q;s.

We have (among others) the following arguments:

a:sb:pc:b¬n(p)d1:bqd2:b¬qd:d1,d2¬s

We get the following argumentation framework:

aac--1-aac200903-g003.jpg

Notice that in this argumentation framework, argument a is not in the unique preferred extension , even though it is syntactically independent from all the other defeasible rules. In other words, a is part of the unique preferred extension in AS7=(LCL,SCL,{s},,A), while adding the rules D7{s}, which are syntactically disjoint from {s}, results in interferent behaviour.

The problem in the above example can be avoided by filtering out the inconsistent d: in that case a will have no attacker and thus will be in the unique preferred extension.

In the following we will show that when omitting undercut from an ASPIC+ framework, all rationality postulates hold for preferred and stable semantics when the strict rules allow for contraposition. For these semantics it is inconsequential whether inconsistent arguments are removed. Moreover, we characterize these semantics in terms of maximal consistent sets of defeasible rules.

4.Results

We now present our meta-theoretic results. In this section we only consider argumentation frameworks without undercut attacks.

4.1.Preferred and stable semantics coincide

Our first result is that preferred and stable extensions coincide when S is contrapositive, i.e., it satisfies the following two requirements:24

S1

If Δ, ψSϕ for some ϕϕ, then Δ, ϕSψ for some ψψ; and

S2

If ΔSϕ for some ϕϕ, then Δ{ϕ}Sϕ.

Often, S2 will simply follow from S1. More precisely, this is the case whenever S has theorems. We say that ϕL is a theorem of S iff Sϕ.25

Fact 3.

If S has theorems, then S1 implies S2.

Proof.

Suppose γ is a theorem of S. Suppose Δ, ϕSϕ. By the monotonicity of S, γ, Δ, ϕSϕ. By S1, there is a γγ such that Δ, ϕSγ. Again by S1, Δ, γSϕ and by the transitivity of S, ΔSϕ. □

Theorem 1.

For any AS=(L,S,D,K,A,) where S satisfies S1 and S2, pref(AS)=stab(AS).

Proof.

This theorem is an immediate corollary of Theorem 9, proven in Appendix B. □

This result ensures that one can use dialectical proof theories for membership of an admissible extension (see e.g. [49]) to show that an argument belongs to a stable extension.

Checking whether an argument is contained in an admissible extension tends to be less demanding than checking if it is part of a stable extension [28], since the former requires us only to consider arguments that attack the argument in question, whereas the latter requires us to find a set that contains the argument in question and attacks every argument not in the set.26 However, it should be remarked that both checking whether an argument belongs to an admissible or a stable extension are in the worst case intractable [31].27

In the context of deductive argumentation with defeasible premises, results like Theorem 1 are well-known and are often strengthened by showing that the maximally conflict-free extensions (also called naive extensions) coincide with the preferred and stable extensions (see e.g. [9,37]).28 However, even for argumentation systems with the trivial prefence relation D×D over the set of defeasible rules D, maximally conflict-free extensions might not be stable or preferred, as shown by the following example:

Example 8.

Let AS8=(LCL,SCL,{p},{¬p},A). This argumentation framework has a unique stable extension which is also preferred: {aArg(AS8)D(a)=}. However, the set {p} is conflict-free. Thus, there is a maximally conflict-free set that includes p and this set is neither stable nor preferred.

4.2.Rationality postulates

The four rationality standards hold for both preferred and stable semantics (which coincide as shown in Theorem 1). The following theorem was shown for a slightly different setting in [53],29 and is proven in Appendix C.1:

Theorem 2.

pref and stab satisfy Direct Consistency, Closure and Indirect Consistency for any AS=(L,S,D,K,A,) for which S satisfies S1 and S2.

Non-interference holds for strict rule bases that are uniform:30

Definition 12.

A rule set S is uniform iff for any two sets of formulas Γ, Γ in L and any formula ϕ in L such that Γ is S-consistent and syntactically disjoint from Γ{ϕ}, it holds that ΓSϕ iff ΓΓSϕ.

Non-Interference for ASPIC+ for prioritized rule bases was not shown before and is proven in Appendix C:

Theorem 3.

pref and stab satisfy Non-Interference for any argumentation systems whose sets of strict rules are uniform and satisfy S1 and S2.

In particular, this means that an argumentation system that is induced by classical logic satisfies non-interference. In more detail, we say that AS=(L,S,D,K,n,A,) is induced by classical logic if L is closed under the classical connectives {¬,,} and S is the set of strict rules capturing classical logic CL (over L): ϕ1,,ϕnϕS iff {ϕ1,,ϕn}CLϕ. For a concrete example, see Example 2.

Fact 4.

Where AS=(L,S,D,K,n,A,) is induced by classical logic, S is uniform and satisfies S1 and S2.

Given the uniformity of classical logic, Theorem 3 immediately implies the non-interference of any argumentation system induced by classical logic.

Theorem 4.

pref and stab satisfy Non-Interference for any argumentation system induced by classical logic.

Strict Non-Interference holds for systems with sets of strict rules that satisfy S1 and S2.

Theorem 5.

pref and stab satisfy Strict Non-Interference for any argumentation systems with sets of strict rules S that satisfy S1 and S2.

The reader may wonder why S1 and S2 are needed. We first note that both S1 and S2 are very much in line with the interpretation of strict rules S as truth-preserving rules. For example, S1 requires that if ΔSA for some AB (i.e. Δ implies the falsity of B), then if B is true, one of the members of Δ must be false. Likewise, S2 requires that if Δ can be used to derive AB, i.e. show that B is false, B does not have to be assumed true.

From the perspective of the argumentative rationality postulates, S1 ensures that whenever an argument a is attacked by an argument b=b1,,bnConc(a), we can construct the contraposed argument b2,,bn,aConc(b1). If we cannot do this, several rationality postulates are violated.

Example 9.

AS 9=({p,q,s,r,p,q,s,r},S9,D9,{s},A,9) where S9={qr} and D9={sq,sr}, ϕ={ϕ} and ϕ={ϕ} for any ϕL, and sq<9sr. We have the following arguments:

a:sb:aqc:brd:ar

Notice that c attacks but does not defeat d since D(c)9D(d). Vice versa, d does not even attack c since c is a strict rule-argument, which cannot be attacked. Thus, the unique preferred extension of this argumentation framework includes a, b, c and d and thus this argumentation framework violates consistency since there are arguments for both r (namely c) and its contrary r (namely d).

S2 ensures, among other things, that a defeasible argument concluding an S-anti-theorem or contradiction (i.e., a formula ϕ for which Sϕ such as p¬p in classical logic) is attacked by a strict argument (namely ϕ). As such, S2 ensures there is always an argument that can defend any argument from an attack based on a “contradictory” formula. If this assumption is given up, non-interference can be violated for rule bases S that have explosive behavior:

Example 10.

Where L10={p,q,r,q,r}, D10={1r}, D10={2p;p1q;p1q}, p={p} (i.e. p is a falsity), q={q}, q={q}, r={r}, r={r}, and

S10={q,¬qϕϕL10}{pϕϕL10}{ϕpϕL10},
and (D10D10)2 ranks the defeasible rules according to their subscripts, consider AS10=(L10,S10,D10,,A,) and AS10=(L10,S10,D10D10,,A,). We get, for instance, the following arguments:
a1:pa2:a1qa3:a1qa4:a2,a3ra5:r

This results in the following argumentation graph

aac--1-aac200903-g004.jpg

This argumentation graph has the unique preferred extension and no stable extensions. Also, while r is in the grounded resp. in every preferred extension of AS10 it is not in the grounded resp. in any preferred extension of the aggregated framework. This means also non-interference does not hold. In sum, both the equivalence between stable and preferred semantics from Theorem 1 and non-interference are violated. Note while S satisfies S1, S2 does not hold since {p}Sp while Sp (recall that pp).

4.2.1.A note on symmetric contraries

The reader might at this point be suspicious that the results above admit counter-examples in view of argumentation systems with assymetric contraries. For example, the following example seems at first sight to contradict Theorem 1:31

Example 11.

Let AS11=({p,q,},S11,D11,,A) where S11=, D11={p;pq}, q= and p={q}. Then Args(AS11) consists, among others, of the following two arguments:

a:pb:a1q

Notice that b defeats a and itself. Hence there is no stable extension while the unique preferred extension is , thus {}=pref(AS11)stab(AS11)=.

However, the above example does not constitute a counterexample to Theorem 1, since in fact S11 violates S1. Indeed {q}Sq and qp yet there is no qq such that {p}Sq. In fact, for any rule base that satisfies S1, the set of contraries will be (pseudo-)symmetric in the sense that if there is a ϕψ then there is a ϕϕ for which ψSϕ. Notice that this is weaker than symmetry as it is perhaps usually understood, i.e. if ϕψ then ψϕ.

Fact 5.

If S satisfies S1 and ϕψ, there is a ϕϕ such that ψSϕ.

Proof.

Suppose that S satisfies S1 and ϕψ. Since ϕSϕ, with S1 there is some ϕϕ for which ψSϕ. □

4.3.Characterization using maximally consistent sets

In this section we show that the preferred and stable semantics can be characterized in terms of maximally consistent sets of defeasible rules. Similar results have been proven for a multitude of formalisms for deductive argumentation with defeasible assumptions, for example for deductive argumentation based on classical logic [4,5,22,35], or on arbitrary Tarskian logics [2], sequent-based argumentation [7,8,13] or assumption-based argumentation [37,38]. However, to the best of our knowledge, such results have not been established for argumentation with defeasible rules. We start with non-prioritized framework in Section 4.3.1 and then move to the prioritized case in Section 4.3.2.

4.3.1.The non-prioritized case

We first present a simple but flawed idea of how to characterize argumentation extensions by means of maximal consistent sets of defeasible rules which we call naive rule maximizing. For this we first define what it means for a set of defeasible rules in D to be consistent, given a fixed context of strict rules S and of (strict) premises K.

Definition 13.

Where ΔD, we define ΔKSϕ by KSΔϕ (see Definition 8).32

Where the context disambiguates, we simply write K instead of KS. Simply expressed, ϕ follows from Δ if it can be derived by applying modus ponens for premises in K and rules in SΔ. Where the context disambiguates, we will omit the sub-script K and simply write Δϕ.

Definition 14.

Where ΔD, Δ is KS-inconsistent iff there is a formula ϕ and a ψϕ for which ΔKSψ and ΔKSϕ. Otherwise Δ is KS-consistent.

Where the context disambiguates, we will simply speak of (in)consistent sets Δ. In particular, for the following result we assume a fixed argumentation system AS=(L,S,D,K,A,).

According to naive rule maximizing we collect as many defeasible rules as is consistently possible. Let for this MCSnaS,K(D) be the set of all KS-consistent ΔD for which there is no KS-consistent ΔD such that ΔΔ.33 However, this approach does not characterize argumentation semantics (and other “conclusion-maximizing” approaches such as default logic), as the following simple example illustrates.

Example 12.

Let AS12=(LCL,SCL,D12,,A) where ψϕ iff ψ=¬ϕ or ϕ=¬ψ and D12={r1:p,r2:pq,r3:¬q}.

Then MCSnaSCL,={Δ1:{r1,r2},Δ2:{r1,r3},Δ3:{r2,r3}}. However, if we consider the argumentation framework based on the same ingredients, we will have two preferred (resp. stable) extensions: E1={a1,a2,} and E2={a1,a3,} where a1=p, a2=a1q and a3=¬q. Note that both extensions contain a1=p. This contrasts with the maximal consistent set Δ3={r2,r3}.

The problem with the set {r2,r3} in our example is that it is not “grounded”: the rule r2 cannot be triggered: indeed, {r2,r3}Kp where body(r2)={p}. This is why it does not correspond to an extension of the corresponding argumentation framework. In the following we will restrict our attention to those sets of defeasible rules that are grounded in the sense that Δψ for each ψbody[Δ].

Definition 15.

Where ΔD and rD, r is KS-triggered by Δ iff ΔKSψ for each ψbody(r). We will also call Δ a KS-trigger set of r. Let ˆS,K(D) be the set of all Δ(D) such that every rΔ is KS-triggered by Δ.

As before we will reduce clutter whenever the context disambiguates and simply say that r is triggered by Δ, talk of trigger sets of r and denote ˆS,K by ˆ.

Fact 6.

Where Δˆ(D), Δ is inconsistent iff there are ϕhead[Δ] and ψϕ for which ΔKψ.

Proof.

For the right-to-left direction suppose there are ϕhead[Δ] and ψϕ for which ΔKψ. Since Δˆ(D) also ΔKϕ and we are done. The left-to-right direction can be shown by an induction over the lengths of the proof of ϕ and ψ from Δ by making use of the contrapositably nature of the strict rules. We omit the technical details but give a simple example instead.

Example 13.

Suppose, where K={d,s,t}, Δ={de;u,tp} and su and e,up are strict rules and pp we have the following two proofs (in tree form) demonstrating that ΔKp and ΔKp:

P1=desupP2=tp

By contraposition, also u,pe is a rule for some ee. So, we have the following proof

P3=tpsue,
which shows that ΔKe.

 □

Definition 16.

MCSS,K(D) is the set of all consistent Δˆ(D) for which there is no consistent Δˆ(D) such that ΔΔ.

Where the context disambiguates, we will omit the superscript and simply write MCS(D).

Example 14

Example 14(Example 12 cont.).

We have MCS(D)={Δ1:{r1,r2},Δ2:{r1,r3}}. Note that Δ1Kp and Δ2Kp just like both argumentation extensions contain arguments for p.

There is indeed a very close relationship between the set MCSS,K(D) and the preferred resp. stable extensions of AS=L,S,D,K,A. To state it we introduce one more notation.

Definition 17.

Where ΔD let Arg(Δ)=df{aArg(AS)D(a)Δ} be the set of arguments that only make use of defeasible rules in Δ.

Our main result for non-prioritized argumentation can then be stated as follows:

Theorem 6.

For any AS=(L,S,D,K,A) where S satisfies S1 and S2,

pref(AS)=stab(AS)={Arg(Δ)ΔMCS(D)}.

There are two open question which we will address in the remainder of this section: (a) can the grounded semantics respectively (b) can the extensions of frameworks constructed on the basis of prioritized defeasible rule bases be represented in a similar way?

We start with a negative result concerning question (a). One may expect that the grounded extension can be characterized by MCS(D). We give the following counter-example:

Example 15

Example 15(Example 6 continued).

Recall AS6 from Example 6. We have MCS(D6)={{p,q},{¬p,q}}, {q}=MCS(D6) and {q}ˆ(D6). However, the grounded extension is Arg(). Recall for this that the argument b=p,¬p¬q attacks a=q. Note that q is implied by every MCS, but there is no argument for it in the grounded extension.

What we see in the example is contaminating behavior by the inconsistent argument a which attacks the syntactically disjoint b. This contamination does not occur when working with MCSs. One way to deal with this problem in the context of formal argumentation is to filter out inconsistent arguments such as a [57].34

Definition 18.

Let Arg(AS) be the set of all consistent arguments a in Arg(AS), where a is consistent iff D(a) is consistent (see Definition 14). Similarly, where sem{pref,stab,groun}, let sem(AS) be the set of extension of the restriction of Arg(AS),(AS) to consistent arguments.

Indeed, once we filter out inconsistent arguments we can characterize also the grounded semantics. First we note a minor complication, namely, generally it does not hold that MCS(D)ˆ(D).

Example 16.

AS 16=(LCL,SCL,D16,,A) where ψϕ iff ψ=¬ϕ or ϕ=¬ψ and D16={r1:p,r2:¬p,r3:pq,r4:¬pq,r5:qs}. Then MCS(D16)={{r1,r3,r5},{r2,r4,r5}}. Note that MCS(D16)={r5}ˆ(D).

In the Appendix (Lemma 6) we show that there is a unique ⊂-maximal Δˆ(D) that is contained in MCS(D).

Definition 19.

We call the unique ⊆-maximal Δˆ(D) that is contained in MCS(D) the free set in D, denoted by Free(D).

The set Free(D) characterizes the grounded extension when filtering out inconsistent arguments.

Theorem 7.

Where AS=(L,S,D,K,A) and S satisfies S1 and S2, Arg(Free(D))=groun(AS).

Naturally, the question arises whether for preferred and stable semantics the filtering of inconsistent arguments changes the extensions. The answer is no:

Theorem 8.

For any AS=(L,S,D,K,A) where S satisfies S1 and S2,

pref(AS)=stab(AS)=pref(AS)=stab(AS)={Arg(Δ)ΔMCS(D)}.

4.3.2.The prioritized case

We now move to prioritized frameworks. Stable and preferred extensions can be characterized by selecting a subset of MCS(D). For this, we introduce a new priority-sensitive notion of consistency. Recall that the defeasible rules in D are ranked by a total order ⩽. This means that, without loss of generality, we can assume that the defeasible rules in D are ranked relative to a (finite) set of natural numbers. We denote this ranking by R:DN. Where ΔD, let R[Δ]=dfmin({R(r)rΔ}) where R[]=dfω>R(r) for all rD. We then define:

Definition 20.

Δˆ(D) is KS-R-consistent iff it is KS-consistent and for all Θˆ(D) for which (ΔΘ) there is a Δˆ(Δ) such that (ΔΘ) and R[Δ]R[Θ]. We write MCSRS,K(D) for the set of all KS-R-consistent Δ for which there are no KS-R-consistent Θ such that ΘΔ.

An R-consistent set Δ is a consistent set that “dominates” every set Θ that is inconsistent with it in the sense that we can always find a subset Δ of Δ that is already inconsistent with Θ but for which R[Δ]R[Θ]. This makes it rational to stick with an R-consistent set of rules Δ since whenever we are confronted with a set of rules Θ inconsistent with Δ, it is rational to disregard a rule in Θ because the conflict can be further localized in the conflict (ΔΘ) and there is no reason to give up rules in Δ since R[Δ]R[Θ].

In order to avoid clutter we will again talk about R-consistent sets and write MCSR whenever the context disambiguates.

In the appendix we show that, as expected, the set of maximally R-consistent sets is exactly the set of all maximally consistent set that are R-consistent (Proposition 1).

Example 17

Example 17(Example 2 continued).

We consider a slight modification of AS2 that does not contain undercut: AS2=(L2,SCL,D2,K2,A,) where D2=D2{b1¬δ}.

We have one set of rules that is maximally R-consistent: Θ={g2¬p,l1q,q1w}. Note that any set Δˆ(D2) that is inconsistent with Θ contains g1p. Since R[{g2¬p}]R[Δ] and {g2¬p}Θ this suffices to show that Θ is R-consistent. Since Θ is also maximally consistent, it is maximally R-consistent as well. Our other maximally consistent set Θ={g1p,l1q,q1w} is not R-consistent since for Δ={g2¬p} we have (ΔΘ) and there is no Θˆ(Θ) for which (ΘΔ) and R[Θ]R[Δ]. This is for the simple reason that any Θ for which (ΘΔ) will contain g1p.

Maximal R-consistency can be used to characterize preferred and stable semantics, both for frameworks with and without consistent arguments.

Theorem 9.

Where AS=(L,S,D,K,A,) and S satisfies S1 and S2,

pref(AS)=stab(AS)=pref(AS)=stab(AS)={Arg(Δ)ΔMCSR(D)}.

Our final question is whether we can characterize the grounded semantics in a similar way as in Theorem 7 also for the prioritized setting. The answer is negative, as the following example illustrates.

Example 18.

Consider AS18=(LCL,SCL,D18,,A,) where ψϕ iff ψ=¬ϕ or ϕ=¬ψ and

D18={r1:5pq,r2:5p¬q,r3:4¬p,r4:¬p4¬s,r5:3s}.
We have, among others, the arguments:
a:pqa1:apa2:a¬(p¬q)b:p¬qb1:apb2:a¬(pq)c:¬p¬sd:s

This gives rise to the following argumentation framework:

aac--1-aac200903-g005.jpg

We have MCSR(D18)={{r1,r5},{r2,r5}} and so {r5}=MCSR(D18). Note also that {r5}ˆ(D18) and so it is the unique ⊂-maximal set contained in MCSR(D18). Nevertheless, the grounded extension for this example does not include any defeasible arguments and so also not an argument for s.

5.Related work

As pointed out in the introduction, work on simultaneous satisfaction of all rationality postulates for members of the ASPIC-family is rather limited. The postulates of consistency and closure, on the other hand, have been more extensively investigated. They were first introduced in [1,19] and were subsequently proven for ASPIC+ in [50,53] where the strict rule base satisfies either contraposition or transposition. This line of work was continued in [32], where different variants of the weakest link lifting were studied. Let us therefore compare the conditions of contraposition and transposition to the conditions S1 and S2 used in this paper. Let ϕ denote a contradictory of ϕ, i.e., a formula ψ for which ϕψ and ψϕ. For the definitions of Tpos and Cpos we thus follow [50] in assuming

  • CPE Every formula ϕ has a contradictory ψ (so ϕψ and ψϕ)

that every formula has a contradictory. Given an argumentation system (L,S,D,K,n,A,), transposition and contraposition require the following:

  • Tpos If ϕ1,,ϕnϕS then for every 1in, ϕ1,,ϕi1,ϕ,ϕi+1,,ϕnϕiS.35

  • Cpos For any ΔL, if ΔSϕ then for all ψΔ, (Δ{ψ}){ϕ}Sψ.

Unlike [50], in the setting of this paper we did not suppose CPE, i.e., the existence of contradictories. Note, however, that S1 implies that if some formula has a contrary, so does every.36 For most use cases of ASPIC this will coincide with the slightly stronger assumptions that

  • CTE For every formula ϕ, ϕ.

Clearly, CPE implies CTE but not vice versa. Assuming CTE, we can define the variant of CPos (and analogous of Tpos):

  • Cpos For any ΔL, if ΔSϕ, then for all ψΔ, for all ψψ, and for all ϕϕ, (Δ{ψ}){ϕ}Sψ.37

It will not surprise the reader that there is a close connection between the Cpos resp. Cpos and requirement S1.

Fact 7.

Cpos implies S1 if for all ϕL and all ϕϕ, ϕSϕ.

Proof.

Assume Δ, ψSϕ for some ϕϕ and that Cpos is valid. By Cpos, Δ, ϕSψ. Since ϕSϕ and by the transitivity of S, Δ, ϕSψ. □

Fact 8.

Cpos and CPE imply S1.

Proof.

Suppose Δ, ψSϕ for some ϕϕ. By Cpos and CPE, Δ, ϕSψ. Since ϕSϕ, by Cpos and CPE, ϕSϕ and furthermore, ϕSϕ. By the transitivity of S, Δ, ϕSψ. □

Fact 9.

Cpos implies S1 if for all ϕL and all ϕϕ there is a ϕϕ for which ϕSϕ.

Proof.

Assume Δ, ψSϕ for some ϕϕ and that Cpos is valid. We have to show that Δ, ϕSψ for some ψψ. We suppose that ϕSϕ for some ϕϕ. By Cpos, Δ, ϕSψ for some ψψ. By the transitivity of S therefore Δ, ϕSψ. □

In particular, the requirement of Facts 79 hold if for all formulas ϕ all members of ϕ are contradictories, i.e., if ϕϕ for all ϕϕ.

Interestingly, even given CPE, we can easily find counter-examples to rationality postulates such as Consistency for frameworks satisfying Cpos (and similarly for Tpos).

Example 19.

Consider AS19=(L19,S19,D19,{},A,19), where L19={p,q,¬p,¬q,,}, S19={}, D19={r1:p,r2:q}, ={}, ={}, p={¬p}, ¬p={p}, q={¬q,p}, ¬q={q}, and r119r2.

Note that p is merely a contrary, not a contradictory of q, while ¬q and q are contradictories. We have the following arguments:

a:pb:q

Note that we have no defeats between a and b and so the only preferred, stable and grounded extension will include both arguments. Nevertheless, this extension is not consistent since the conclusions p and q are not consistent given that pq.

Note that while S19 satisfies Cpos and CPE, it does not satisfy S1 since pS19p but not qS19¬p.

The example also shows that S1 does not imply Cpos.

To see that neither Cpos, Cpos, nor Tpos implies S2, consider the following example: Let S= and p={p}. Then we see that S is closed under Cpos and Tpos, however, it does not satisfy S2, as {p}Sp yet p. In view of Example 10, this means that Tpos and Cpos as studied in [50] are not sufficient to guarantee non-interference.

As Example 19 shows, only relying on Cpos (or Tpos) in combination with CPE does not suffice to get rationality postulates, such as Consistency. What is proposed in addition in [50] is to treat rebut defeats where the concluding formula of the attacking argument is a contrary (so not a contrapositive) of the conclusion of the attacked argument different from those rebuts with contradictory conclusions. While the latter case works as our Definition 5, in the former case argument strength is disregarded and any attack results in a defeat. While this move secures the standard rationality postulates (except for non-interference), it leads to what may be considered as counterintuitive behavior nevertheless. We give some examples.

Example 20

Example 20(Problems with “contrary-rebut”).

In all example below we treat ¬ϕ and ϕ as contradictories. Our examples concern two very weak versions of “interference”38 and a lightweight version of the well-known Cumulativity principle from non-monotonic logic.

  • Interference 1. Suppose AS1 has the rule base D={8p}, p has as a contrary r and the strict rules are induced by classical logic. Clearly, p will be a grounded consequence of AS1. Suppose further we add the rules D={1q,1¬q} resulting in an extended system AS2. Now the argument 1q, 1¬qr will defeat 8p and p will therefore not be a grounded consequence of AS2. Note that we only added weaker rules than the ones in AS1, both of which are syntactically disjoint from AS1, but this was sufficient to contaminate the framework.

  • Interference 2. In this example we will again add rules to a given AS3, this time rules that only extend arguments which are rejected in any extension of a given standard (completeness-based) semantics. Let AS3 be based on D3={100p,2¬p}. Clearly, the argument a=100p will be in any extension, while b=2¬p will be defeated in any extension. We now add the rules in D4={¬p1q,q1p} resulting in AS4, where p has as a contrary p. We note that these rules are weaker than those in D3 and they only extend our rejected b to c=b1q1p. Interestingly, now c defeats a and so p will not be anymore a consequence of AS4.

  • Cumulativity lite. Suppose an argument a with conclusion ϕ and strength n (so n=min({mϕ1,,ϕkmψD(a)})) is contained in every preferred extension of AS. Then one would expect that adding a new rule nϕ to the defeasible rules should lead to robust results. (In Appendix C.4 we show that our system satisfies our expectation.) Let AS5 come with the rules

    D5={10p,p10q,qr1¬q,¬q1p},
    and suppose p has as a contrary p. We have, for instance, the following arguments:
    a:10p10qa:aqrb:a1¬qb:b1p

    This results in the framework to the left:

    aac--1-aac200903-g006.jpg

    So a and a are contained in every preferred extension of AS5. Now if we add 10qr to D5 (resulting in AS6), we also get the argument c=10qr1¬q and c=c1p. This results in the graph to the right (omitting the nodes b and b for clutter reduction). Now, there is a preferred extension containing c and c in which a and a are defeated, so that p and q are not anymore consequences of AS6.

In order to avoid this kind of behavior we stuck in this paper to a uniform treatment of defeat where argument strength is considered for both rebuts, those with contrary and those with contradictory attacking formulas.

[30] goes beyond transposition and contraposition by formulating a condition called the self-contradiction axiom, which is implied by both transposition and contraposition. This self-contradiction axiom requires of an argumentation system AS=(L,S,D,K,A) that:

SCA

for any ⊆-minimally inconsistent39 set of formulas ΣL, ΣSϕ for any ϕΣ and some ϕϕ.

[30] shows that this axiom is sufficient to guarantee the postulates of closure and consistency for argumentation systems without preferences over the defeasible rules. However, non-interference is not studied. In fact, self-contradiction alone is not sufficient to guarantee non-interference, even for argumentation systems without preferences. To see this, notice that in Example 10 the self-contradiction axiom is satisfied as: for all ϕL10, {p}Sϕ and {q,¬q}Sϕ. However, as explained in Example 10, non-interference is not satisfied.

In this paper, we characterized the extensions of frameworks under some argumentation semantics in terms of maximal consistent sets of premises. As mentioned above, for structured argumentation with defeasible premises, such results are well-studied, see e.g. [6]. In contrast, for structured argumentation with defeasible rules such results were, to the best of our knowledge, not yet available. A series of different but related results are presented in [3], where structured argumentation formalisms allowing for reasoning with defeasible rules are studied. This paper studies the exact effects of various conditions on both the attack relation and the output of structured argumentation formalisms on the behaviour of various argumentation semantics. For example, it is shown for a conflict-dependent attack relation (which says that if a attacks b, then {Conc(c)cSub(a)Sub(b)}S), the output of an argumentation system satisfies consistency, closure, closure under sub-arguments. Moreover, if every extension contains all strict arguments, for every stable extension E, D[E] is maximally consistent. It is also shown that if an attack relation is such that the number of stable extensions is the same as the number of maximally consistent subsets of defeasible rules, the stable and the preferred extensions coincide (as in Theorem 1) and coincide with the sets of arguments that can be constructed on the basis of maximally consistent subsets of defeasible rules (as in Theorem 9).

Although the results in [3] are similar in spirit to some of the results obtained in this paper, the set-up is quite different. While we obtain results for a specific system, [3] takes a reverse-engineering approach by studying requirements for structured argumentation formalisms that warrant desired results. Finally, in [3] priorities over the defeasible rules are not studied and arguments are assumed to be consistent and minimal, which is not required in the present study.

In [59 ,60] ASPIC+ is used to obtain an argumentative characterization of prioritised default logic [16]. For this it is noticed that the weakest link lifting is not adequate and therefore the structure preference order has to be used, a lifting tailored for the characterization of prioritised default logic. Since prioritised default logic gives rise to a single extension for totally ordered default theories, the resulting ASPIC+ frameworks also have a unique stable extension, which can be contrasted with ASPIC+ under weakest link (see e.g. Example 6). Furthermore, even though [59,60] show closure, direct and indirect consistency for the resulting formalism, non-interference is not mentioned.

6.Concluding discussion and outlook

The main contributions of this paper can be summarized as follows: ASPIC+ without undercut and defeasible premises, and with a strict contrapositable rule base satisfies all four rationality postulates under preferred and stable semantics (which coincide) and admits a representation in terms of maximal consistent subsets under the weakest link lifting for totally ordered defeasible rules. Furthermore, we showed that the grounded extension for non-prioritized argumentation systems contain the free defeasible rules, but for prioritized argumentation systems such a characterization does not work. We conclude this paper by explaining how these results shed further light on the close relationship between assumption-based argumentation and ASPIC+ and finally point to further work we plan on the basis of this paper.

6.1.Assumption-based argumentation

Besides the ASPIC-family, another popular approach to structured argumentation is assumption-based argumentation [12]. As the name suggests, it provides a formal model of reasoning with strict rules and defeasible assumptions. In contrast to ASPIC, it does not allow for the chaining of defeasible inference rules.40 Another major difference between these two formalisms is that in ABA, nodes in argumentation graphs consist of sets of defeasible assumptions, as opposed to structured arguments in the form of proof trees for a specific conclusion in ASPIC+. In this way, ABA can be seen as an abstraction to the level of equivalence-classes of arguments that are based on the same defeasible ingredients.

Formally, a prioritised ABA system ASABA=L,Ab,S,K,A, consists of a language L, a set of defeasible assumptions AbL, a set of strict rules formulated over L, a strict premise set K, a contrariness relation A:Ab(L) and a preference relation ⪯ over Ab. Argumentation frameworks constructed on the basis of a prioritised ABA system ASABA are AF(ASABA)=((Ab),) where ΔΘ iff (1) KΔSA for some AB and some BΘ and (2) min(Δ)B.41

Several results have indicated a strong connection between assumption-based argumentation and reasoning with maximally consistent subsets for both non-prioritized [37,43] and prioritized assumption-based systems [40,42]. Theorem 9 generalizes such insights to settings where defeasible inferences can be chained. This result thus shows that ABA and ASPIC+ give rise to similar output. What is still an open question, though, is whether the abstract perspective offered by ABA (i.e. to consider argumentation graphs on the basis of equivalence classes of arguments) can also be obtained in ASPIC+. A positive answer to this question would mean that it is possible to smoothly change perspectives between different levels of abstraction for argumentation based on defeasible rule bases. The more abstract perspective has the benefit that the set of arguments is bounded by the size of the powerset of defeasible elements, which implies that the set of arguments will be finite if the set of defeasible elements is finite. This stands in contrast with approaches with ASPIC+-style arguments, where even for a finite number of defeasible elements, the argumentation graph may contain an infinite number of arguments (since e.g. classical logic gives rise to an infinite number of conclusions for every premise set).

6.2.Outlook and further work

One limitation of this work is that the rationality postulates and the correspondence with maximally consistent sets have only been proven for argumentation systems without undercutting attacks, without defeasible premises and only for systems with totally ordered sets of defeasible rules. E.g., concerning undercut, Examples like 7 lead to interferent behaviour. Similarly, it is a challenge to generalize our results to non-total orders and to incorporate defeasible premises which may be incomparable in strength to some of the defeasible rules, in such a way that the rationality postulates are satisfied. This will be a topic for future work.

Furthermore, in this contribution we only considered the weakest link lifting. Our results do not cover another popular lifting for ASPIC+, the last link lifting. According to it, an argument is as strong as the last defeasible elements applied in the construction of the argument. A complication with the last link lifting concerns arguments in which we are dealing with several last defeasible links. We can, for instance, opt for the strongest of the last links (called elitist approach [50]) or the weakest (called democratic approach in [50]). It turns out that both approaches lead to violations of non-interference in the current setting. We paradigmatically present an example for the democratic approach.

Example 21

Example 21(Inspired by Example 6.7 in [57]).

AS 21=(LCL,SCL,D21,{s},A,) where ϕ={ψψCL¬ϕ} and D21={s1p;p3q;s2¬p¬q}. We have, among others, the following arguments:

a:sa1:a1pa2:a2¬p¬qa3:a13qa12:a1,a2p¬qa13:a1,a3pqa23:a2,a3¬pqa:a1,a2,a3

In this example we use the democratic last link lifting, which says that an argument blldc iff the ⩽-minimal last defeasible rule used in b is weaker than the ⩽-minimal last defeasible rule used in c. For example, a2llda3 since the weakest last defeasible link of a2, s2¬p¬q, is weaker than the weakest (and only) last defeasible link of a3, p3q. For the same reason, a3llda2. We get the following defeat diagram:

aac--1-aac200903-g007.jpg

It can be seen that the unique preferred extension only contains strict arguments and arguments with the defeasible rule s2¬p¬q. If we now add the syntactically disjoint rule 1t, the argument a123 defeats the argument 1t and thus interferes with the derivability of t.

It is interesting to note that AS21 is used in [57] to show that under last link, filtering out inconsistent arguments leads to violations of closure and consistency. Indeed, when a13, a23 and a are not part of the argumentation framework, a1, a2, a3, and a12 are all undefeated, meaning they are part of the unique preferred extension of Arg(AS21). This means that this extension contains arguments for e.g. p, q and ¬p¬q, constituting a violation of indirect consistency and closure (since {p,q,¬p¬q}CL but there is no argument for ⊥ in Arg(AS21)). It is therefore an important avenue for future work to define a formalism that satisfies all four rationality postulates under the last link principle.

Notes

1 The notation used in this example will be properly introduced in Section 2.

2 In the context of ASPIC+ scholars often distinguish domain-dependent from domain-independent rules (see e.g., [53, Section 4] for a more detailed discussion). The latter hold for purely logical reasons which is why we deal with them typically when the set of strict rules is induced by a (Tarskian) logic, while the former cover typically cases in which the strict rules are not justified by a truth-preservational logical standard but rather by empirical insights.

3 For structured argumentation systems with defeasible premises (but without defeasible rules), on the other hand, the situation looks a lot better, see e.g. [9,27,37].

4 Note that ϕ does not denote the set theoretic complement.

5 K is S-consistent iff there is no derivation based on rules in S from K of some ϕK and some ψϕ. See also Def. 8.

6 A preorder is a binary relation that is reflexive and transitive.

7 More precisely, when omitting ⩽ we consider the preorder D×D.

8 We use subscripts to refer to the numbers of our examples.

9 In the examples that follow, we shall denote with SCL the rule set constructed in the same way as in this example, except that the language is changed relative to the example at hand.

10 In all the examples that follow where L is closed under ¬, we will treat ϕ the same.

11 In this paper we will for the sake of simplicity omit several features of the original ASPIC+ framework of [53], such as defeasible premises and undermining attacks. We note that (in case no incomparabilities between the strength of defeasible premises and the strength of defeasible rules occur) defeasible premises γ can easily be modelled as a defeasible rule γ and undermining attacks can be modelled as a rebuttals.

12 We note that D is a set of rules whereas D(a) is a function mapping arguments to subsets of D. This will not cause any confusion.

13 Some works [21,39,41] have studied forms of unrestricted rebut where the conclusion of the attacked argument need not be the head of a defeasible rule.

14 A preference-dependent notion of undercutting attack was for example also used by [11] in the context of deontic logic, with the aim of modelling a cautious, ‘austere’ style of reasoning.

15 Unlike [50], in our contribution we do not distinguish between defeats with contrary formulas from those with contradictory formulas. See a justification of our approach in the context of a richer discussion in Section 5.

16 [50,53] distinguish between rebuts where Conc(b)Conc(a) and rebuts where Conc(b)Conc(a). The latter they call contrary-rebut and treat differently, since in these works contrary-rebuts result in defeats regardless of the relative strength of a and b. We will have more to say about this in Section 5.

17 Dung [29] showed that for every AF (Arg,) there is a unique grounded extension, which we denote by groun((Arg,)).

18 In [41, Example 6.1] one finds an example of a violation of the related postulate of crash-resistance that is caused by an inadequate treatment of incomparable priorities instead of inconsistencies.

19 Notice that this notion of syntactic disjointedness would have to be more explicitly spelled out when generalizing the results of this paper to a first order language. For an example of how to do this, cf. [27, Notation 3].

20 A related rationality standard is Crash-Resistance. It follows from Non-Interference under some very weak criteria on the strict rule base (cf. [20]).

21 We here phrase Non-Interference in terms of the semantics rather than in terms of the nonmonotonic entailment. In the setting of this paper, the latter formulation is a direct corollary of our formulation.

22 Another recently proposed strategy to obtain non-interference for prioritized settings with the grounded semantics is to use a generalized non-restricted form of rebut [41].

23 [58] observes that filtering out inconsistent arguments does not work when using the last link lifting. Unfortunately, even though we show that for a wide class of frameworks filtering out inconsistent arguments is unnecessary, these results do not generalize to the last link lifting either, as we show in Example 21.

24 In Section 5 we give a detailed comparison between these assumptions and other definitions of contaposition found in the literature.

25 Note, however, that the requirement is non-trivial even in cases where S is induced by a logic, since some logics, such as the well-known 3-valued logic K3 lack theorems.

26 A similar observation has been made in [28], where it is shown that stable and preferred semantics coincide for deductive argumentation with defeasible premises.

27 To give substance to the intuition that checking membership of an admissible extension is less demanding than checking membership of a stable extension, it might be interesting to compare proof theories for these problems (see e.g. [49]) using criteria proposed to compare efficiency or computational demands of proof theories as proposed in e.g. [23,26].

28 This is not necessarily so in logic/sequent-based argumentation for specific choices of attack-forms as shown in [7].

29 In Section 5 we give a detailed comparison of the setting of [53] and the assumptions made in this paper.

30 Structural consequence relations S are also well-behaved in other respects, such as having a characteristic matrix (see [56, Theorem 3]).

31 This example was suggested to us by a reviewer.

32 We use the same ⊢ symbol in both Definitions 8 and 13: note, however, that its usage is disambiguated by the nature of the subscript and the nature of its left side, which is either a set of rules and a set of L-formulas (Def. 8), or a set of formulas in L and a set of rules (Def. 13).

33 This is the core mechanism behind constrained input-output logics [48].

34 In [39,41] an alternative solution to the problem of contamination is investigated that does not require to filter out inconsistent arguments but is instead based on a generalized notion of rebut attack.

35 This is the formulation from [50] while [19,53] only require “…then for some 1in …”. [19] state the property explicitly only for ¬ instead of A. Similar comments apply to Cpos. The exact effect of the subtle differences between these different formulations of transposition, respectively contraposition and different assumptions on the contrariness relation A are outside the scope of this paper but give rise to an interesting direction for future research.

36 Suppose ϕϕ. Then {ψ,ϕ}Sϕ and so by S1, {ϕ,ϕ}Sψ for some ψψ.

37 A similar example as Example 9 can be used to show that a weaker version of Cpos which only demands “for some ψψ and for some ϕϕ” instead of “for all ψψ and for all ϕϕ” leads to problems with rationality postulates. Consider AS9=({p,q,s,r,p,q,s,r},S9,D9,,A,9) where S9={qr,rq}, r=r={r}, r={r,r} and for all other atoms ϕ, ϕ={ϕ} and ϕ={ϕ}. We have the same arguments as in Example 9 and the counter-example to closure is thus analogous. Note that S9 satisfies the weak version of Cpos.

38 We use this term in order to indicate that the addition of “irrelevant” information leads to contaminating effects (see also [14]). “Irrelevance” is disambiguated differently in the two versions considered.

39 On the most general level, [30] assumes that an argumentation system is built on the basis of an abstract logic (CN,CONTRA) over a language L where CN is a Tarskian consequence relation and CONTRA is a collection sets that is upward-closed and doesn’t contain CN(). A set Δ is inconsistent if Cn(Δ)CONTRA. For ASPIC+ with symmetric negation, [30] remarks that CONTRA can be instantiated by any set that contains both a formula and its contarry. In view of Definition 9, this can be seen to coincide with our notion of inconsistency.

40 Although it has been shown in [43] that, at least when preferences are not taken into account, ABA admits ASPIC+, and thus the chaining of defeasible rules, via a translation.

41 We compare here ASPIC+ with assumption-based argumentation with direct attacks, called ABAd in [40,44]. However, in the setting of this paper, the remarks made here generalize to assumption-based argumentation with reverse attacks (called ABAr in [40,44] and ABA+ in [25]), since it has been shown that ABAr and ABAd give rise to the same outcomes when a flat assumption-based framework satisfies S1 and S2 [42].

42 For simplicity we suppose here that our defeasible rules are ranked.

Acknowledgements

We would like to thank the anonymous reviewers of this manuscript for useful comments. The research of Jesse Heyninck was supported by the the FCT project RIVER (PTDC/CCI-COM/30952/2017), NOVA LINCS (UID/CEC/04516/2013) and the German National Science Foundation under the DFG-project CAR (Conditional Argumentative Reasoning) KE-1413/11-1.

Appendices

Appendix

AppendixProofs

The order of appearance of results in these appendix does not necessarily mirror the order of the statements of these results in the paper but is primarily based on logical dependency.

In order to avoid clutter, we will in the following proofs often slightly abuse notation by using ϕ to denote an arbitrary representative of ϕ.

Appendix B.

Appendix B.Representation in terms of maximal consistent sets

B.1.The flat case

In what follows we shall assume a fixed AS=(L,S,D,K,A) where S satisfies S1 and S2. We start with some facts about set in ˆ(D). We will usually write ⊢ instead of KS (see Def. 14).

Fact 10.

Where Δˆ(D) and Δϕ, there is an argument aArg(AS) with D(a)Δ and conclusion ϕ.

Proof.

Suppose Δˆ(D) and Δϕ. By Def. 14, KSΔϕ. Thus, by Def. 8, there is a proof P of ϕ based on facts in K and rules in S and Δ. We construct a now exactly in terms of the structure of P. □

Fact 11.

Where Δˆ(D): K, head[Δ]Sϕ iff Δϕ.

Proof.

Suppose K, head[Δ]Sϕ. By Def. 13 we have to show that KSΔϕ. Since Δˆ(D) and by Def. 15, for each rΔ, Δψ for all ψbody(r). So, KSΔψ for all ψbody[Δ]. Also, by applying the rules in Δ we get KSΔψ for all ψhead[Δ]. By our main supposition KSΔϕ.

Suppose Δϕ. By Def. 14, KSΔϕ. By Def. 8, there is a proof P of ϕ from K using rules in S and Δ. Let {r1,,rn}Δ be the set of all defeasible rules used in P. Then, trivially, also K,{head(r1),,head(rn)}Sϕ. Thus, K, head[Δ]Sϕ. □

Fact 12.

ˆ(D) is closed under.

Proof.

Let Δ,Θˆ(D) and rΔΘ. Without loss of generality let rΔ. Thus, r is triggered by Δˆ(ΔΘ) and so also by ΔΘ. □

Fact 13.

Where Δˆ(D) and rΔ, there is a Θˆ(Δ{r}) for which Θψ for all ψbody(r).

Proof.

Consider a ψbody(r). Since Δψ there is a proof P from Δ of ψ which we can, without loss of generality, assume to be minimal (in that no proper sub-proof of P establishes ψ). Let Δψ be the set of all rΔ that are used in P. Note that if (modus ponens on) r were used in P, there would be a proper sub-proof of P that establishes ψ since ψbody(r). Thus, rΔψ. Moreover, since trivially all rΔψ are used and thus triggered in P, Δψˆ(Δ).

Let Θ=ϕbody(r)Δϕ where for each ϕbody(r), Δϕ is defined as in the previous paragraph. By Fact 12, Θˆ(Δ). Since for each ϕbody(r), Δϕϕ, also Θϕ for all ϕbody(r). Since rΔϕ for all ϕbody(r), also rΘ. □

Fact 14.

Where Δˆ(D) and r and r are two different rules in Δ, for any-minimal trigger sets Δr,Δrˆ(Δ) for r and r we have: (rΔr{r} or rΔr{r}) and so (Δr{r}Δ or Δr{r}Δ).

Proof.

Let r,rΔ such that rr and let Δr,Δrˆ(Δ) be ⊂-minimal trigger sets of r resp. r. Assume Δr{r}=Δ. So, rΔr. By Fact 13 and the ⊂-minimality of Δr, rΔr. Since Δrˆ(D), there is a ⊂-minimal Δrˆ(Δr) that triggers r. Since Δr{r}ΔrΔ we are finished. □

Fact 15.

Where Δˆ(D) is finite and non-empty, there is a Δˆ(Δ) such that ΔΔ and all rΔ are triggered by Δ.

Proof.

Let Δ={r1,,rn}ˆ(D). Assume for a contradiction that there is no Δˆ(Δ) such that ΔΔ and Δ triggers all rΔ. This means that for each rΔ there is a π(r)Δ{r} for which there is no trigger set in Δ{r}. Thus, for r1 there is a π(r1)Δ{r1} such that every trigger set of π(r1) contains r1.

With some renumbering let π(r1)=r2. Also for r2 there is a π(r2) for which there is no trigger set in Δ{r2}. Suppose π(r2)=r1. However, then every trigger set of r2 includes r1 and every trigger set of r1 includes r2 which contradicts Fact 13 since then every trigger set of r1 includes r1.

After some renumbering let π(r2)=r3. Again, there is a π(r3) for which there is no trigger set in Δ{r3}. Suppose r2=π(r3). But then every trigger set (in Δ) of r2 contains r3 and vice versa, every trigger set of r3 (in Δ) contains r2. This is in contradiction with Fact 14. Suppose then that r1=π(r3). So any trigger set of r1 contains r3. However, every trigger set of r3 contains r2 and so every trigger set of r1 contains r2. Since every trigger set of r2 contains r1 this is impossible.

Altogether we can create a sequence r1,π(r1)=r2,π(r2)=r3,,π(ri)=ri+1,. Since each member of the sequence is different from those before and since we only have n many rules we run into a contradiction. This means our assumptions was false. □

Fact 16.

Where Δˆ(D) is finite, Δ0= and Δi+1 is the set of all rΔ triggered by Δi then Δ=i0Δi, Δii0 is-monotonically increasing, and there is a minimal fixed point Δk=Δk+1.

Proof.

Note that in our construction for each i0, Δiˆ(D). Therefore also Δi+1Δi. A fixed point is reached after finitely many steps since Δ is finite.

“⊆”: Let rΔ. Thus, there is a Λ0ˆ(Δ) that triggers r. By Fact 15, there is a Λ1ˆ(Λ0) that triggers every rΛ0 and for which Λ1Λ0. We proceed iteratively: for Λi there is a Λi+1ˆ(Λi) that triggers each rΛi and Λi+1Λi. Since Λii0 is a ⊂-monotonically decreasing sequence and Λ0 is finite, we reach a minimal point Λl=. Note that by the construction, i=0l1Λii0Δi. So, ri0Δi.

“⊇”: This holds trivially. □

Fact 17.

Where Δˆ(D) and ΔΔ, there is an rΔ such that some Δˆ(ΔΔ) triggers r.

Proof.

Let r0Δ. Thus, there is a finite Δ0ˆ(Δ) that triggers r0. In view of Fact 13 we can safely assume r0Δ0. Let Δ0=ΔΔ0. If Δ0= we are finished since Δ0ΔΔ triggers r0. Otherwise, for an arbitrary r1Δ0 there is a Δ1ˆ(Δ0) that triggers r1. In view of Fact 13 we can safely assume r1Δ1. Let Δ1=ΔΔ1Δ0. If Δ1= we are done since then Δ1ΔΔ triggers r1. Otherwise we continue in the same manner. Since Δii0 is a ⊂-decreasing sequence of finite sets, we reach the point where Δi= after finitely many steps at which point Δi triggers ri, ΔiΔΔ and riΔ. □

The next result offers a Lindenbaum-like construction of maximal consistent sets of defeasible rules in ˆ(D).

Lemma 1.

Where Θˆ(D) is consistent, there is a maximal consistent Δˆ(D) for which ΔΘ.

Proof.

Let D be enumerated by r1,r2,. Where L=l1,l2, is a list let top(L)=l1. Let tr(Λ)=rj1,rj2, be a list of all the rules triggered by Λ except those in Λ (where ji<ji+1 for every index). We construct Δ=dfα0Θα by a transfinite induction (bounded by ω2) as follows: (Θ0;R0;X0)=df(Θ;tr(Θ);), and for all successor ordinals α+1,

(Θα+1;Rα+1;Xα+1)=df(Θα{top(Rα)};tr(Θα{top(R)});Xα)if Θα{top(Rα)} is consistent,(Θα;Rα{top(Rα)};Xα{top(Rα)})else
and for all limit ordinals α, (Θα;Rα;Xα)=df(β<αΘβ;β<αRβ;β<αXβ).

We first show (inductively) that each Θα is consistent. For Θ0 this holds by the supposition. For the inductive step consider first a successor ordinal α and suppose Θα is consistent. Then, by the construction also Θα+1 is consistent. Consider now a limit ordinal α and suppose for all β<α, Θβ is consistent. Assume for a contradiction that that Θα is inconsistent. Thus, there is a finite Θ{r}Θα such that Θhead(r). Thus, there is a β<α for which Θ{r}Θβ. But then Θβ is inconsistent in contradiction to our inductive hypothesis.

Note also that in view of the construction (and Fact 12) Θαα0 is a monotonically ⊆-increasing sequence of sets in ˆ(D). By Fact 12, Δˆ(D).

Suppose now that Δ is not consistent. Thus there is a rule riΔ and a Δˆ(Δ) for which Δψ where ψhead(ri). Thus, there is a Θα for which ΔΘα. Also, since riΔ, either riΘβ where β=0, or for some β1, ri=top(Rβ) and Θβ+1=Θβ{ri}. Clearly, ΘβΘα or ΘαΘβ. So either, Θβ+1ψ or Θαψ in contradiction to the consistency of Θβ+1 respectively of Θα. So Δ is consistent.

Suppose Δ is not maximal consistent. Thus, there is a consistent Λˆ(D) for which ΔΛ. Let ΛΔ={r1,,rn,}. By Fact 17, some ri=rj is triggered by Δ. Thus, there is a Δˆ(Δ) for which Δψ for all ψbody(ri). Thus, there is a minimal α for which ΔΘα. Note that ri is triggered by Θα and that riXβ for any β0 (since otherwise Λ by item (ii)). But since ri never enters Xl, for some mi, ri=top(Rα+m) and by the consistency of Θα+m{ri}, it is added to Θα+m+1. This is a contradiction. □

In the following, given some proof P based on some (strict and/or defeasible) inference rules R, let topD(P) denote the set of the top (or last) defeasible rules used in P.

Fact 18.

If Δˆ(D), ΘMCS(D), and (ΔΘ), then Θψ for some ψhead[Δ].

Proof.

Since (ΔΘ), i.e., ΘΔ is inconsistent, there is a Λˆ(ΘΔ) for which Λϕ where ϕhead(r) for some rΘΔ. If ΛΘ, by the consistency of Θ, rΔ and so we are done. Otherwise, let ΛΘ={r1,,rn}. By Fact 17, there is an riΛΘ for which some set in ˆ(ΛΘ) triggers ri. Thus, Θ triggers ri and so Θ{ri}ˆ(D) is inconsistent (by the ⊆-maximality of Θ). Thus, there is a Ωˆ(Θ{ri}) such that Ωψ for some rΘ{ri} such that ψ=head(r).

If riΩ then r=ri by the consistency of Θ and our proof is finished.

Suppose now that riΩ. Let P be a proof of ψ from Ω. Let topD(P)={rk1,,rkm}. Suppose first that ritopD(P). But then there is a proof of ψ from Θ since each rkiΘ and as such is triggered by some Θiˆ(Θ). Let Θi+=Θi{rki}. Thus, 1imΘi+ψ. Thus, by the consistency of Θ, r=ri and we are done. Suppose now that ritopD(P). Without loss of generality, suppose ri=rkm. So, K,head(rk1),,head(rkm)Sψ. By S1, K,head(rk1),,head(rkm1),ψShead(ri).

If ri=r, by S2, K,head(rk1),,head(rkm1)Shead(ri) and thus Θ1+,,Θm1+head(ri). Since, in view of Fact 12, Θ1+Θm1+ˆ(Θ) our proof is finished.

If rir, then rΘ and since Θ triggers r, there is a Θrˆ(Θ) that triggers r. Thus, Θ1+,,Θm1+,Θr{r}head(ri). Since, in view of Fact 12, Θ1+Θm1+Θr{r}ˆ(Θ), our proof is finished. □

Lemma 2.

Where Θˆ(D) is consistent, there are no a,bArg(Θ) such that a attacks b.

Proof.

Where a,bArg(Θ), suppose a attacks b. Thus, there is an rD(b) such that D(a)head(r). This is in contradiction to the consistency of Θ since D(a)ˆ(Θ) and rΘ. □

Lemma 3.

Where ΘMCS(D), Arg(Θ)stab(AS) and Arg(Θ)stab(AS).

Proof.

Let A=Arg(Θ), where ΘMCS(D). By Lemma 2, A is conflict-free. Consider now some bArg(AS)A. Thus, D(b)Θ. Notice that since ΘMCS(D), (D(b)Θ) and hence, by Fact 18, there is a rD(b) for which Θhead(r). Thus, there is a Θˆ(Θ) such that there is a proof from Θ with conclusion head(r). The corresponding argument aA with D(a)Θ (see Fact 10) attacks b. □

The next fact follows since any defeater/attacker of a sub-argument of some argument a also defeats/attacks a.

Fact 19

Fact 19(Sub-Argument Closure).

Where A is a complete extension of AS, aA and b is a sub-argument of a, bA.

Fact 20.

Where AArg(AS) is closed under sub-arguments and rD[A], there is an argument aA with top-rule r.

Proof.

Suppose rD[A]. Thus, there is a bA with rD(b). Thus, there is a aSub(b) with top-rule r. By sub-argument closure, aA. □

Lemma 4.

Where Apref(AS) (resp. Apref(AS)), D[A] is consistent.

Proof.

Suppose Θ=D[A] is inconsistent. Thus, there is a finite Δˆ(Θ) and an rΘ for which Δhead(r).

Since Δ{r}D[A] and by the sub-argument closure of A (Fact 19) and by Fact 20, for each rΔ{r} there is a arA with top-rule r. Let Δr=D(ar).

Since Δhead(r), Δ={ΔrrΔ{r}} is inconsistent and by Fact 12 Δˆ(Θ). Let Δ=i=0kΔi=Δk as in Fact 16. Thus, there is a minimal 1lk for which Δl is inconsistent. Let ΔlΔl1={rl1,,rlm}. Let l be maximal in {l1,,lm} such that Λ=Δl1{rl1,,rl} is consistent while Λ{rl+1} is inconsistent. So, Λ{rl+1}head(r) for some r in Λ{rl+1}. Note that Λ,Λ{rl+1}ˆ(D). By Fact 11 (and the compactness of S), K, head[Λ], head(rl+1)Shead(r) for some finite KK and by S1 and S2, K, head[Λ]Shead(rl+1).

Where Λ={r1,,rm} and K={κ1,,κm} we have b=κ1,,κm,ar1,,armhead(rl+1)Arg(AS) attacks arl+1. Thus, there is a cA that attacks b. But this attack must take place in some ari in contradiction to the conflict-freeness of A. □

Lemma 5.

For every Apref(AS) (resp. Apref(AS)) there is a ΘMCS(D) such that A=Arg(Θ). In signs: pref(AS)Arg[MCS(D)] (resp. pref(AS)Arg[MCS(D)]).

Proof.

Suppose Apref(AS) (resp. Apref(AS)) and let Θ=D[A]. By Lemma 4, Θ is consistent.

Assume now that it is not maximal consistent. By Lemma 1, there is a maximal consistent Δˆ(D) for which ΔΘ. By Lemma 3, Arg(Δ) is stable and thus also admissible which contradicts the maximality of Θ. □

The following theorem follows immediately with Lemma 3 and Lemma 5.

Theorem 10.

Where AS=(L,S,D,K,A) and S satisfies S1 and S2,

pref(AS)=stab(AS)=pref(AS)=stab(AS)={Arg(Θ)ΘMCS(D)}.

B.2.Grounded semantics for flat frameworks

We first show that the free set exists (see Def. 19).

Lemma 6.

Where Ξ=MCS(D), there is a unique-maximal Δˆ(D) that is contained in Ξ.

Proof.

Let {Δ1,,Δn} be the set of all Δiˆ(D) contained in Ξ. Then, by Fact 12, also Δ=i=1nΔiˆ(D). □

The following lemma shows that the free set in D can be constructed in a bottom-up iterative way.

Lemma 7.

Free(D)=i0Θi where Θ0= and Θi+1 is the set of all rMCS(D) that are triggered by Θi.

Proof.

“⊇”: This follows since by its construction, i0Θiˆ(D) and i0ΘiMCS(D).

“⊆”: Assume for a contradiction that Free(D)i0Θi. By Fact 17, there is a rFree(D)i0Θi that is triggered by i0Θi. But then ri0Θi. This is a contradiction. □

Lemma 8.

For all Δˆ(D), if (ΔFree(D)) then Δ.

Proof.

Suppose Δˆ(D) is consistent. By Lemma 1, there is a ΩMCS(D) such that ΔΩ. Thus, Free(D)Ω and so ΔFree(D) is consistent. □

Lemma 9.

There is no aArg(AS) that attacks some argument in Arg(Free(D)).

Proof.

Suppose some aArg(AS) attacks a bArg(Free(D)). Thus, D(a)head(r) for some rD(b). Thus, (D(a)Free(D)). By Lemma 8, D(a). □

Theorem 11.

Where AS=(L,S,D,K,A) and S satisfies S1 and S2, Arg(Free(D))=groun(AS).

Proof.

“⊇”: Note that groun(AS)A for every preferred extension A of AS. This means that groun(AS)pref(AS) and by Theorem 10, groun(AS)Arg(MCS(D)). Also D[groun(AS)]ˆ(D) and so groun(AS)Arg(Free(D)).

“⊆”: By Lemma 9, Arg(Free(D)) has no attackers in Arg(AS). Thus, trivially Arg(Free(D))groun(AS). □

In view of Theorem 11 and Lemma 9 we have:

Corollary 1.

Where AS=(L,S,D,K,A) and S satisfies S1 and S2, groun(AS) is the set of arguments in Arg(AS) that have no attackers in Arg(AS).

B.3.The prioritized case

In what follows we assume a fixed AS=(L,S,D,K,A,) where S satisfies S1 and S2.

Fact 21.

Where Δ,Θ,Λˆ(D),

  • (1) R[Δ]R[ΔΘ]

  • (2) if R[Δ]R[Λ] and R[Θ]R[ΔΛ] then R[ΔΘ]R[Λ].

We again provide a Lindenbaum-like construction for showing the existence of maximal R-consistent superset of R-consistent sets in ˆ(D).

Lemma 10.

Where Θˆ(D) is R-consistent, there is a maximal R-consistent Δˆ(D) such that ΔΘ.

Proof.

Suppose D={r1,,rn}. For any set of rules Ξ, let the function top(Ξ) return the rule with the lowest index. Our construction is similar to the one in Lemma 1.

We again let tr(Λ) be the set of all rules in D triggered by Λ except those in Λ. Where rtr(Λ) let trS(Λ,r)=df{Λˆ(Λ)Λ triggers r}. Let trR(Λ,r)=dfmax({R[Λ]ΛtrS(Λ,r)}). Finally, let trmax(Λ)=df{rtr(Λ)trR(Λ,r)=max({trR(Λ,r)rtr(Λ)})}. Informally, trmax(Λ) contains those rules triggered by Λ whose strongest trigger sets in Λ are strongest as compared to the strongest trigger sets of other triggered rules. We now construct Δ=dfα0Θi via a transfinite induction (bounded by ω2) as follows: (Θ0;R0;X0)=df(Θ;trmax(Θ);) and, where α is a successor ordinal,

(Θα+1;Rα+1;Xα+1)=df(Θα{top(Rα)};trmax(Θαtop(R));Xα)if not (Θα{top(Rα)})(Θα;Rα{top(Rα)};Xα{top(Rα)})else
and (Θα;Rα+1;Xα+1)=df(β<αΘβ;β<αRβ;β<αXβ), where α is a limit ordinal.
  • (i) We first show (inductively) that each Θα is consistent. For Θ0 this holds by the supposition. For the inductive step consider first a successor ordinal α and suppose Θα is consistent. Then, by the construction also Θα+1 is consistent. Consider now a limit ordinal α and suppose for all β<α, Θβ is consistent. Assume for a contradiction that that Θα is inconsistent. Thus, there is a finite Θ{r}Θα such that Θhead(r). Thus, there is a β<α for which Θ{r}Θβ. But then Θβ is inconsistent in contradiction to our inductive hypothesis.

  • (ii) In view of the construction (and Fact 12), Θαα0 is a monotonically ⊆-increasing sequence of sets in ˆ(D). Also by Fact 12, Δˆ(D).

  • (iii) Our main work now is to show that each Θα is R-consistent for each ordinal α. This can be done inductively, where the base case holds by definition.

For the inductive step we first consider a limit ordinal α. Suppose Θβ is R-consistent for each β<α. Assume for a contradiction that Θα is not R-consistent. Thus, there is a Λˆ(D) such that (ΘαΛ) and for all Θˆ(Θα), R[Λ]>R[Θ] if (ΛΘ). Since (ΘαΛ), by compactness of S there is a finite ΘΘα such that (ΘΛ). Thus, there is a β<α for which ΘΘβ and so (ΘβΛ). Since by the inductive hypothesis, Θβ is R-consistent, there is a Θˆ(Θβ)ˆ(Θα) such that (ΘΛ) and R[Θ]R[Λ], which is a contradiction.

We now consider a successor ordinal α=β+1. Assume for a contradiction that Θα=Θβ{r} is not R-consistent. Therefore there is a Δˆ(D) that is inconsistent with Θα such that (†) for all Θˆ(Θα) that are inconsistent with Δ, R[Δ]>R[Θ]. If (ΔΘβ) then, by the inductive hypothesis, there would be a Θˆ(Θβ)ˆ(Θα) that is inconsistent with Δ and for which R[Θ]R[Δ]. So, ΔΘβ is consistent.

Since (ΘαΔ), there is a Λˆ(ΔΘα) and a rΔΘα for which Λϕ, where head(r)=ϕ. Let P be the corresponding proof.

Let (TopD(P){r})Θα={r1,,rm} and (TopD(P){r})Θα={rm+1,,rn}. For each 1jm there is a R-maximal trigger set Ωjˆ(Θβ). Let Ωj+=Ωj{rj}ˆ(Θα). Also, for each m<jn there is a trigger set Δjˆ(Δ). Let Δj+=Δj{rj}ˆ(Δ). Note that n>m since otherwise Θα.

By Fact 12, j=1mΩj+ˆ(Θα) and j=m+1nΔj+ˆ(Δ). By Fact 21, since (j=1mΩj+Δ) and by (†), R[j=1mΩj+]<R[Δ]R[j=m+1nΔj+].

Recall that Θα=Θβ{r}. Without loss of generality let r=rm. (Note for this that r must be among TopD(P) since otherwise TopD(P)ΘαΘβ and so j=1mΩj+Θβ and hence (ΘβΔ) which was already shown to be impossible.)

Assume now for a contradiction that R[Δj+]>R[Ωm+] for some m<jn. We now show that this means that this would imply that r is not added to Θβ but rather some rΔj+. To see this let Δj+=i=1kΔi as in Fact 16. Note that Δj+Θβ since rjΘα. Thus, there is a minimal 1lk for which ΔlΘβ. Thus, any rΔlΘβ is triggered by Θβ: by if l=0 resp. by Δl1Θβ if l>0. Since not (Θβ{