Leila Amgoud
email: amgoud@irit.fr

Philippe Besnard

Logical limits of abstract argumentation frameworks

Keywords: abstract argumentation frameworks, logic, postulates

, or return arbitrary results. Consequently, Dung's (1995) framework seems problematic when applied over deductive logical formalisms.

Introduction

Argumentation has become an Artificial Intelligence keyword for the last twenty years, especially for handling inconsistency in knowledge bases (e.g., [START_REF] Amgoud | Inferring from inconsistency in preference-based argumentation frameworks[END_REF][START_REF] Besnard | Elements of argumentation[END_REF][START_REF] Simari | A mathematical treatment of defeasible reasoning and its implementation[END_REF], making decisions (e.g., [START_REF] Amgoud | Using arguments for making and explaining decisions[END_REF][START_REF] Bonet | Arguing for decisions: A qualitative model of decision making[END_REF], modelling different types of dialogues between agents like persuasion (e.g., [START_REF] Amgoud | Modelling dialogues using argumentation[END_REF][START_REF] Zabala | Beliefs, reasons and moves in a model for argumentative dialogues[END_REF], negotiation (e.g., [START_REF] Rahwan | Argumentation-based negotiation[END_REF][START_REF] Sycara | Persuasive argumentation in negotiation[END_REF] and inquiry (e.g., [START_REF] Black | An inquiry dialogue system[END_REF][START_REF] Parsons | Properties and complexity of some formal interagent dialogues[END_REF], and for learning concepts (e.g., [START_REF] Amgoud | Agents that argue and explain classifications[END_REF][START_REF] Mozina | Argument based machine learning[END_REF].

One of the most abstract argumentation formalisms in existing literature was proposed by [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. It consists of a set of arguments and a binary relation encoding attacks between these arguments. Semantics are used for defining acceptable sets of arguments, called extensions. Since its original formulation, [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] framework has become very popular because it seriously abstracts away from the application for which it can be used. Indeed, the structure and the origin of arguments and attacks are left unspecified. While this can be seen as a great advantage of the framework, two important questions are raised regarding its interplay with logic -namely, when it is applied for reasoning about inconsistent information:

(1) Is the framework compatible with a logical formalism? To put it differently, is it possible to instantiate 'properly' the framework from a logical knowledge base? (2) Are the semantics significant when the framework is instantiated from a logical knowledge base? Are they really different? What are the counterparts of the extensions (under each semantics) in the knowledge base? Are those counterparts meaningful? What are the plausible inferences under these semantics?

In this paper we answer the above questions. For this purpose, we first propose to fill in the gap between the abstract framework and the logical knowledge base from which it is specified. The idea is to consider all the ingredients involved in an argumentation problem. We start with the notion of an abstract monotonic logic, as defined by [START_REF] Tarski | On some fundamental concepts of metamathematics[END_REF]. According to Tarski, a monotonic logic is a set of formulas and a consequence operator that satisfies some axioms. It is worth mentioning that almost all well-known monotonic logics such as propositional logic, modal logic, first order logic, fuzzy logic and probabilistic logic are special cases of Tarski's notion of abstract logic. Consequently, any result that holds in the general case of a Tarskian logic obviously holds under all of these particular logics. We then show how to build, in a systematic way, arguments from a knowledge base formalised in such a logic.

A 'good' instantiation of [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] framework is one that satisfies some basic rationality postulates. In [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF], three postulates were proposed, and it was shown that not every instantiation is acceptable since some may lead to counterintuitive results. Examples are the instantiations proposed in [START_REF] Prakken | Argument-based extended logic programming with defeasible priorities[END_REF] and [START_REF] Governatori | Argumentation semantics for defeasible logic[END_REF]. The three postulates are tailored for rule-based formalisms, i.e., logical languages that distinguish between strict rules and defeasible ones. In [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF] and [START_REF] Amgoud | Bridging the gap between abstract argumentation systems and logic[END_REF], those postulates were generalised to any Tarskian logic. Moreover, three new and intuitive ones were proposed. We study under which conditions they are satisfied or violated. The satisfaction/violation of a postulate by an instantiation depends mainly on the properties of the attack relation. We show that this relation should be based on the inconsistency of the knowledge base. We show also that symmetric relations cannot be adopted when the knowledge base contains a ternary or n-ary (n > 2) minimal conflict. We do establish the existence of appropriate attack relations. To sum up, there are interesting cases that cannot be captured by [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] framework. Nevertheless, the framework can still be properly instantiated.

In the second part of the paper, we investigate the underpinnings of the main semantics: stable, semi-stable, preferred, grounded and ideal. For this purpose, we consider only the logic-based instantiations that satisfy the postulates, since the remaining ones are not good. For each semantics, we delimit the number of extensions an instantiation may have, characterise its extensions in terms of subsets of the knowledge base over which the instantiation is built, and fully characterise its set of plausible inferences that may be drawn from the knowledge base. The results show that unlike the abstract framework, its good instantiations have a finite number of extensions under stable, semi-stable and preferred semantics. This is particularly the case when the knowledge base is finite. We show that the set of all formulas used in the supports of the arguments of a stable extension is a maximal (for set inclusion) consistent subset of the knowledge base. However, not every maximal consistent subset of the knowledge base necessarily has a corresponding stable extension. This leads to arbitrary plausible inferences. In the case of a full correspondence, stable semantics does not play any role since the same result is already ensured by the naive semantics. This means that stable semantics either returns arbitrary results or provides no added value. Besides, naive semantics either leads to arbitrary results or generalises the coherence-based approach initially developed by [START_REF] Rescher | On inference from inconsistent premises[END_REF]. The situation is worse for preferred semantics. The set of formulas that are used in support of the arguments of a preferred extension is a consistent (but not necessarily maximal for set inclusion) subset of the knowledge base. Thus, arbitrary inferences may be drawn from the knowledge base. Semi-stable extensions are shown to always coincide with stable ones. Thus, semi-stable semantics provides no added value w.r.t. stable semantics. Regarding the ideal and grounded semantics, there are two cases as well. In the first case, both semantics coincide, i.e., the ideal extension of any argumentation framework satisfying the postulates coincides with the grounded extension, which itself coincides with the set of arguments that are built from the free part of a knowledge base, i.e., using the subset of formulas which are not involved in the inconsistency of the knowledge base. Consequently, under these semantics, the set of plausible conclusions is the so-called free consequences in the coherence-based approach for reasoning about inconsistent information [START_REF] Benferhat | Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study part 1: The at case[END_REF]. In the second case, both semantics return arbitrary conclusions.

The overall study reveals that [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] framework can be properly instantiated; i.e., there are instantiations that satisfy some basic rationality postulates. However, stable, semistable, preferred, ideal and grounded semantics are not suitable. Thus, Dung's framework is problematic when applied over a logical formalism, specifically a deductive one.

The paper is structured as follows: Section 2 recalls the abstract argumentation framework of [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. Section 3 details our instantiation of Dung's framework. Section 4 defines rationality postulates that such instantiation should satisfy, and investigates when those postulates are satisfied/violated. Section 5 analyses the different acceptability semantics introduced by Dung. Section 6 compares our contribution with existing works. Finally, Section 7 concludes the paper with some remarks and perspectives.

Dung's (1995) abstract argumentation framework

In [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] An argumentation framework (A, R) is a graph, the nodes of which are the arguments of A and the edges of which are the attacks in R. The arguments are evaluated using a semantics. In [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], different acceptability semantics were proposed. Some of them were refined, for instance in Caminada (2006b) and [START_REF] Dung | Computing ideal skeptical argumentation[END_REF]. The basic idea behind them is the following: for a rational agent, an argument is acceptable if the agent can defend this argument against all attacks upon it. All the arguments jointly acceptable for a rational agent will be gathered in a so-called extension. An extension must satisfy a consistency requirement and must defend all of its elements.

Definition 2 (Conflict-freeness, Defence) Let (A, R) be an argumentation framework and E ⊆ A.

• E is conflict-free iff ∄a, b ∈ E such that (a, b) ∈ R. • E defends an argument a iff ∀ b ∈ A, if (b, a) ∈ R, then ∃c ∈ E such that (c, b) ∈ R.
The following definition recalls the main semantics that were proposed by [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], as well as their refinements (Caminada 2006b;[START_REF] Dung | Computing ideal skeptical argumentation[END_REF]. It is worth noticing that the fundamental semantics features admissible extensions. The other semantics are based on it.

Definition 3 (Acceptability semantics) Let T = (A, R) be an argumentation framework, and E ⊆ A be a conflict-free set.

• E is a naive extension iff it is a maximal (w.r.t. set ⊆) conflict-free set.

• E is an admissible set iff it defends all of its elements.

• E is a complete extension iff it is an admissible set that contains any argument it defends.

• E is a preferred extension iff it is a maximal (w.r.t. set ⊆) admissible set. • E is a stable extension iff it attacks any argument in A \ E.
• E is a semi-stable extension iff it is a complete extension and the union of the set E and the set of all arguments attacked by E is maximal (w.r.t. ⊆). • E is a grounded extension iff it is a minimal (w.r.t. set ⊆) complete extension.

• E is an ideal extension iff it is a maximal (w.r.t. set ⊆) admissible set contained in every preferred extension.

Notations: Ext x (T ) denotes the set of all extensions of T under semantics x where x ∈ {n, p, s, ss} and n (respectively p, s, ss) stands for naive (respectively preferred, stable and semi-stable). When we do not need to refer to a particular semantics, we write Ext(T ) for short. Since grounded and ideal extensions are unique for any argumentation framework T , they will be denoted respectively by GE(T ) and IE(T ).

It is worth recalling that stable extensions are naive (respectively preferred) extensions but that the converse is not always true. Moreover, an argumentation framework has at least one preferred extension, but it may have no stable extensions. When stable extensions exist, they coincide with the semi-stable ones (i.e., if |Ext s (T )| > 0, then Ext s (T ) = Ext ss (T ) for any argumentation framework T ).

Example 4 Let us consider the argumentation framework T = (A, R) such that:

• A = {a, b, c, d, e, f, g}. • R = {(c, b), (b, e), (e, c), (d, c), (a, d), (d, a), (a, f ), ( f, g)}.
This framework has five naive extensions:

• E 1 = {a, c, g}, • E 2 = {d, e, f }, • E 3 = {b, d, f },
• E 4 = {a, e, g}, and

• E 5 = {a, b, g}.
It has one stable/semi-stable extension E 3 and two preferred extensions: E 3 and E 6 = {a, g}. Both the grounded and the ideal extensions are empty, i.e., GE(T ) = IE(T ) = ∅.

An argumentation framework may be infinite, i.e., its set of arguments may be infinite. Consequently, it may have an infinite number of extensions (under a given semantics).

Logic-based instantiations of Dung's (1995) framework

Argumentation is an alternative approach for reasoning with inconsistent information. It follows three main steps: (i) constructing arguments and counterarguments from a logical knowledge base; (ii) defining the status of each argument; and (iii) specifying the conclusions to be drawn from the base. In what follows, we instantiate [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] framework by defining all of these items. We start with an abstract logic as defined by Alfred [START_REF] Tarski | On some fundamental concepts of metamathematics[END_REF], from which the notions of argument and attacks between arguments are defined. [START_REF] Tarski | On some fundamental concepts of metamathematics[END_REF] defines a logic as a pair (L, CN) where the members of L are called well-formed formulas, and CN is a consequence operator. No constraints are defined on the logical language L. Thus, no particular connectors are required. However, the consequence operator CN is a function from 2 L to 2 L that should satisfy the following axioms:

Tarski's (1956) abstract consequence operators

(1) X ⊆ CN(X ) (Expansion) (2) CN(CN(X )) = CN(X ) (Idempotence) (3) CN(X ) = Y ⊆ f X CN(Y ) (Compactness) (4) CN({x}) = L for some x ∈ L (Absurdity) (5) CN(∅) = L (Coherence) Notations: Y ⊆ f X means that Y is a finite subset of X .
Intuitively, CN(X ) returns the set of formulas that are logical consequences of X according to the logic in question. In [START_REF] Tarski | On some fundamental concepts of metamathematics[END_REF], it was shown that CN is a closure operator, that is, CN enjoys properties such as:

Property 5 Let X, X ′ , X ′′ ⊆ L. (1) X ⊆ X ′ ⇒ CN(X ) ⊆ CN(X ′ ). (2) CN(X ) ∪ CN(X ′ ) ⊆ CN(X ∪ X ′ ). (3) CN(X ) = CN(X ′ ) ⇒ CN(X ∪ X ′′ ) = CN(X ′ ∪ X ′′ ). (4) CN(X ∩ X ′ ) ⊆ CN(X ) ∩ CN(X ′ ).
Almost all well-known monotonic logics (classical logics, intuitionistic logics, modal logics, etc.) can be viewed as special cases of Tarski's notion of an abstract logic. AI introduced non-monotonic logics, which do not satisfy monotonicity [START_REF] Bobrow | Special issue on non-monotonic reasoning[END_REF].

Once (L, CN) is fixed, a notion of consistency arises as follows:

In simple English, this says that X is consistent iff its set of consequences is not the set of all formulas. The coherence requirement (absent from Tarski's original proposal but added here to avoid considering trivial systems) forces the empty set ∅ to always be consistentthis makes sense for any reasonable logic.

One can show that if a set X is consistent, then its closure under CN is also consistent and any proper subset of X is consistent.

Property 7 Let X ⊆ L. (1) If X is consistent, then CN(X ) is consistent as well. (2) ∀X ′ ⊆ X , if X is consistent, then X ′ is consistent. (3) ∀X ′ ⊆ X , if X ′ is inconsistent, then X is inconsistent. If a set X ⊆ L of formulas is inconsistent, this means that it contains minimal conflicts. Definition 8 (Minimal conflict) A set C ⊆ L is a minimal conflict iff: • C is inconsistent. • ∀x ∈ C, C\{x} is consistent. Notations: Let X ⊆ L. C X denotes the set of all minimal conflicts C such that C ⊆ X .
Max(X ) is the set of all maximal (for set inclusion) consistent subsets of X , Free(X ) = S i ∈Max(X ) S i , and Inc(X ) = X \ Free(X ).

The following properties are useful for proving our results.

Property 9 For all X ⊆ ⊆ L,

• if X is consistent then C X = ∅; • if X is consistent then X ⊆ S for some S ∈ Max( );
• if X is inconsistent then there exists at least one minimal conflict C such that C ⊆ X .

The next property is true in the case that the underlying logic is adjunctive. Let us first define this new concept.

Definition 10 (Adjunctiveness) A logic (L, CN) is adjunctive iff for all x and y in L, there exists z ∈ L such that CN({z}) = CN({x, y}).

Intuitively, an adjunctive logic infers, from the union of two formulas {x, y}, some formula(s) that can be inferred neither from x alone nor from y alone (except, of course, when y ensues from x or vice versa). In fact, most well-known logics are adjunctive. 1 A logic which is not adjunctive could for instance fail to deny x ∨ y from the premises {¬x, ¬y}.

Property 11 Let (L, CN) be adjunctive, C ⊆ L be a minimal conflict. For all X ⊂ C, if X = ∅, then: (1) ∃x ∈ L such that CN({x}) = CN(X ). (2) ∃x 1 ∈ CN(X ) and ∃x 2 ∈ CN(C \ X ) such that the set {x 1 , x 2 } is inconsistent.

Tarskian logic-based instantiations

Let (L, CN) be a fixed abstract logic. From now on, we will consider a knowledge base , which is a subset of the logical language L (in symbols, ⊆ L). This base may be infinite, however, with no loss of generality and for the sake of simplicity, it is assumed to be free of tautologies: Assumption 12 Let be a knowledge base. For all x ∈ , x / ∈ CN(∅).

The first parameter of an argumentation framework is the set of arguments. In [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] framework, an argument is an abstract entity. In what follows, it is built from a knowledge base . It gives a reason for believing a conclusion. Formally, an argument satisfies three main requirements: (i) the reason is a subset of the knowledge base, thus restricting the origin of the arguments; (ii) the reason should be consistent, thus avoiding absurd reasons; and (iii) the reason is minimal. The third requirement means that only relevant information w.r.t. the conclusion is considered.

Definition 13 (Argument) Let be a knowledge base. An argument is a pair (X, x) such that:

(1) X ⊆ and x ∈ L.

(2) X is consistent.

(3) x ∈ CN(X ). (4) ∄X ′ ⊂ X such that x ∈ CN(X ′ ). An argument (X, x) is a sub-argument of another argument (X ′ , x ′ ) iff X ⊆ X ′ .
Let us introduce some notations that will be used throughout the paper.

Notations: Supp and Conc are two functions that return respectively the support X and the conclusion x of an argument (X, x). Sub is a function that returns all the sub-arguments of a given argument. For X ⊆ L, Arg(X ) denotes the set of all arguments that can be built from X by means of Definition 13. For a set E of arguments, Concs(E) = {Conc(a) | a ∈ E} and Base(E) = a∈E Supp(a).

The following property shows that the conclusion of any argument is consistent.

Property 14 For all (X, x) ∈ Arg( ), the set {x} is consistent.

Due to Assumption 12 (x ∈ CN(∅) for all x ∈ ), it can also be shown that each consistent formula in gives birth to an argument: Property 15 Let be a knowledge base such that for all x ∈ , x ∈ CN(∅). For all x ∈ such that the set {x} is consistent, ({x}, x) ∈ Arg( ).

Since CN is monotonic, constructing arguments is a monotonic process; additional knowledge never causes the set of arguments to shrink but only gives rise to extra arguments that may interact with the existing ones.

Property 16 Arg( ) ⊆ Arg( ′ ) whenever ⊆ ′ ⊆ L.

We show now that any proper subset of a minimal conflict is the support of at least one argument. This is particularly so in the case of adjunctive logics. This result is of utmost importance as regards encoding the attack relation.

Proposition 17 Let (L, CN) be adjunctive and be a knowledge base. For all nonempty proper subsets X of some minimal conflict C ∈ C , there exists a ∈ Arg( ) such that Supp(a) = X .

Proposition 17 is fundamental because it says that if statements from contradict others then it is always possible to define an argument exhibiting the conflict.

In the sequel, we use the term system instead of framework in order to distinguish the framework of [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] from its logical instantiations, which are defined as follows.

Definition 18 (Argumentation system) Let (L, CN) be a given Tarskian logic and ⊆ L be a knowledge base. An argumentation system over is a pair T = (Arg( ), R) such that R ⊆ Arg( ) × Arg( ) (intuitively, it is an attack relation).

In the previous definition, the attack relation is left unspecified. However, in Section 4 we show that it should be assigned some properties, otherwise the system may return counter-intuitive results.

The arguments of a system T = (Arg( ), R) are evaluated using one of the semantics given in Definition 3. Recall that the structure of arguments is not taken into account in those semantics. The extensions are used in order to define the conclusions that may be drawn from according to the system T . The idea is to conclude x if it is the conclusion of an argument in every extension of the system.

Definition 19 (Output) Let T = (Arg( ), R) be an argumentation system over a knowledge base and Ext(T ) its set of extensions under a given semantics. For x ∈ L, x is a conclusion of T iff ∀E i ∈ Ext(T ), ∃a ∈ E i such that Conc(a) = x. We write Output(T ) to denote the set of all conclusions of T .

It follows immediately from the definition that the set of conclusions exactly consists of the formulas which happen to be, in each extension, the conclusion of an argument of the extension.

Property 20 Let T = (Arg( ), R) be an argumentation system over a knowledge base and Ext(T ) its set of extensions under a given semantics. It holds that

Output(T ) = E i ∈Ext(T ) Concs(E i ).
Finally, it is obvious that the outputs of an argumentation system are consequences of the corresponding knowledge base under the consequence operator CN.

Property 21 Let T = (Arg( ), R) be an argumentation system over a knowledge base . Output(T ) ⊆ CN( ).

On the quality of logic-based argumentation systems

We have shown so far how to build an argumentation system from a logical knowledge base. The system is still incomplete since the attack relation is not specified. As already mentioned, [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] is silent on how to proceed in order to obtain a reasonable R in practice. It happens that it is in fact a delicate step. We will show next that the choice of this relation is crucial for the 'soundness' of the system. Soundness is determined by some rationality postulates that any system should satisfy.

The first work on rationality postulates in argumentation was undertaken by [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF]. The authors focused only on rule-based systems (i.e., systems that distinguish between strict and defeasible rules in their underlying logical language). They proposed the following postulates that such systems should satisfy:

• Closure: the idea is that if a system concludes x and there is a strict rule 2 x → y, then the system should also conclude y. • Direct consistency: the set of conclusions of arguments of each extension should be consistent. • Indirect consistency: the closure of the set of conclusions of arguments of each extension should be consistent.

As obvious as they may appear, these postulates are violated by most rule-based systems (such as [START_REF] Amgoud | Towards a consensual formal model: inference part[END_REF][START_REF] Governatori | Argumentation semantics for defeasible logic[END_REF][START_REF] Prakken | An abstract framework for argumentation with structured arguments[END_REF][START_REF] Prakken | Argument-based extended logic programming with defeasible priorities[END_REF]. Besides, they are tailored for rule-based logics. Their counterparts for any Tarskian logic were defined in [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF] and [START_REF] Amgoud | Bridging the gap between abstract argumentation systems and logic[END_REF]. Moreover, three new postulates were proposed in [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF]. In what follows, we recall all the postulates that are necessary for our study.

Rationality postulates for logic-based argumentation systems

The first rationality postulate that an argumentation system should satisfy concerns the closure of its output. The basic idea is that the conclusions of a formalism should be 'complete'. There should be no case where a user performs some extra reasoning on her own to derive statements that the formalism apparently 'forgot' to entail. In [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF], closure is defined for rule-based argumentation systems. In what follows, we extend this postulate to systems that are grounded in any Tarskian logic. The idea is to define closure using the consequence operator CN.

Postulate 22 (Closure under CN) Let T = (Arg( ), R) be an argumentation system over a knowledge base . For all E ∈ Ext(T ), Concs(E) = CN(Concs(E)). We say that T is closed under CN.

In [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF], closure is imposed both on the extensions of a system and on its output set. The next result shows that the closure of the output set does not deserve to be a separate postulate since it immediately follows from the closure of extensions.

Proposition 23 Let T = (Arg( ), R) be an argumentation system over a knowledge base . If T is closed under CN, then Output(T ) = CN(Output(T )).

The second rationality postulate concerns sub-arguments. An argument may have one or several sub-arguments, reflecting the different premises on which it is based. Thus, the acceptance of an argument should also imply the acceptance of all of its sub-parts.

Postulate 24 (Closure under sub-arguments) Let T = (Arg( ), R) be an argumentation system over a knowledge base . For all E ∈ Ext(T ), if a ∈ E, then Sub(a) ⊆ E. We say that T is closed under sub-arguments.

These two postulates have a great impact on the extensions of an argumentation system, as shown by the following result:

Proposition 25 Let T = (Arg( ), R) be an argumentation system over a knowledge base . If T is closed under sub-arguments and under CN, then for all E ∈ Ext(T ),

Concs(E) = CN(Base(E)).
The third rationality postulate concerns the consistency of the results. It ensures that the set of conclusions supported by each extension is consistent. The following postulate generalises the direct consistency postulate, which was proposed for rule-based argumentation systems in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF]:

Postulate 26 (Consistency) Let T = (Arg( ), R) be an argumentation system over a knowledge base . For all E ∈ Ext(T ), Concs(E) is consistent. We say that T satisfies consistency.

As for closure, in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF] a postulate imposing the consistency of the output is defined. We show next that such a postulate is not necessary. Indeed, an argumentation system that satisfies Postulate 26 necessarily has a consistent output.

Proposition 27 If an argumentation system T = (Arg( ), R) satisfies consistency, then the set Output(T ) is consistent.

We show next that argumentation systems that satisfy both consistency and closure under sub-arguments enjoy a strong version of consistency. Indeed, the set of formulae used in the arguments of each extension is consistent. It is worth mentioning that this result is very general, as it holds under any semantics, any attack relation and any Tarskian logic.

Proposition 28 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that for all x ∈ , x / ∈ CN(∅). If T satisfies consistency and is closed under sub-arguments, then for all E ∈ Ext(T ), Base(E) is consistent.

Since the free formulas of a knowledge base (i.e., the ones that are not involved in any minimal conflict) are the 'hard' part in the base, it is natural that any argument that is built only from this part should be in every extension of an argumentation system built over the knowledge base.

Postulate 29 (Free Precedence) Let T = (Arg( ), R) be an argumentation system over a knowledge base . For all E ∈ Ext(T ), Arg(Free( )) ⊆ E. We say that T satisfies free precedence.

We show next that the free formulas are drawn by any argumentation system satisfying Postulate 29.

Proposition 30 Let T = (Arg( ), R) be an argumentation system over a knowledge base . If T satisfies free precedence, then Free( ) ⊆ Output(T ) (under any of the reviewed semantics).

The last postulate says that if the support and the conclusion of an argument are part of the conclusions of a given extension, then the argument should belong to the extension. Informally: if each step in the argument is good enough to be in the extension, then so is the argument itself.

Postulate 31 (Exhaustiveness) An argumentation system T = (Arg( ), R) over a knowledge base satisfies exhaustiveness iff for all E ∈ Ext(T ), for all (X, x) ∈ Arg( ), if X ∪ {x} ⊆ Concs(E), then (X, x) ∈ E.

The following result shows that when this postulate is satisfied, then extensions are closed in terms of arguments.

Proposition 32 If an argumentation system T is closed under both CN and sub-arguments and satisfies the exhaustiveness postulate, then ∀E ∈ Ext(T ), E = Arg(Base(E)) (under any of the reviewed semantics).

The five postulates are generally independent. However, in the case of naive and stable semantics, closure under the consequence operator CN is induced from closure under subarguments and consistency. This is particularly the case when the attack relation is based on inconsistency.

Definition 33 (Conflict-dependent) An attack relation R is conflict-dependent iff for all a, b ∈ Arg( ), if aRb then Supp(a) ∪ Supp(b) is inconsistent.
The above definition says that R should show no attack from a to b unless provides evidence (according to CN) that the supports of a and b conflict with each other. That is, being conflict-dependent ensures that, when passing from to (Arg( ), R), no conflict is 'invented' in R. Note that all the attack relations that are used in existing structured argumentation systems are conflict-dependent (see [START_REF] Gorogiannis | Instantiating abstract argumentation with classical logic arguments: Postulates and properties[END_REF], for a summary of existing relations).

Proposition 34 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. If T satisfies consistency and is closed under sub-arguments (under naive and stable semantics), then it is closed under CN (under naive and stable semantics).

It was shown in [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF] that the five postulates are compatible, i.e., they can be satisfied altogether by an argumentation system. This is particularly witnessed in the argumentation system studied in [START_REF] Cayrol | On the relation between argumentation and non-monotonic coherence-based entailment[END_REF]. This system is grounded in propositional logic (a Tarskian logic) and uses the assumption attack relation defined in [START_REF] Elvang-Gøransson | Acceptability of arguments as 'logical uncertainty[END_REF]. According to this relation, an argument attacks another if its conclusion is the negation of an element of the support of the second argument. This relation was generalised to any Tarskian logic in [START_REF] Amgoud | A formal analysis of logic-based argumentation systems[END_REF] as follows:

Definition 35 (Assumption attack relation) Let (L, CN) be a Tarskian logic. An argument (X, x) attacks another argument (X ′ , x ′ ) iff ∃y ∈ X ′ such that the set {x, y} is inconsistent. This relation will be denoted by R as .

It was shown in Amgoud ( 2012) that any argumentation system (Arg( ), R as ) satisfies the five postulates. This is certainly a positive result as it shows that [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] abstract framework can be correctly instantiated with logical formalisms. However, in the next section we show that there is a broad class of natural instantiations that are not possible since they violate the postulates.

On the violation of consistency postulate

In subsection 3.2 we provided a clear definition of an argument and how it is built from a knowledge base . However, there is still no indication on how the attack relation R is chosen and how it is related to . Moreover, in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF] it was shown that there are some instantiations of [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] framework that violate the consistency postulate. This means that the choice of the attack relation has a direct impact on the postulates. This also means that conflict-freeness is not sufficient to ensure consistency. Thus, an attack relation should enjoy some basic properties. The first one concerns its origin. We show that an attack relation should be based on inconsistency, and thus conflictdependent.

When the attack relation is conflict-dependent, then it is empty when the knowledge base is consistent.

Proposition 36 Let (Arg( ), R) be such that R is conflict-dependent. If is consistent, then R = ∅.
It follows that when the attack relation is conflict-dependent, if a set of arguments is such that its corresponding base (set-theoretic union of supports) is consistent then it is a conflict-free set:

Proposition 37 Let (Arg( ), R) be such that R is conflict-dependent. ∀E ⊆ Arg( ), if Base(E) is consistent, then E is conflict-free.
It is also worth pointing out that an attack relation which is conflict-dependent exhibits no self-attacks.

Proposition 38 Let (Arg( ), R) be such that R is conflict-dependent. For all a ∈ Arg( ), (a, a) ∈ R.

Let us now consider the following example of an argumentation system that is built from a propositional knowledge base and uses the symmetric attack relation known as rebut [START_REF] Elvang-Gøransson | Acceptability of arguments as 'logical uncertainty[END_REF]. According to this relation, an argument a attacks another argument b iff Conc(a) ≡ ¬Conc(b) (in the case that (L, CN) is propositional logic). This relation will be denoted by R r e .

Example 39 Let (L, CN) be propositional logic and = {x, y, x → ¬y}. Let us consider the following set of arguments:

• a 1 = ({x}, x). • a 2 = ({y}, y). • a 3 = ({x → ¬y}, x → ¬y). • a 4 = ({x, x → ¬y}, ¬y). • a 5 = ({y, x → ¬y}, ¬x). • a 6 = ({x, y}, x ∧ y).
The rebut relation is as follows: {(a 1 , a 5 ), (a 5 , a 1 ), (a 2 , a 4 ), (a 4 , a 2 ), (a 3 , a 6 ), (a 6 , a 3 )}. The set {a 1 , a 2 , a 3 } -as a finite representation [START_REF] Amgoud | Identifying the core of logic-based argumentation systems[END_REF] for all of its 'mates', i.e., the arguments ({x}, . . .) and ({y}, . . .) and ({x → ¬y}, . . .) -is an admissible extension of the system (Arg( ), R r e ). However, the set {Conc(a 1 ), Conc(a 2 ), Conc(a 3 )} is inconsistent. Similarly, the set {a 4 , a 5 , a 6 } is (a finite representation of) another admissible extension whose set of conclusions is inconsistent.

This example shows that an admissible set of arguments may fail to have a consistent set of conclusions. The problem encountered with the rebut relation is due to the fact that it is binary, in compliance with [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] definitions of the attack relation as binary. Thus, the ternary conflict between a 1 , a 2 and a 3 is not captured. Particularly, symmetric attack relations are crippled by non-binary minimal conflicts. Indeed, we show that when the attack relation is symmetric, Postulate 26 is violated.

Proposition 40 Let (L, CN) be adjunctive and be a knowledge base such that ∃C ∈ C and |C| > 2. If R is conflict-dependent and symmetric, then the argumentation system (Arg( ), R) violates consistency.

This result shows a broad class of attack relations that cannot be used in argumentation: the symmetric ones. Relations like rebut or a union of rebut and any other conflict-dependent attack relation would lead to the violation of consistency, namely when there exist n-ary (n > 2) minimal conflicts in the knowledge base. Consequently, the symmetric systems studied in [START_REF] Coste | Symmetric argumentation frameworks[END_REF] cannot be adopted in a concrete application.

The outcomes of logic-based argumentation systems

The aim of this section is to investigate the underpinnings of the different acceptability semantics introduced in Dung (1995), [START_REF] Dung | Computing ideal skeptical argumentation[END_REF], and Caminada (2006b) and to check whether they make sense in a concrete application. Recall that those semantics are defined without considering either the internal structure or the origin of arguments and attacks. In this section, we fully characterise for the first time both the extensions and the output set of any Tarskian logic-based argumentation system under naive, stable, semi-stable, preferred, grounded and ideal semantics. For this purpose, we consider only systems that enjoy the rationality postulates introduced in the previous section (as the other systems are regarded as ill-fated instantiations of Dung's 1995 framework).

Naive semantics

In this section, we characterise the outputs of an argumentation system under naive semantics. We show that the naive extensions of any argumentation system that satisfies consistency and closure under sub-arguments always return maximal (for set inclusion) consistent subsets of .

Theorem 41 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. If T satisfies consistency and is closed under subarguments (under naive semantics), then:

• For all E ∈ Ext n (T ), Base(E) ∈ Max( ). • For all E ∈ Ext n (T ), E = Arg(Base(E)). • For all E i , E j ∈ Ext n (T ), if Base(E i ) = Base(E j ) then E i = E j .
The next theorem confirms that any maximal consistent subset of defines a naive extension of an argumentation system which satisfies consistency and closure under subarguments. This is the case when the logic (L, CN) is adjunctive.

Theorem 42 Let (L, CN) be adjunctive. Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. If T satisfies consistency and is closed under sub-arguments (under naive semantics), then:

• For all S ∈ Max( ), Arg(S) ∈ Ext n (T ). • For all S i , S j ∈ Max( ), if Arg(S i ) = Arg(S j ) then S i = S j .
• For all S ∈ Max( ), S = Base(Arg(S)).

It follows that any argumentation system that satisfies the two postulates 24 and 26 enjoys a full correspondence between the maximal consistent subsets of and the naive extensions of the system.

Corollary 43 Let (L, CN) be adjunctive. Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. T satisfies consistency and is closed under sub-arguments (under naive semantics) iff there is a bijection between the naive extensions of T and the elements of Max( ).

A direct consequence of the previous result is that the number of naive extensions of an argumentation system is less than or equal to the number of maximal consistent sub-bases of the knowledge base over which the system is built. Thus, if the knowledge base is finite, then the system has a finite number of naive extensions.

Corollary 44 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under sub-arguments (under naive semantics).

• |Ext n (T )| ≤ |Max( )|.
• If is finite, then T has a finite number of naive extensions.

The following result characterises the case where an argumentation system has an empty naive extension. It shows that the knowledge base contains only inconsistent formulae.

Corollary 45 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under sub-arguments (under naive semantics). If Ext n (T ) = {∅}, then for all x ∈ , CN({x}) is inconsistent.

Let us now characterise the set of inferences that may be drawn from a knowledge base by any argumentation system under naive semantics. It coincides with the set of inferences that are drawn from some maximal consistent subsets of .

Theorem 46 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under sub-arguments (under naive semantics). Output(T ) = CN(S i ) where S i ranges over

{S i ∈ Max( ) | ∃E i ∈ Ext n (T ) and S i = Base(E i )}.
When the number of naive extensions of an argumentation system is less than the number of maximal consistent subsets of the knowledge base over which the system is built, the system returns arbitrary conclusions.

Example 47 Assume that (L, CN) is non-adjunctive, = {x, ¬x ∧ y} and that this base has two maximal consistent subsets:

• S 1 = {x}. • S 2 = {¬x ∧ y}.
According to Theorem 41, any argumentation system T = (Arg( ), R) satisfying the postulates and whose attack relation R is conflict-dependent will have one or two naive extensions:

E 1 = Arg(S 1 ) and E 2 = Arg(S 2 ). Assume that Ext n (T ) = {E 1 }. It follows that x ∈ Output(T ) and ¬x / ∈ Output(T ). If Ext n (T ) = {E 2 }, x /
∈ Output(T ) and ¬x ∈ Output(T ). Both results are arbitrary.

In the case of adjunctive logics, the output of an argumentation system is the set of conclusions that follow from all the maximal consistent subsets of .

Corollary 48 Let (L, CN) be adjunctive. Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under sub-arguments (under naive semantics).

Output(T ) = S i ∈Max( ) CN(S i ).
Example 47 (Cont): Assume now that (L, CN) is propositional logic (which is adjunctive). The base = {x, ¬x ∧ y} has two maximal consistent subsets:

• S 1 = {x}. • S 2 = {¬x ∧ y}.
According to Corollary 43, any argumentation system T = (Arg( ), R) satisfying the postulates and whose attack relation R is conflict-dependent will have exactly two naive extensions: Arg(S 1 ) and Arg(S 2 ). Moreover, Output(T ) = CN(S 1 ) ∩ CN(S 2 ).

In short, under naive semantics, any 'good' instantiation of [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] abstract framework returns exactly the formulas that are drawn (with CN) by all the maximal consistent subsets of the knowledge base . So whichever attack relation is chosen, the result will be the same. It is worth recalling that the output set contains exactly the so-called universal conclusions in the coherence-based approach developed in [START_REF] Rescher | On inference from inconsistent premises[END_REF] for reasoning from inconsistent propositional bases. Indeed, Rescher and Manor take as input a (possibly inconsistent) propositional knowledge base, then compute all of its maximal (for set inclusion) consistent subsets. The universal conclusions to be drawn from the base are the formulae that follow logically from all of these subsets. Thus, argumentation systems generalise (under naive semantics) this approach to any adjunctive Tarskian logic. As a consequence, the argumentation approach is syntax-dependent, and may thus lead to undesirable results, as discussed in the following example.

Example 47 (Cont): Assume again that (L, CN) is propositional logic. Thus, Output(T ) = CN(S 1 ) ∩ CN(S 2 ). Note that y / ∈ Output(T ). Assume that x stands for 'Sunny day' and y for 'It is cloudy'. The fact that y / ∈ Output(T ) seems reasonable. Assume now that y stands for 'The temperature is 18 degrees'. In this case, y should be inferred from according to the idea that it is not part of the conflict.

Should ¬x ∧ y instead be written as two formulas, namely ¬x and y, then y is out of the conflict and is inferred.

Figure 1 summarises the main results under naive semantics.

Stable and semi-stable semantics

We show that the stable extensions of any argumentation system satisfying consistency and closure under sub-arguments return maximal consistent subsets of . This means that if one instantiates [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] framework and does not get maximal consistent subsets with stable extensions, then the instantiation certainly violates one or both of the two key postulates: consistency and closure under sub-arguments.

Theorem 49 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. If T satisfies consistency and closure under sub-arguments (under stable semantics) and Ext s (T ) = ∅, then:

• For all E ∈ Ext s (T ), Base(E) ∈ Max( ). • For all E ∈ Ext s (T ), E = Arg(Base(E)). • For all E i , E j ∈ Ext s (T ), if Base(E i ) = Base(E j ) then E i = E j .
This result characterises the stable extensions of a large class of argumentation systems, namely the ones that are built using (adjunctive and non-adjunctive) Tarskian logics. However, it does not guarantee that each maximal consistent subset of has a corresponding stable extension in an argumentation system T = (Arg( ), R). To put it differently, it does not guarantee a bijection from the set Ext s (T ) to the set Max( ). The bijection (thus the equality |Ext s (T )| = |Max( )|) broadly depends on the attack relation that is chosen.

Let ℜ s be the set of all attack relations that ensure the postulates under stable semantics:

ℜ s = ⊆L {R ⊆ Arg( ) × Arg( ) | R is conflict-dependent and (Arg( ), R)
satisfies Postulates 22, 24, 26, 29 and 31 under stable semantics}.

This set contains three disjoint subsets of attack relations:

ℜ s = ℜ s 1 ∪ ℜ s 2 ∪ ℜ s 3 : • ℜ s 1 : the relations which lead to |Ext s (T )| = 0. • ℜ s 2 : the relations which ensure 0 < |Ext s (T )| < |Max( )|. • ℜ s 3 : the relations which ensure |Ext s (T )| = |Max( )|.
Let us analyse each category of attack relations in turn. The following result shows that the set ℜ s 1 is empty, meaning that there is no attack relation which prevents the existence of stable extensions. In other words, any argumentation system satisfying the rationality postulates has at least one stable extension. It is worth recalling that in the general case, [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] has shown that stable semantics does not guarantee the existence of extensions. This was considered a weakness of this semantics.

Theorem 50 It holds that ℜ s1 = ∅.
What about the attack relations of the category ℜ s 2 ? Systems that use these relations choose a proper subset of the maximal consistent subsets of and make inferences from them. Their output sets are as follows:

Theorem 51 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s 2 . Output(T ) = CN(S i ) where S i ranges over {S i ∈ Max( ) | ∃E i ∈ Ext s (T ) and S i = Base(E i )}.
These attack relations lead to an unjustified discrimination between maximal consistent subsets of a knowledge base. Unfortunately, this is fatal for the argumentation systems which use them as they may return arbitrary results. Note that the situation is similar to the one encountered under naive semantics when the logic is non-adjunctive (see Example 47).

Attack relations of the category ℜ s3 induce a one-to-one correspondence between the stable extensions of an argumentation system and the maximal consistent subsets of the knowledge base over which it is built.

Theorem 52 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s3 . For all S ∈ Max( ), Arg(S) ∈ Ext s (T ).

The stable extensions of any argumentation system using an attack relation of the category ℜ s3 coincide with the naive extensions. They even coincide with the preferred extensions of the system, meaning that this system is coherent [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF].

Theorem 53 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s3 . The equality Ext n (T ) = Ext s (T ) holds. If T satisfies the postulates under preferred semantics, then Ext s (T ) = Ext p (T ).

An argumentation system using an attack relation of this category leads to exactly the same result under naive semantics. It returns the universal conclusions (of the coherencebased approach) under any monotonic logic as opposed to only propositional logic, as in [START_REF] Rescher | On inference from inconsistent premises[END_REF]. Finally, it is worth mentioning that the set ℜ s3 is not empty. Indeed, the assumption attack relation (R as ) recalled in Definition 35 is one of its elements. In [START_REF] Cayrol | On the relation between argumentation and non-monotonic coherence-based entailment[END_REF], it was shown that there is a full correspondence between the stable extensions of an argumentation system (defined over propositional logic) and the maximal consistent subsets of the propositional knowledge base over which it is built. This result was generalised to any Tarskian logic in [START_REF] Amgoud | A formal analysis of logic-based argumentation systems[END_REF]. Consequently, any argumentation system using R as is coherent.

Corollary 54 For all ⊆ L, the argumentation system T = (Arg( ), R as ) is coherent.

From the previous results, it follows that any argumentation system satisfying the four postulates has stable extensions. Moreover, it is possible to delimit their maximum number.

Corollary 55 Let T = (Arg( ), R) be an argumentation system over a base such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence (under stable semantics). It holds that

0 < |Ext s (T )| ≤ |Max( )|.
It follows that when the knowledge base is finite, the number of stable extensions is finite as well.

Corollary 56 If is finite, then the set Ext s (T ) is finite, whenever T = (Arg( ), R) satisfies consistency and closure under sub-arguments (under stable semantics).

To sum up, there are two possible categories of attack relations that lead to the satisfaction of the rationality postulates: ℜ s 2 and ℜ s 3 . Relations of ℜ s 2 should be avoided as they lead to arbitrary results. Relations of ℜ s 3 lead to 'correct' results, but argumentation systems based on them return exactly the same results under naive semantics. This means that stable semantics does not play any particular role in the logic-based argumentation systems studied in the paper. Thus, stable semantics either leads to undesirable results or provides no added value w.r.t. naive semantics. Figure 2 summarises the different situations that may be encountered under this semantics.

From the definitions of the two categories ℜ s2 and ℜ s3 , stable extensions exist. Besides, it was shown in Caminada (2006b) that when this is the case, semi-stable extensions coincide with the stable ones.

Corollary 57 Let T = (Arg( ), R) be an argumentation system over a base such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence (under stable semantics). The equality Ext s (T ) = Ext ss (T ) holds.

Thus, in practice semi-stable semantics does not offer added value w.r.t. stable semantics, which is itself problematic.

Preferred semantics

Preferred semantics was mainly proposed in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] as an alternative to stable semantics, since the latter does not guarantee (for abstract frameworks) the existence of extensions. In this section, we study the outcomes of logic-based argumentation systems under preferred semantics and check whether it offers added value w.r.t. stable semantics in the context of handling inconsistency in knowledge bases.

We have previously shown in Proposition 28 that the extensions (under any admissibilitybased semantics) of an argumentation system satisfying the postulates are made up of consistent subsets of the knowledge base over which the system is defined. Thus, the subset Base(E) computed from any preferred extension E is a subset of maximal consistent subbase of the knowledge base at hand.

Theorem 58 Let T = (Arg( ), R) be an argumentation system such that R is conflictdependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). For all E ∈ Ext p (T ), there exists S ∈ Max( ) such that Base(E) ⊆ S.

Unlike stable extensions, the subsets of a knowledge base that are computed from preferred extensions are not necessarily maximal (for set inclusion). This is due to the existence of undecided arguments under preferred semantics. In Caminada (2006a) another way of defining [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] semantics was provided. It consists of labelling the nodes of the graph corresponding to the argumentation system with three possible values: {in, out, undec}.An argument is labelled in iff all of its attackers are labelled out, and labelled out iff one of its attackers is labelled in. Finally, it is labelled undec iff it is not possible to assign either in or out. When the subset of which is computed from a preferred extension is not maximal then some formulae of appear only in support of undecided arguments.

This does not mean that a preferred extension can never return a maximal consistent subset. Remember that stable extensions exist, thus, there is at least one preferred extension whose base is maximal for set inclusion.

Corollary 59 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence (under preferred semantics). There exists E ∈ Ext p (T ) such that Base(E) ∈ Max( ).

The following result shows that the subsets computed from the preferred extensions of an argumentation system are pairwise different.

Theorem 60 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). For all

E i , E j ∈ Ext p (T ), if Base(E i ) ⊆ Base(E j ) then E i = E j .
We show that every maximal consistent subset of a knowledge base is captured by at most one preferred extension.

Theorem 61 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). Let S ∈ Max( ). For all

E i , E j ∈ Ext p (T ), if Base(E i ) ⊆ S and Base(E j ) ⊆ S, then E i = E j .
The previous result allows us to delimit the maximum number of preferred extensions a system may have. Like stable semantics, it is the number of maximal (for set inclusion) consistent subsets of the knowledge base at hand.

Theorem 62 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). It holds that

1 ≤ |Ext p (T )| ≤ |Max( )|.
When a knowledge base is finite, each argumentation system enjoying the rationality postulates has a finite number of preferred extensions.

Corollary 63 If a knowledge base is finite, then for all T = (Arg( ), R) such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics), Ext p (T ) is finite.

Let us characterise the inferences that are drawn from a knowledge base by an argumentation system T satisfying the rationality postulates under preferred semantics. Let ℜ p be the set of all attack relations that ensure the postulates under preferred semantics:

ℜ p = ⊆L {R ⊆ Arg( ) × Arg( ) | R is conflict-dependent and (Arg( ), R)
satisfies Postulates 22, 24, 26, 29 and 31 under preferred semantics} .

In his seminal paper, [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] has shown that the stable extensions of an argumentation system are also preferred extensions of the system. Consequently, the set ℜ p is a subset of ℜ s .

Property 64 It holds that ℜ p ⊆ ℜ s .

The set ℜ p thus contains three disjoint subsets of attack relations:

ℜ p = ℜ p 1 ∪ℜ p 2 ∪ℜ p 3 : • ℜ p 1 : the relations which are in ℜ p ∩ ℜ s 1 . • ℜ p 2 : the relations which are in ℜ p ∩ ℜ s 2 . • ℜ p 3 : the relations which are in ℜ p ∩ ℜ s 3 .
Let us analyse each category of attack relations in turn. The first set is empty (i.e., ℜ p 1 = ∅) since we have shown previously that there is no attack relation which prevents an argumentation system from having stable extensions (ℜ s 1 = ∅).

Attack relations of the category ℜ p 3 lead to coherent argumentation systems (their stable extensions coincide with the preferred extensions) as shown in Theorem 53. Moreover, the preferred extensions coincide with the naive ones, meaning that preferred semantics provides no added value w.r.t. naive semantics.

Theorem 65 Let T = (Arg( ), R) be an argumentation system. If R ∈ ℜ p 3 then:

• For all S ∈ Max( ), Arg(S) ∈ Ext p (T ). • |Ext p (T )| = |Max( )|.
The output of an argumentation system is in this case the same as under naive semantics, i.e., the universal conclusions given in Corollary 48.

Corollary 66 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 .

Output(T ) = S i ∈Max( )

CN(S i ).

Let us now analyse the attack relations of the second category, ℜ p 2 . Remember that in this case stable semantics chooses only some maximal consistent subsets of the knowledge base at hand. Four situations may be encountered:

(1) The stable extensions and the preferred extensions of an argumentation system coincide. Thus, preferred semantics provides no added value w.r.t. stable semantics. Moreover, it leads to arbitrary results, as discussed in the previous subsection (i.e., when R ∈ ℜ s 2 ).

(2) The preferred extensions consider additional but not all maximal consistent subsets (other than the ones chosen by stable semantics). This case is similar to the previous one and the argumentation system returns arbitrary results.

(3) The preferred extensions return all the maximal consistent subsets of the knowledge base. This means that stable semantics chooses some maximal consistent subsets and preferred semantics considers the remaining ones. This case collapses in the case of attack relations of the category ℜ p 3 . We have seen that the result of preferred semantics is already ensured by naive and stable semantics in this case. (4) Some of the preferred extensions provide non-maximal consistent subsets of the knowledge base. In this case, the result of the argumentation system is arbitrary.

To sum up, attack relations of the category ℜ p 2 may lead either to arbitrary results or to results which can be provided by naive semantics. The results are characterised in the following theorem.

Theorem 67 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ p 2 . Output(T ) = CN(S i ) where S i ranges over {S i ∈ Cons( ) | ∃E i ∈ Ext p (T ) and S i = Base(E i )} and Cons( ) = {S | S ⊆ , S is consistent and Free( ) ⊆ S}.

The results of this section show that reasoning under preferred semantics is not recommended, since it leads either to arbitrary results or to the results got under naive semantics. Figure 3 summarises the different situations that may be encountered under this semantics.

Grounded and ideal semantics

This section analyses the outputs of argumentation systems under existing sceptical semantics, namely grounded and ideal. Grounded semantics was proposed by [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. It ensures a unique extension for every argumentation system, and is based on a sceptical principle. It starts with non-attacked arguments, to which are added the arguments they defend. This reinstatement process is repeated until a fixpoint is reached. Argumentation systems that do not have non-attacked arguments have empty grounded extensions. In [START_REF] Dung | Computing ideal skeptical argumentation[END_REF], this semantics was extended to the so-called ideal semantics. The new semantics returns a unique extension which is an admissible set of arguments contained by every preferred extension of an argumentation system. The following properties were shown in [START_REF] Dung | Computing ideal skeptical argumentation[END_REF].

Property 68 (Dung, Mancarella, and Toni, 2007) Let T be an argumentation system.

• T admits a unique ideal extension.

• GE(T ) ⊆ IE(T ) ⊆ E i ∈Ext p (T ) E i . • If E i ∈Ext p (T ) E i is admissible, then IE(T ) = E i ∈Ext p (T ) E i .
The following example, borrowed from [START_REF] Dung | Computing ideal skeptical argumentation[END_REF], shows some differences between ideal and grounded semantics. It can be checked that:

• GE(T ) = ∅, • Ext p (T ) = {{b, c}, {b, d}}, and • IE(T ) = {b}.
Before analysing the argumentation systems' outputs under ideal and grounded semantics, we provide a result of great importance. It shows that the set of arguments built from Free( ) is an admissible extension of any argumentation system whose attack relation is conflict-dependent. Thus, this is true even for systems that do not satisfy the free precedence postulate.

Theorem 70 Let T = (Arg( ), R) be such that R is conflict-dependent.

• For all a ∈ Arg(Free( )), a neither attacks nor is attacked by another argument in Arg( ). • Arg(Free( )) is an admissible extension of T .

Since ideal semantics is based on preferred semantics, we analyse the two cases that may be encountered with the latter. We start with the case of an argumentation system that uses an attack relation of the category ℜ p 3 . We show that the ideal extension of such a system coincides with the intersection of all of its preferred extensions. Moreover, it is exactly the set of arguments built from the free part of the knowledge base.

Theorem 71 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 .

IE(T ) = E i ∈Ext p (T ) E i = Arg(Free( )).
Since arguments of Arg(Free( )) are not attacked by any argument, then they belong to the grounded extension of the argumentation system. Consequently, grounded and ideal extensions coincide.

Corollary 72 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 .

IE(T ) = GE(T ) = Arg(Free( )).
From the previous results, it is possible to characterise the set of conclusions drawn from a knowledge base using grounded and ideal semantics. It is the set of all formulae that follow using the consequence operator CN from Free( ).

Theorem 73 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 . The output of T under grounded/ideal semantics is: It is worth pointing out that, in this case, argumentation systems generalise the free consequences proposed by [START_REF] Benferhat | Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study part 1: The at case[END_REF] for reasoning about inconsistent propositional knowledge bases. Indeed, argumentation systems consider not only propositional logic but also any other Tarskian logic.

Output(T ) = CN(Free( )).
Recall that the assumption attack relation leads to coherent argumentation systems, thus their ideal and grounded semantics coincide.

Corollary 74 Let T = (Arg( ), R as ). For any ⊆ L, Output(T ) = CN(Free( )).

Let us now consider the case where the attack relation of an argumentation system is of the category ℜ p 2 . Here again, since the attack relation is conflict-dependent, the set of arguments Arg(Free( )) is contained by both ideal and grounded extensions.

Corollary 75 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 2 . The inclusions Arg(Free( )) ⊆ GE(T ) ⊆ IE(T ) ⊆ S hold for some S ∈ Max( ).

In the case of the above inclusions being strict, i.e., Arg(Free( )) ⊂ GE(T ) (respectively Arg(Free( )) ⊂ IE(T )), we show that the argumentation system T returns arbitrary conclusions.

Theorem 76 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies the five postulates under grounded (respectively ideal) semantics. If Arg(Free( )) ⊂ GE(T ) (respectively Arg(Free( )) ⊂ IE(T )) then there exists C ∈ C such that there exist x, x ′ ∈ C and x ∈ Output(T ) and x ′ / ∈ Output(T ).

To sum up, ideal and grounded semantics either coincide and return as output the set of all formulas that follow from the safe part of a knowledge base, i.e., CN(Free( )), or may both return arbitrary results. Figure 4 summarises the different situations encountered under these two semantics.

Related work

This paper investigated the compatibility of [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] argumentation framework with logical formalisms. For this purpose, it showed how to instantiate the framework from a logical knowledge base, namely how to define the arguments in a systematic way. Then, it proposed some basic postulates that the logical instantiations should satisfy, and studied under which conditions the postulates may be violated. Next, it investigated the outputs of such instantiations under various semantics.

There are some works in the literature which are in some ways related to ours. In [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF], rationality postulates were proposed for instantiations that use a particular language (it distinguishes between strict rules and defeasible rules). In our work, we extended some of those postulates to Tarskian logics and proposed three new ones. In [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF], the authors investigated when the ASPIC system satisfies the postulates. In [START_REF] Gorogiannis | Instantiating abstract argumentation with classical logic arguments: Postulates and properties[END_REF], the authors focused on some argumentation systems that are defined using propositional logic. They studied when those systems satisfy some of the rationality postulates presented in this paper. Our work is more general, since we considered a larger class of logics and did not focus on particular attack relations. Our results hold for any attack relation that is conflict-dependent. Note that all the attack relations that were studied in [START_REF] Gorogiannis | Instantiating abstract argumentation with classical logic arguments: Postulates and properties[END_REF] are conflict-dependent.

The second part of our paper on the outputs of argumentation systems under various semantics is novel. There is almost no work on the topic, with the exception of [START_REF] Cayrol | On the relation between argumentation and non-monotonic coherence-based entailment[END_REF]. Cayrol studied the underpinnings of stable semantics for one particular argumentation system: the one that is grounded in propositional logic (a particular case of Tarski's logics) and uses the 'assumption attack' relation. She showed that there is a one-to-one correspondence between the stable extensions of the system and the maximal consistent subsets of the knowledge base over which the system is built. In our paper, this result is generalised to any Tarskian logic and any attack relation. Moreover, we have shown that this result is already ensured by naive semantics. Thus, in the case of the system studied by Cayrol, stable semantics is useless. Finally, we have shown that this particular system is coherent, i.e., its stable extensions coincide with its preferred ones. Our work is more general, since it presented a complete view of the outputs of argumentation systems not only under stable semantics but also under various other semantics.

Conclusion

The paper investigated [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] argumentation framework. It started by pointing out its main limits, namely the gap between the abstract framework and the application for which it may be used, the lack of rationality postulates that would describe the kind of results expected from the framework, the lack of methodology for defining arguments and the attacks between them, and finally an overview of the underpinnings of the different acceptability semantics, as well as the basic concepts of the framework such as defence and conflict-freeness. The paper gave an answer to each of these issues.

The paper extended [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] argumentation framework by taking into account the logic from which arguments are built. The new framework is general since it is grounded in any abstract logic in Tarski's sense. Thus, a wide variety of logics can be used -even those that have not yet been considered in argumentation, such as temporal logic, modal logic, etc. The extension has two main advantages: first, it enforces the framework to avoid unsound conclusions; second, it relates the different notions of Dung's approach, like the attack relation and conflict-freeness, to the knowledge base at hand.

In [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF], three rationality postulates were defined for rule-based argumentation systems. The paper generalised the two postulates on direct consistency and closure to any argumentation framework built over a monotonic logic, and proposed three new postulates on sub-arguments, free precedence and exhaustiveness. It then showed that indirect consistency is always satisfied if direct consistency is ensured. Moreover, it showed that if consistency (respectively closure) is satisfied by the different extensions, then it is also satisfied by the output of the framework.

The paper then presented a formal methodology for defining arguments from a knowledge base, and for eliciting an appropriate attack relation. By appropriate, we mean an attack relation that satisfies the postulates. It showed that an attack relation should be grounded in the minimal conflicts that occur in the knowledge base at hand. An important result shows that when ternary or more minimal conflicts occur in the knowledge base, symmetric attack relations should be avoided since they lead to the violation of direct consistency.

Using well-behaved attack relations, the paper analysed the different acceptability semantics introduced in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] in terms of the subsets that are returned by each extension. The results of the analysis are very surprising and, unfortunately, disappointing. In fact, they show to what extent the rationality of Dung's approach is at stake. Moreover, it behaves in a completely arbitrary way. The first important result shows that maximal conflict-free sets of arguments are sufficient in order to derive reasonable conclusions from a knowledge base. Indeed, there is a one-to-one correspondence between maximal consistent subsets of a knowledge base and maximal conflict-free sets of arguments. This means that the different acceptability semantics defined in the literature are not necessary, and the notion of defence is useless. It is also shown that under naive semantics, argumentation systems generalise the coherence-based approach of [START_REF] Rescher | On inference from inconsistent premises[END_REF] to any Tarskian logic. This is particularly the case for adjunctive logics.

Remember that stable extensions are maximal conflict-free sets of arguments. Does this mean that stable semantics is appropriate? The answer is unfortunately 'no'. Indeed, stable extensions amount to either an arbitrary pick of some maximal consistent subsets of the knowledge base, or to the consideration of all of them. In the first case, they lead to arbitrary inferences whereas in the second case they lead to the result already ensured by naive semantics. The case of preferred semantics is even worse, and so this semantics should be avoided. The corresponding extensions represent some consistent subsets but not necessarily maximal ones. Thus, they lead to arbitrary inferences. There are, however, two pieces of good news. The first is that the number of (stable/preferred/naive) extensions is finite as soon as the knowledge base is finite. The second is that stable extensions always exist, meaning that semi-stable semantics proposed in Caminada (2006b) is useless since it does not provide added value w.r.t. stable semantics. Reasoning under ideal and grounded semantics may also be problematic. There are two possible situations: (i) the situation where the two extensions (grounded and ideal) coincide with the set of arguments built from the free part of a knowledge base; and (ii) the situation where both semantics lead to arbitrary results.

One of the main reasons for this defective behaviour of [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] approach is the attack relation. Indeed, we have shown that in order to ensure reasonable results, this relation should capture the minimal conflicts that occur in the knowledge base at hand. A minimal conflict is an inconsistent set of formulas. It is well known that the notion of inconsistency is not oriented. Thus, it should be captured by a symmetric attack relation. However, we have also shown that, due to the binary character of the attack relation, if it is symmetric, then consistency often fails. Which is when n-ary (other than binary) minimal conflicts occur in the knowledge base. The second reason is the definition of semantics without taking into account the application to which the system is applied, and thus without considering the structure of arguments.

Notes

1. Some fragments of well-known logics fail to be adjunctive, e.g., the pure implicational fragment of classical logic as it is negationless, disjunctionless, and, of course, conjunctionless. 2. A strict rule x → y means that if x holds, then y holds with no exception whatsoever. and (b'), CN(X ) ∪ CN(X ′′ ) ⊆ CN(X ∪ X ′′ ). From (a), it follows that X ′ ∪ X ′′ ⊆ CN(X ∪ X ′′ ). By monotonicity, CN(X ′ ∪ X ′′ ) ⊆ CN(CN(X ∪ X ′′ )). Finally, by the idempotence axiom, the inclusion CN(X ′ ∪ X ′′ ) ⊆ CN(X ∪ X ′′ ) holds. To show that CN(X ∪ X ′′ ) ⊆ CN(X ′ ∪ X ′′ ), the same reasoning is applied by starting with

X instead of X ′ . (4) X ∩ X ′ ⊆ X thus CN(X ∩ X ′ ) ⊆ CN(X ). Similarly, X ∩ X ′ ⊆ X ′ thus CN(X ∩ X ′ ) ⊆ CN(X ′ ). Consequently, CN(X ∩ X ′ ) ⊆ CN(X ) ∩ CN(X ′ ).
Property 7 Let X ⊆ L.

(1) If X is consistent, then CN(X ) is consistent as well.

(2)

∀X ′ ⊆ X , if X is consistent, then X ′ is consistent. (3) ∀X ′ ⊆ X , if X ′ is inconsistent, then X is inconsistent. Proof Let X ⊆ L. Assume that X is consistent, then CN(X ) = L (1).
(1) Let us now assume that CN(X ) is inconsistent. This means that CN(CN(X )) = L. However, according to the idempotence axiom, CN(CN(X )) = CN(X ). Thus, CN(X ) = L, which contradicts (1). ( 2) Assume that ∃X ′ ⊆ X such that X ′ is inconsistent. This means that CN(X ′ ) = L.

However, since X ′ ⊆ X then CN(X ′ ) ⊆ CN(X ) (according to the monotonicity axiom). Thus,

L ⊆ CN(X ). Since CN(X ) ⊆ L, then CN(X ) = L. Thus, X is inconsistent. Contradiction. (3) Let X ′ ⊆ X . Assume that X ′ is inconsistent. Since X ′ ⊆ X thus CN(X ′ ) ⊆ CN(X ) (by the monotonicity axiom). Since X ′ is inconsistent, CN(X ′ ) = L. Consequently, CN(X ) = L which means that X is inconsistent.
Property 9 For all X ⊆ ⊆ L,

• if X is consistent then C X = ∅; • if X is consistent then X ⊆ S for some S ∈ Max( );
• if X is inconsistent then there exists at least one minimal conflict C such that C ⊆ X .

Proof The first and third items are obvious. Let us now prove the second item. Let us construct a maximal consistent subset of that contains X . Consider an enumeration s 1 , s 2 , . . . of . Define a series S 0 , S 1 , S 2 , . . . of subsets of as follows: S 0 is X , and S n+1 = S n ∪ {s n+1 } if S n ∪ {s n+1 } is consistent, otherwise S n+1 = S n . By construction, S n is consistent for all n ≥ 0. Let S = n≥0 S n . Trivially, X ⊆ S. We now show S ∈ Max( ). Assume first that S is inconsistent, i.e., CN(S) = L according to Definition 6. Tarski's absurdity axiom yields that x ∈ CN(S) for some x satisfying CN({x}) = L. Since S n ⊆ S n+1 , Tarski's compactness axiom means that x ∈ CN(S) iff x ∈ CN(S k ) for some k. However, x ∈ CN(S k ) means that x ∈ S k is inconsistent -a contradiction. Hence, we have shown that S is consistent. By construction, it is a subset of . It remains to show that it is a maximal consistent subset of . Let y be in \ S. Assume that S ∪ {y} is consistent. Since y ∈ , y is some s h in the above enumeration. Should S ∪ {y} be consistent, so would S h ∪ {y} be, in view of Tarski's compactness axiom (monotony direction). However, S h ∪ {y} consistent would mean that y ∈ S h+1 hence y ∈ S, a contradiction.

Property 11 Let (L, CN) be adjunctive, C ⊆ L be a minimal conflict. For all X ⊂ C, if X = ∅, then:

(1) ∃x ∈ L such that CN({x}) = CN(X ). (2) ∃x 1 ∈ CN(X ) and ∃x 2 ∈ CN(C \ X ) such that the set {x 1 , x 2 } is inconsistent. Proof Let C be a minimal conflict. Consider X ⊂ C such that X = ∅.
We prove the first item of the property by induction, after we first take care to show that X is finite. By Tarski's requirements, there exists

x 0 ∈ L such that CN({x 0 }) = L. Since C is a conflict, CN(C) = CN({x 0 }). As a consequence, x 0 ∈ CN(C). However, CN(C) = C ′ ⊆ f C CN(C ′ ) by Tarski's requirements. Thus, x 0 ∈ CN(C) means that there exists C ′ ⊆ f C such that x 0 ∈ CN(C ′ ). This says that C ′ is a conflict. Since C is a minimal conflict, C = C ′ and
it follows that C is finite. Of course, so is X : let us write X = {x 1 , . . . , x n }. Base step: n = 1. Taking x to be x 1 is enough. Induction step: Assume the lemma is true up to rank n -1. As CN is a closure operator, CN({x 1 , . . . ,

x n }) = CN(CN({x 1 , . . . , x n-1 }) ∪ {x n }). The induction hypothesis entails ∃x ∈ L such that CN(CN({x 1 , . . . , x n-1 }) ∪ {x n }) = CN(CN({x}) ∪ {x n }). Then, CN({x 1 , . . . , x n }) = CN({x, x n }). Hence, there exists y ∈ L such that CN({x, x n }) = CN({y}) because (L, CN) is adjunctive. Since CN({x 1 , . . . , x n }) = CN({x, x n }) was just proved, it follows that CN({y}) = CN({x 1 , . . . , x n }).
Take X 1 = X and X 2 = C \ X 1 . Since X is a non-empty proper subset of C, so are both X 1 and X 2 . Then, the first bullet of this property can be applied to X 1 and X 2 . As a result,

∃x 1 ∈ L such that CN({x 1 }) = CN(X 1 ) and ∃x 2 ∈ L such that CN({x 2 }) = CN(X 2 ).
The expansion axiom gives {x 1 } ⊆ CN({x 1 }) and {x 2 } ⊆ CN({x 2 }). Thus, x 1 ∈ CN(X 1 ) and x 2 ∈ CN(X 2 ). Using the expansion axiom again, X 1 ⊆ CN(X 1 ) and X 2 ⊆ CN(X 2 ). Thus,

X 1 ∪ X 2 ⊆ CN(X 1 ) ∪ CN(X 2 ) = CN({x 1 }) ∪ CN({x 2 }). It follows that C ⊆ CN({x 1 }) ∪ CN({x 2 }). Using Property 5, CN({x 1 }) ∪ CN({x 2 }) ⊆ CN({x 1 , x 2 }), thus C ⊆ CN({x 1 , x 2 }). Since C is inconsistent, Property 7 gives that CN({x 1 , x 2 }) is inconsistent as well. By the definition of inconsistency, it follows that CN(CN({x 1 , x 2 })) = L. Applying the idempotence axiom, CN({x 1 , x 2 }) = L, thus the set {x 1 , x 2 } is inconsistent.
Property 14 For all (X, x) ∈ Arg( ), the set {x} is consistent.

Proof Let (X, x) ∈ Arg( ). From Definition 13, the support X is consistent. Thus, according to Property 7, CN(X ) is consistent as well. Since x ∈ CN(X ), then {x} ⊆ CN(X ) thus {x} is consistent.

Property 15 Let be a knowledge base such that for all x ∈ , x ∈ CN(∅). For all x ∈ such that the set {x} is consistent, ({x}, x) ∈ Arg( ).

Proof Let x ∈ be such that the set {x} is consistent. Since x ∈ CN(∅), then {x} is a minimal set such that x ∈ CN({x}). It follows that ({x}, x) ∈ Arg( ).

Property 16 Arg( ) ⊆ Arg( ′ ) whenever ⊆ ′ ⊆ L. Proof Let ⊆ ′ ⊆ L. Assume that (X, x) ∈ Arg( ) and (X, x) / ∈ Arg( ′ ). Since (X, x) /
∈ Arg( ′ ), then there are four possible cases:

(1) X is not a subset of ′ . This is impossible since

(X, x) ∈ Arg( ), thus X ⊆ ⊆ ′ . (2) X is inconsistent. This is impossible since (X, x) ∈ Arg( ). (3) x / ∈ CN(X ). This is impossible since (X, x) ∈ Arg( ) hence x ∈ CN(X ). (4
) X is not minimal. This means that ∃X ′ ⊂ X that satisfies conditions 1-3 of Definition 13. This is impossible since (X, x) ∈ Arg( ).

Property 20 Let T = (Arg( ), R) be an argumentation system over a knowledge base and Ext(T ) its set of extensions under a given semantics. It holds that

Output(T ) = E i ∈Ext(T ) Concs(E i ).
Proof Let T = (Arg( ), R) be an argumentation system over a base .

(1) Let x ∈ Output(T ). Thus, for all

E i ∈ Ext(T ), ∃a i ∈ E i such that Conc(a i ) = x.
It follows that x ∈ Concs(E i ), ∀E i and hence x ∈ ∩Concs(E i ).

(2) Assume that x ∈ ∩Concs(E i ). Thus,

∀E i ∈ Ext(T ), ∃a i ∈ E i such that Conc(a i ) = x. Consequently, x ∈ Output(T ).
Property 21 Let T = (Arg( ), R) be an argumentation system over a knowledge base . Output(T ) ⊆ CN( ).

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base . Let x ∈ Output(T ). Thus, ∃a ∈ Arg( ) such that Conc(a) = x. Besides, x ∈ CN(Supp(a)) and Supp(a) ⊆ . By monotonicity of CN, CN(Supp(a)) ⊆ CN( ). Thus, x ∈ CN( ).

Property 64 It holds that ℜ p ⊆ ℜ s .

Proof Let R ∈ ℜ p . Thus, for all T = (Arg( ), R), T satisfies all the postulates, i.e., for all E ∈ Ext p (T ),

• Concs(E) is consistent; • Concs(E) = CN(Concs(E)); • for all a ∈ E, Sub(a) ⊆ E; • Arg(Free( )) ⊆ E; • for all (X, x) ∈ Arg( ), if X ∪ {x} ⊆ Concs(E), then (X, x) ∈ E.
Since Ext s (T ) ⊆ Ext p (T ), the previous properties are satisfied by all the stable extensions of T . Consequently, R ∈ ℜ s .

Proposition 17 Let (L, CN) be adjunctive and be a knowledge base. For all nonempty proper subsets X of some minimal conflict C ∈ C , there exists a ∈ Arg( ) such that Supp(a) = X .

Proof Let C ∈ C and X ⊆ C such that X is non-empty. Assume ∄a ∈ Arg( ) such that Supp(a) = X -i.e., there exists no x such that X is a minimal consistent set satisfying x ∈ CN(X ). So, for all x ∈ L, if x ∈ CN(X ) then ∃Y ⊂ X such that x ∈ CN(Y ). In short, for all x ∈ CN(X ), there exists Y ⊂ X such that x ∈ CN(Y ). Property 11 says that there exists z ∈ L such that CN({z}) = CN(X ).

However, z ∈ CN(Y ) for all Y ⊂ X otherwise C would fail to be minimal (because Y ∪ (C \ X ) ⊂ C while z ∈ CN(Y ) implies CN(C) = CN(X ∪ (C \ X )) = CN({z} ∪ (C \ X )) ⊆ CN(Y ∪ (C \ X ))). A contradiction arises.
Proposition 23 Let T = (Arg( ), R) be an argumentation system over a knowledge base . If T is closed under CN, then Output(T ) = CN(Output(T )).

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base , and Ext(T ) be its set of extensions under a given semantics. Assume that T satisfies closure under CN. From the Expansion axiom, it follows that Output(T ) ⊆ CN(Output(T )).

Assume now that x ∈ CN(Output(T )). Thus, ∃x 1 , . . . , x n ∈ Output(T ) such that x ∈ CN({x 1 , . . . , x n }). From Property 20, x 1 , . . . , x n ∈ ∩Concs(E i ) where E i ∈ Ext(T ). From Property 5, it holds that CN({x 1 , . . . , x n }) ⊆ CN(∩Concs(E i )). Again, from Property 5, x ∈ CN(Concs(E 1 )) ∩ . . . ∩ CN(Concs(E n )). Since T satisfies closure under CN, then for each

E i it holds that CN(Concs(E i )) = Concs(E i ). Thus, x ∈ Concs(E 1 ) ∩ . . . ∩ Concs(E n ).
From Property 20, it holds that x ∈ Output(T ).

Proposition 25 Let T = (Args( ), R) be an argumentation system over a knowledge base . If T is closed under sub-arguments and under CN, then for all E ∈ Ext(T ),

Concs(E) = CN(Base(E)).
Proof Assume that T = (Args( ), R) is closed under sub-arguments and under CN. From Property 4 in Amgoud ( 2012), since T is closed under sub-arguments, then it fol- lows that Base(E) ⊆ Concs(E). By monotonicity of CN, we get

CN(Base(E)) ⊆ CN(Concs(E)). Since T is closed under CN, then CN(Base(E)) ⊆ Concs(E). Besides, by definition of Concs(E), Concs(E) ⊆ CN(Supp(a i )) with a i ∈ E. From Property 5, it follows that Concs(E) ⊆ CN( Supp(a i )), thus Concs(E) ⊆ CN(Base(E)).
Proposition 27 If an argumentation system T = (Arg( ), R) satisfies consistency, then the set Output(T ) is consistent.

Proof Let T = (Arg( ), R) be an argumentation system built over a knowledge base . Assume that T satisfies consistency. Thus, ∀E i ∈ Ext(T ), Concs(E i ) is consistent. Let E be a given extension in the set Ext(T ). Since ∩Concs(E i ) ⊆ Concs(E), then ∩Concs(E i ) is consistent as well. Besides, from Property 20, Output(T ) = ∩Concs(E i ). It follows that Output(T ) is consistent.

Proposition 28 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that for all x ∈ , x / ∈ CN(∅). If T satisfies consistency and is closed under sub-arguments, then for all E ∈ Ext(T ), Base(E) is consistent.

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base . Assume that T satisfies consistency and closure under sub-arguments. From closure under sub-arguments, it follows that for all E ∈ Ext(T ), Base(E) ⊆ Concs(E) (from Property 4 in Amgoud, 2012). Since T satisfies consistency, the set Concs(E) is consistent. From Property 7, it follows that Base(E) is consistent.

Proposition 30 Let T = (Arg( ), R) be an argumentation system over a knowledge base . If T satisfies free precedence, then Free( ) ⊆ Output(T ) (under any of the reviewed semantics).

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base , and let Ext(T ) be its set of extensions under any of the reviewed semantics. Assume that T satisfies Postulate 29. Thus, for all E ∈ Ext(T ), Arg(Free( )) ⊆ E. Assume that Free( ) = ∅. Thus, for all x ∈ Free( ), ({x},

x) ∈ Arg(Free( )) (indeed, x / ∈ CN(∅)) and thus, ({x}, x) ∈ E (for all E ∈ Ext(T )). Consequently, Free( ) ⊆ Concs(E) (for all E ∈ Ext). So, Free( ) ⊆ Output(T ).
Proposition 32 If an argumentation system T is closed under both CN and sub-arguments and satisfies the exhaustiveness postulate, then ∀E ∈ Ext(T ), E = Arg(Base(E)) (under any of the reviewed semantics).

Proof Let T be an argumentation system that satisfies exhaustiveness and that is closed under both CN and sub-arguments. Let Ext(T ) be its extensions under any of the reviewed semantics. Let E ∈ Ext(T ). From the definition of Arg and Base, it follows that E ⊆ Arg(Base(E)).

Assume now a ∈ Arg(Base(E)) and let a = (X, x). Thus, X ⊆ Base(E). By monotonicity of CN, CN(X ) ⊆ CN(Base(E)). From Proposition 25, since T is closed under both CN and sub-arguments, then Concs(E) = CN(Base(E)). Thus, CN(X ) ⊆ Concs(E). Besides, X ⊆ CN(X ) (from the Expansion Axiom of CN) and x ∈ CN(X ) (from the definition of an argument), thus, X ∪ {x} ⊆ Concs(E). By exhaustiveness of T , a ∈ E.

Proposition 34 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. If T satisfies consistency and is closed under sub-arguments (under naive and stable semantics), then it is closed under CN (under naive and stable semantics).

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. Assume that T is closed under sub-arguments and satisfies consistency. Assume also that T violates closure under CN. Thus, ∃E ∈ Ext n (T ) such that Concs(E) = CN(Concs(E)). This means that ∃x ∈ CN(Concs(E)) and x / ∈ Concs(E). Besides, CN(Concs(E)) ⊆ CN(Base(E)). Thus, x ∈ CN(Base(E)). Since CN verifies compactness, then ∃X ⊆ Base(E) such that X is finite and x ∈ CN(X ). Moreover, from Proposition 28, Base(E) is consistent. Then, X is consistent as well (from Property 7). Consequently, the pair (X, x) is an argument. Besides, since x / ∈ Concs(E) then (X, x) / ∈ E. This means that ∃a ∈ E such that aR(X, x) or (X, x)Ra. Finally, since R is conflict-dependent, then Supp(a) ∪ X is inconsistent and consequently Base(E) is inconsistent. This contradicts the assumption.

Since Ext s (T ) ⊆ Ext n (T ), then since T satisfies closure under CN under naive semantics, then it also satisfies the postulate under stable semantics.

Proposition 36 Let (Arg( ), R) be such that R is conflict-dependent. If is consistent, then R = ∅.

Proof Let (Arg( ), R) be such that R is conflict-dependent. Assume that is consistent. Then, for all a, b ∈ Arg( ), Supp(a) ∪ Supp(b) is consistent. Since R is conflictdependent, then (a, b) / ∈ R. Thus, R = ∅.

Proposition 37 Let (Arg( ), R) be such that R is conflict-dependent. ∀E ⊆ Arg( ), if Base(E) is consistent, then E is conflict-free.
Proof Let E ⊆ Arg( ). Since Base(E) is consistent, then so is Supp(a) ∪ Supp(b) for all a and b in E (according to Property 7). Hence, there exists no minimal conflict C ⊆ Supp(a) ∪ Supp(b). By the definition of R being conflict-dependent, (a, b) / ∈ R ensues.

Proposition 38 Let (Arg( ), R) be such that R is conflict-dependent. For all a ∈ Arg( ), (a, a) / ∈ R.

Proof Assume that R is conflict-dependent and a ∈ Arg( ) such that(a, a) ∈ R. Since R is conflict-dependent, then ∃C ∈ C such that C ⊆ Supp(a). This means that Supp(a) is inconsistent. This contradicts the fact that a is an argument.

Proposition 40 Let (L, CN) be adjunctive and be a knowledge base such that ∃C ∈ C and |C| > 2. If R is conflict-dependent and symmetric, then the argumentation system (Arg( ), R) violates consistency.

Proof Let C be a minimal conflict in a knowledge base . Consider a partition {X 1 , X 2 , X 3 } of C. Due to Proposition 17, there exist a 1 , a 2 , a 3 in Arg( ) such that CN(Supp(a i )) = CN(X i ) for i = 1...3. For {a 1 , a 2 , a 3 } not to be an admissible extension, either it is not conflict-free or it fails to defend its elements. Assume that {a 1 , a 2 , a 3 } is not conflict-free, i.e., a i Ra j for some i and j in {1, 2, 3}. Since R is conflict-dependent, there exists C ′ ∈ C such that C ′ ⊆ Supp(a i ) ∪ Supp(a j ). Hence, CN(Supp(a i ) ∪ Supp(a j )) = L. However, CN(Supp(a i ) ∪ Supp(a j )) = CN(CN(Supp(a i )) ∪ CN(Supp(a j ))) = CN(CN(X i ) ∪ CN(X j )) = CN(X i ∪ X j ), meaning that X i ∪ X j is an inconsistent proper subset of C, contradicting C ∈ C . Otherwise, assume that {a 1 , a 2 , a 3 } fails to defend its elements. It obviously cannot be the case because R is symmetric: if aRa i then a i Ra.

Theorem 41 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. If T satisfies consistency and is closed under sub-arguments (under naive semantics), then:

• For all E ∈ Ext n (T ), Base(E) ∈ Max( ). • For all E ∈ Ext n (T ), E = Arg(Base(E)). • For all E i , E j ∈ Ext n (T ), if Base(E i ) = Base(E j ) then E i = E j .
Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. Assume that T satisfies consistency and is closed under subarguments. Let E ∈ Ext n (T ). From Proposition 28, Base(E) is consistent. Assume now that Base(E) is not maximal (for set inclusion) consistent. Thus, ∃x ∈ \ Base(E) such that Base(E) ∪ {x} is consistent. This means that {x} is consistent. Thus, ∃a ∈ A such that Supp(a) = {x}. Since x / ∈ Base(E), then a / ∈ E. Since E is a naive extension, then ∃b ∈ E such that aRb or bRa. Since R is conflict-dependent, then Supp(a) ∪ Supp(b) is inconsistent. But, Supp(b) ⊆ Base(E), this would mean that Base(E) ∪ {x} is inconsistent. Contradiction.

Let E ∈ Ext n (T ). It is obvious that E ⊆ Arg(Base(E)) since the construction of arguments is monotonic. Let a ∈ Arg(Base(E)). Thus, Supp(a) ⊆ Base(E). Assume that a / ∈ E, then ∃b ∈ E such that aRb or bRa. Since R is conflict-dependent, then Supp(a) ∪ Supp(b) is inconsistent. Besides, Supp(a) ∪ Supp(b) ⊆ Base(E). This means that Base(E) is inconsistent. Contradiction.

Now let E i , E j ∈ Ext n (T ). Assume that Base(E i ) = Base(E j ). Then, Arg(Base(E i )) = Arg(Base(E j )). Besides, from the second bullet of the theorem, E i = Arg(Base(E i )) and E j = Arg(Base(E j )). Consequently, E i = E j .

Theorem 42 Let (L, CN) be adjunctive. Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. If T satisfies consistency and is closed under sub-arguments (under naive semantics), then:

• For all S ∈ Max( ), Arg(S) ∈ Ext n (T ). • For all S i , S j ∈ Max( ), if Arg(S i ) = Arg(S j ) then S i = S j .
• For all S ∈ Max( ), S = Base(Arg(S)).

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. Assume that T satisfies Postulates 24 and 26.

Let S ∈ Max( ), and assume that Arg(S) / ∈ Ext n (T ). Since R is conflict-dependent and S is consistent, it follows from Proposition 37 that Arg(S) is conflict-free. Thus, Arg(S) is not maximal for set inclusion. So, ∃a ∈ A such that Arg(S) ∪ {a} is conflict-free. There are two possibilities:

(1) S ∪ Supp(a) is consistent. But since S ∈ Max( ), then Supp(a) ⊆ S, and this would mean that a ∈ Arg(S).

(2) S ∪ Supp(a) is inconsistent. Thus, ∃C ∈ C such that C ⊆ S ∪ Supp(a). Let X 1 = C∩S and X 2 = C∩Supp(a) with X 1 = ∅ and X 2 = ∅ (since S and Supp(a) are consistent). From Property 11, ∃x 1 ∈ CN(X 1 ) and ∃x 2 ∈ CN(X 2 ) such that the set {x 1 , x 2 } is inconsistent. Note that (X 1 , x 1 ) and (X 2 , x 2 ) are arguments. Moreover, (X 1 , x 1 ) ∈ Arg(S) and (X 2 , x 2 ) ∈ Sub(a). Besides, since Arg(S)∪{a} is conflictfree, then ∃E ∈ Ext(T ) such that Arg(S) ∪ {a} ⊆ E. Thus, (X 1 , x 1 ) ∈ E. Since T is closed under sub-arguments then (X 2 , x 2 ) ∈ E. Thus, {x 1 , x 2 } ⊆ Concs(E).

From Property 7, it follows that Concs(E) is inconsistent. This contradicts the fact that T satisfies consistency. Now let S i , S j ∈ Max( ) be such that Arg(S i ) = Arg(S j ). Assume that S i = S j , thus ∃x ∈ S i and x / ∈ S j . Besides, if S i is consistent, so is the set {x}. Consequently, ∃a ∈ A such that Supp(a) = {x}. It follows also that a ∈ Arg(S i ) and thus a ∈ Arg(S j ). By definition of an argument, Supp(a) ⊆ S j . Contradiction.

Let S ∈ Max( ). Since S is consistent, then ∀x ∈ S, it holds that the set {x} is consistent as well (from Property 7). Then, ({x}, x) is an argument in Arg(S) (from Property 15). Thus, S ⊆ Base(Arg(S)). Conversely, let x ∈ Base(Arg(S)). By definition of the function Base, ∃a ∈ Arg(S) such that x ∈ Supp(a). Besides, by definition of an argument, Supp(a) ⊆ S. Consequently, x ∈ S.

Theorem 46 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent, T satisfies consistency and is closed under sub-arguments (under naive semantics). Output(T ) = CN(S i ) where S i ranges over {S i ∈ Max( ) | ∃E i ∈ Ext n (T ) and S i = Base(E i )}.

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. Assume that T satisfies consistency and is closed under subarguments. From Proposition 34, T enjoys closure under CN (under naive semantics). From Proposition 25, for all E ∈ Ext n (T ), Concs(E) = CN(Base(E)). Besides, from Theorem 41, for all E i ∈ Ext n (T ), ∃!S i ∈ Max( ) such that Base(E i ) = S i . Thus, Concs(E i ) = CN(S i ). By definition, Output(T ) = Concs(E i ), thus Output(T ) = CN(S i ).

Theorem 49 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. If T satisfies consistency and closure under subarguments (under stable semantics) and Ext s (T ) = ∅, then:

• For all E ∈ Ext s (T ), Base(E) ∈ Max( ). • For all E ∈ Ext s (T ), E = Arg(Base(E)). • For all E i , E j ∈ Ext s (T ), if Base(E i ) = Base(E j ) then E i = E j .
Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. Let E ∈ Ext s (T ). Since T satisfies Postulates 22, 24 and 26, then Base(E) is consistent (from Proposition 28). Assume now that Base(E) is not maximal for set inclusion. Thus, ∃x ∈ \ Base(E) such that Base(E) ∪ {x} is consistent. This means that {x} is consistent. Thus, from Property 15, ∃a ∈ Arg( ) such that Supp(a) = {x}. Since x / ∈ Base(E), then a / ∈ E. Since E is a stable extension, then ∃b ∈ E such that bRa. Since R is conflict-dependent, then Supp(a) ∪ Supp(b) is inconsistent. But, Supp(b) ⊆ Base(E), which would mean that Base(E) ∪ {x} is inconsistent. Contradiction.

Let E ∈ Ext s (T ). It is obvious that E ⊆ Arg(Base(E)) since the construction of arguments is monotonic. Let a ∈ Arg(Base(E)). Thus, Supp(a) ⊆ Base(E).Assume that a / ∈ E, then ∃b ∈ E such that bRa. Since R is conflict-dependent, then Supp(a)∪Supp(b) is inconsistent. Besides, Supp(a) ∪ Supp(b) ⊆ Base(E). This means that Base(E) is inconsistent. Contradiction.

Now let E i , E j ∈ Ext s (T ). Assume that Base(E i ) = Base(E j ). Then, Arg(Base(E i )) = Arg(Base(E j )). Besides, from bullet 2 of the theorem, E i = Arg(Base(E i )) and E j = Arg(Base(E j )). Consequently, E i = E j .

Theorem 50 It holds that ℜ s1 = ∅.

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s1 . Thus, Output(T ) = ∅. Assume that Free( ) = ∅. Thus, T violates free precedence postulate. This contradicts the fact that R ∈ ℜ s1 .

Theorem 51 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s 2 . Output(T ) = CN(S i ) where S i ranges over

{S i ∈ Max( ) | ∃E i ∈ Ext s (T ) and S i = Base(E i )}.
Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s2 . From Proposition 25, for all

E i ∈ Ext s (T ), Concs(E i ) = CN(Base(E i )). Thus, Output(T ) = CN(Base(E i )) with E i ∈ Ext s (T ). From Theorem 49, for all E i ∈ Ext s (T ), ∃!S i ∈ Max( ) such that Base(E i ) = S i . Thus, Output(T ) = CN(S i ).
Theorem 52 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s3 . For all S ∈ Max( ), Arg(S) ∈ Ext s (T ).

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s3 . Let S ∈ Max( ). Since Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s3 . From Theorem 52, for all S ∈ Max( ), Arg(S) ∈ Ext s (T ). Theorem 58 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). For all E ∈ Ext p (T ), there exists S ∈ Max( ) such that Base(E) ⊆ S.

Proof Let T = (Arg( ), R) be an argumentation system such that R is conflictdependent and T satisfies consistency and closure under sub-arguments. Let E ∈ Ext p (T ). Due to consistency and closure under sub-arguments, Base(E) is consistent (cf. Proposition 28). From Property 9, there exists S ∈ Max( ) such that Base(E) ⊆ S.

Theorem 60 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). For all

E i , E j ∈ Ext p (T ), if Base(E i ) ⊆ Base(E j ) then E i = E j .
Proof Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments.Assume that E i , E j ∈ Ext p (T ) and Base(E i ) ⊆ Base(E j ).

We first show that ∀x ∈ {i, j}, Arg(Base(E x )) is conflict-free. Assume that Arg(Base(E x )) is not conflict-free. Thus, ∃a, b ∈ Arg(Base(E x )) such that aRb or bRa. Since R is conflict-dependent, then Supp(a) ∪ Supp(b) is inconsistent. Besides, Supp(a) ∪ Supp(b) ⊆ Base(E x ). Thus, Base(E x ) is inconsistent. This contradicts Proposition 28.

Assume that

E i \ E j = ∅. Let E = E j ∪ (E i \ E j ). E ⊆ Arg(Base(E j )).
Thus, E is conflict-free (since Arg(Base(E j )) is conflict-free). Moreover, E defends any element in E j (since E j ∈ Ext p (T )) and any element in E i \ E j (since E i ∈ Ext p (T )). Thus, E is an admissible set. This contradicts the fact that E j ∈ Ext p (T ). The same reasoning holds for the case

E j \ E i = ∅ and having E = E i ∪ E j \ E i .
Theorem 61 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). Let S ∈ Max( ). For all

E i , E j ∈ Ext p (T ), if Base(E i ) ⊆ S and Base(E j ) ⊆ S, then E i = E j .
Proof Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). Assume that there exist two distinct preferred extensions E 1 and E 2 such that for some S ∈ Max( ), both Base(E 1 ) ⊆ S and Base(E 2 ) ⊆ S hold. Then, Base(E 1 ) ∪ Base(E 2 ) ⊆ S and Base(E 1 )∪Base(E 2 ) is consistent. Since R is conflict-dependent, aRb would demand that Supp(a) ∪ Supp(b) be inconsistent. Therefore, aRb is impossible for a and b both in E 1 ∪E 2 . That is, E 1 ∪E 2 is conflict-free. Since E 1 is an extension, it defends all arguments in E 1 . Since E 2 is an extension, it defends all arguments in E 2 . Hence, E 1 ∪E 2 defends all arguments in E 1 ∪ E 2 . That is, E 1 ∪ E 2 is an admissible set, and there exists a preferred extension E 3 that contains it (possibly improperly). According to Theorem 60, Base(

E 1 ) ⊆ Base(E 1 ∪E 2 ) = Base(E 3 ) yield E 1 = E 3 , and, similarly, Base(E 2 ) ⊆ Base(E 1 ∪ E 2 ) = Base(E 3 ) yield E 2 = E 3 . Therefore, E 1 = E 2 ,
contradicting the assumption that E 1 and E 2 are distinct.

Theorem 62 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). It holds that 1

≤ |Ext p (T )| ≤ |Max( )|.
Proof Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments (under preferred semantics). From Theorem 58, for all E ∈ Ext p (T ), ∃S ∈ Max( ) such that Base(E) ⊆ S. From Theorem 61, there cannot exist two distinct preferred extensions E i and E j such that for some S ∈ Max( ), both Base(E i ) ⊆ S and Base(E j ) ⊆ S. Thus, every S ∈ Max( ) is captured by at most one preferred extension of T . It follows that 1

≤ |Ext p (T )| ≤ |Max( )|.
Theorem 65 Let T = (Arg( ), R) be an argumentation system. If R ∈ ℜ p 3 then:

• for all S ∈ Max( ), Arg(S) ∈ Ext p (T ); • |Ext p (T )| = |Max( )|.
Proof Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 . From Theorem 52, for all S ∈ Max( ), Arg(S) ∈ Ext s (T ). Thus, Arg(S) ∈ Ext p (T ).

Since R ∈ ℜ p 3 , thus |Ext s (T )| = |Max( )|. Assume now that there exists E ∈ Ext p (T ) such that Base(E) / ∈ Max( ). Thus, ∃S ∈ Max( ) such that Base(E) ⊆ S. From the previous result, Arg(S) ∈ Ext p (T ). From Theorem 60, E = Arg(S). Consequently, |Ext p (T )| = |Max( )|.

Theorem 67 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ p 2 . Output(T ) = CN(S i ) where S i ranges over

{S i ∈ Cons( ) | ∃E i ∈ Ext p (T ) and S i = Base(E i )}.
Proof Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 2 . Let E ∈ Ext p (T ). From Proposition 25, since T is closed both under CN and under sub- arguments, then Concs

(E) = CN(Base(E)). From Definition 19, Output(T ) = Concs(E i ), E i ∈ Ext p (T ). Thus, Output(T ) = CN(Base(E i )), E i ∈ Ext p (T ).
Besides, Free( ) ⊆ Base(E) for all E ∈ Ext p (T ) and from Proposition 28, Base(E) is consistent. Thus, Base(E) ∈ Cons( ).

Theorem 70 Let T = (Arg( ), R) be such that R is conflict-dependent.

• For all a ∈ Arg(Free( )), a neither attacks nor is attacked by another argument in Arg( ).

• Arg(Free( )) is an admissible extension of T . Proof Let (Arg( ), R) be such that R is conflict-dependent. Let a ∈ Arg(Free( )). Assume that ∃b ∈ A such that aRb or bRa. Since R is conflict-dependent, then ∃C ∈ C such that C ⊆ Supp(a) ∪ Supp(b)
. By definition of an argument, both Supp(a) and Supp(b) are consistent. Then, C ∩ Supp(a) = ∅. This contradicts the fact that Supp(a) ⊆ Free( ). Thus, Arg(Free( )) is conflict-free and can never be attacked. Consequently, Arg(Free( )) is an admissible extension of T .

Theorem 71 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 .

IE(T ) =

E i ∈Ext p (T ) E i = Arg(Free( )).

Proof Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 . Since T satisfies exhaustiveness, then from Proposition 32, for all E i ∈ Ext p (T ), E i = Arg(Base(E i )). So,

E i ∈Ext p (T ) E i = Arg   E i ∈Ext p (T )
Base(E i )   .

From Theorem 65, for all E i ∈ Ext p (T ), Base(E i ) ∈ Max( ). Moreover, |Ext p (T )| = |Max( )|. Thus, E i ∈Ext p (T ) Base(E i ) = Free( ). Consequently,

E i ∈Ext p (T )
E i = Arg(Free( )).

From Theorem 70, Arg(Free( )) is an admissible set of T . Thus, from Property 68,

IE(T ) = E i ∈Ext p (T )
E i = Arg(Free( )).

Theorem 73 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies the five postulates (under preferred semantics). If |Ext p (T )| = |Max( )|, then the output of T under grounded/ideal semantics is: Output(T ) = CN(Free( )).

Proof Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies the five postulates (under preferred semantics). Assume that |Ext p (T )| = |Max( )|. Then, from Corollary 72, IE(T ) = GE(T ) = E i ∈Ext p (T ) E i = Arg(Free( )).

Let us first show that T is closed under CN under grounded/ideal semantics, that is

Concs   E i ∈Ext p (T ) E i   = CN   Concs   E i ∈Ext p (T ) E i     .
Let x ∈ CN Concs E i ∈Ext p (T ) E i . Thus, for all E i ∈ Ext p (T ), x ∈ CN(Concs(E i )). Since T satisfies closure under CN, then x ∈ Concs(E i ). Besides, since x ∈ CN Concs E i ∈Ext p (T ) E i , then there exists a finite set x 1 , . . . , x n ∈ Concs E i ∈Ext p (T ) E i such that x ∈ CN({x 1 , . . . , x n }). Moreover, CN({x 1 , . . . , x n }) ⊆ CN Concs E i ∈Ext p (T ) E i (by monotonicity of CN). Thus,

x ∈ CN Concs E i ∈Ext p (T ) E i . Let us now show that T is closed under sub-arguments under grounded/ideal semantics. Assume that a ∈ IE(T ). Thus, a ∈ E i ∈Ext p (T ) E i . Since T is closed under sub-arguments (under preferred semantics), then for all E i ∈ Ext p (T ), Sub(a) ⊆ E i . Thus, Sub(a) ⊆ Theorem 76 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies the five postulates under grounded (respectively ideal) semantics. If Arg(Free( )) ⊂ GE(T ) (respectively Arg(Free( )) ⊂ IE(T )) then there exists C ∈ C such that there exist x, x ′ ∈ C and x ∈ Output(T ) and x ′ / ∈ Output(T ).

Proof Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies the five postulates under grounded semantics.Assume that Arg(Free( )) ⊂ GE(T ). Thus, there exists an argument a ∈ GE(T ) such that a / ∈ Arg(Free( )). Thus, Supp(a) ⊆ Free( ). So, there exists x ∈ Inc( ) such that x ∈ Supp(a). Then, there exists C ∈ C such that x ∈ C. Since T satisfies closure under CN and under sub-arguments, then Output(T ) = Concs(GE(T )) = CN(Base(GE(T ))). Since x ∈ Supp(a), then x ∈ Base(GE(T )). From the expansion axiom, x ∈ CN(Base(GE(T ))). Since T satisfies consistency, then C ⊆ Concs(GE(T )). Thus, there exists x ′ ∈ C such that x ′ / ∈ Concs(GE(T )). The same proof holds for ideal semantics.

Corollary 43 Let (L, CN) be adjunctive. Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. T satisfies consistency and is closed under sub-arguments (under naive semantics) iff there is a bijection between the naive extensions of Ext n (T ) and the elements of Max( ).

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent. Assume that T satisfies Postulates 24 and 26. Then, from Theorems 41 and 42, it follows that there is a one-to-one correspondence between Max( ) and Ext n (T ).

Assume now that there is a one-to-one correspondence between Max( ) and Ext n (T ). Then, ∀E ∈ Ext(T ), Base(E) is consistent. Consequently, T satisfies consistency. From Amgoud (2012), T is also closed under sub-arguments.

Corollary 44 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under sub-arguments (under naive semantics).

• |Ext n (T )| ≤ |Max( )|

• If is finite, then T has a finite number of naive extensions.

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under sub-arguments. From Theorem 41, it follows that |Ext n (T )| ≤ |Max( )|. If is finite, then it has a finite number of maximal consistent subsets. Thus, the number of naive extensions is finite as well.

Corollary 45 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under subarguments (under naive semantics). If Ext n (T ) = {∅}, then for all x ∈ , CN({x}) is inconsistent.

Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under sub-arguments. Assume that Ext n (T ) = {∅}. Thus, Base(∅) = ∅. From Theorem 41, ∅ ∈ Max( ). Thus, for all x ∈ , CN({x}) is inconsistent.

Corollary 48 Let (L, CN) be adjunctive. Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency and is closed under sub-arguments (under naive semantics). Output(T ) = S i ∈Max( ) CN(S i ). Proof It follows immediately from Theorem 42 and Theorem 46.

Corollary 55 Let T = (Arg( ), R) be an argumentation system over a base such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence (under stable semantics). It holds that Corollary 57 Let T = (Arg( ), R) be an argumentation system over a base such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence (under stable semantics). The equality Ext s (T ) = Ext ss (T ) holds.

Proof Let T = (Arg( ), R) be an argumentation system over a base such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence (under stable semantics). From Corollary 55, |Ext s (T )| > 0. From Caminada (2006b), Ext s (T ) = Ext ss (T ).

Corollary 59 Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence (under preferred semantics). There exists E ∈ Ext p (T ) such that Base(E) ∈ Max( ).

Proof Let T = (Arg( ), R) be an argumentation system such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence (under preferred semantics). Thus, T satisfies the same postulates under stable semantics since Ext s (T ) ⊆ Ext p (T ). Then, |Ext s (T )| > 0. Thus, ∃E ∈ Ext s (T ) and thus E ∈ Ext p (T ). From Theorem 49, Base(E) ∈ Max( ).

Corollary 63 If a knowledge base is finite, then for all T = (Arg( ), R) such that R is conflict-dependent and T satisfies consistency and closure under sub-arguments, Ext p (T ) is finite.

Proof This follows from the compactness of the knowledge base and Theorem 62.

Corollary 66 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 .

Output(T ) =

S i ∈Max( )

CN(S i ).

Proof Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 . From Theorem 65, for all E ∈ Ext p (T ), Base(E) ∈ Max( ). Moreover, since T is closed under both CN and sub-arguments, then Concs(E) = CN(Base(E)). Thus, Output(T ) = S i ∈Max( ) CN(S i ). Corollary 72 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 . IE(T ) = GE(T ) = Arg(Free( )).

Proof Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 3 . From Theorem 71, IE(T ) = Arg(Free( )). Moreover, from Theorem 70, Arg(Free( )) ⊆ GE(T ) (since arguments of Arg(Free( )) are not attacked). Thus, GE(T ) = IE(T ).

Corollary 75 Let T = (Arg( ), R) be an argumentation system such that R ∈ ℜ p 2 . The inclusions Arg(Free( )) ⊆ GE(T ) ⊆ IE(T ) ⊆ S hold for some S ∈ Max( ).

Proof Follows from Theorem 70, Property 9 and Property 68.

  , an argumentation framework consists of a set of arguments and a binary relation expressing attacks among the arguments. Definition 1 (Argumentation framework) An argumentation framework is a pair (A, R) where A is a set of arguments and R ⊆ A × A is an attack relation. A pair (a, b) ∈ R means that a attacks b. A set E ⊆ A attacks an argument b iff ∃a ∈ E such that (a, b) ∈ R. Notations: We sometimes use the infix notation aRb to denote (a, b) ∈ R.

Figure 1 .

 1 Figure 1. Reasoning under naive semantics.

Figure 2 .

 2 Figure 2. Reasoning under stable semantics.

Figure 3 .

 3 Figure 3. Reasoning under preferred semantics.

Example 69

 69 Let us consider the argumentation framework T = (A, R), where • A = {a, b, c, d}. • R = {(a, a), (a, b), (b, a), (c, d), (d, c)}.

Figure 4 .

 4 Figure 4. Reasoning under grounded and ideal semantics.

  |Ext s (T )(T )| = |Max( )|, then from Theorem 49, ∃E ∈ Ext s (T ) such that Base(E) = S. Besides, from the same theorem, E = Arg(Base(E)), thus E = Arg(S). Consequently, Arg(S) ∈ Ext s (T ). Theorem 53 Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R ∈ ℜ s3 . The equality Ext n (T ) = Ext s (T ) holds. If T satisfies the postulates under preferred semantics, then Ext s (T ) = Ext p (T ).

  From Theorem 41, |Ext n (T )| ≤ |Max( )|. Thus, Ext n (T ) = Ext s (T ). Assume now that T satisfies the postulates under preferred semantics, then from Theorem 60, |Ext p (T )| = |Max( )| and Ext s (T ) = Ext p (T ).

E

  i ∈Ext p (T ) E i . So, Sub(a) ⊆ IE(T ). Since T satisfies closure under sub-arguments and CN (under ideal/grounded semantics), then from Proposition 25, Concs(IE(T )) = Concs(GE(T )) = Output(T ) = CN(Free( )).

0

  < |Ext s (T )| ≤ |Max( )|. Proof Let T = (Arg( ), R) be an argumentation system over a knowledge base such that R is conflict-dependent and T satisfies consistency, closure under sub-arguments and free precedence. From Theorem 49, |Ext s (T )| ≤ |Max( )|. From Theorem 50 ℜ s1 = ∅, then |Ext s (T )| > 0. Corollary 56 If is finite, then the set Ext s (T ) is finite, whenever T = (Arg( ), R) satisfies consistency and closure under sub-arguments (under stable semantics). Proof It follows from Corollary 55.

Acknowledgements

The authors are very grateful to the anonymous referee for her/his valuable suggestions for improving the presentation of this work.

Appendix

Property 5 Let X, X ′ , X ′′ ⊆ L.

(1) X ⊆ X ′ ⇒ CN(X ) ⊆ CN(X ′ ).

(

(1) Assume that X ⊆ X ′ . According to the compactness axiom, it holds that

According to the expansion axiom, the following inclusions hold: X ′ ⊆ CN(X ′ ) and X ′′ ⊆ CN(X ′′ ). Thus,

Similarly, X ′′ ⊆ X ∪ X ′′ thus CN(X ′′ ) ⊆ CN(X ∪ X ′′ ) (b'). From (a')