Strong admissibility for abstract dialectical frameworks

1.Introduction

Interest and attention in argumentation theory from researchers in the field of Artificial Intelligence (AI) has been increasing, as witnessed by the wide variety of formalisms to model argumentation and by the variety of semantics proposed to assess the acceptance of arguments [7,57]. Abstract argumentation frameworks (AFs for short) as introduced in the landmark paper by Dung [34] have gained more and more significance in the AI domain. First of all, it has been shown in [34] that AFs are useful to capture the essence of different non-monotonic formalisms. In addition, compared to other non-monotonic formalisms (which are built on top of classical logical syntax), AFs are a much simpler formalism; indeed, they are just directed graphs in which nodes present arguments and directed edges indicate attack relations among arguments. Moreover, AFs are nowadays an integral concept in several advanced argumentation-based formalisms in the sense that their semantics are defined based on a formal connection to Dung’s AFs. Finally, the simplicity of the syntax of AFs has made them an attractive modeling tool in several areas, such as multi-agent systems [44], multi-agent negotiation [3], and legal reasoning [10].

Despite the popularity and simplicity of AFs, these frameworks are used to model argumentation with simple attack relations among arguments. Thus, there exist a number of generalizations of AFs, for instance, modeling group attacks among arguments [48] or modeling preference over the arguments [9,11]. Among all generalizations of AFs, abstract dialectical frameworks (ADFs) were first introduced in [18] and further refined in [14,15,17]. They are expressive generalizations of AFs in which the logical relations among arguments can be represented. This allows researchers to express notions of support, collective attacks, and even more complicated relations. Thanks to their flexibility in formalizing relations between arguments, ADFs have recently been used in several applications; in legal reasoning [1,2,33], online dialog systems [46,47], and text exploration [19].

ADFs have been actively researched [13,16,37,54–56,59]. A key question in formal argumentation is ‘How is it possible to evaluate arguments in a given formalism?’. Answering this question leads to the introduction of several types of semantics. In AFs, different semantics single out coherent subsets of arguments that “fit” together, according to specific criteria [4]. More formally, an AF semantics takes an argumentation framework as input and produces as output a collection of sets of arguments, called extensions. Thus, different semantics reflect different points of view about the acceptance or denial of arguments. Most of the semantics of AFs/ADFs are based on the concept of admissibility.

In AFs, admissibility plays an important role with respect to rationality postulates [24]. Often a new semantics is an improvement of an already existing one by introducing further restrictions on the set of accepted arguments (that are chosen together) or possible attackers. One of the main admissibility-based semantics of AFs is the grounded semantics. First, each AF has a unique grounded extension. Second, the elements of the grounded extension usually belong to other semantics of AFs. The grounded extension collects all unattacked (undoubted) arguments and each argument that can be iteratively supported by these unattacked arguments. Informally, the grounded extension accepts those arguments that no one can avoid to accept; it rejects all the arguments that no one avoid to reject; and it does not have any idea about all other arguments. Thus, no one has any doubt on the acceptance of the arguments that are in the grounded extension. Thus, answering the credulous decision problem under grounded semantics of AFs (i.e., investigating whether a queried argument is part of the grounded extension of a given AF) has a considerable importance.

It has been shown that to answer the credulous decision problem under grounded semantics, not all arguments within the grounded extension are necessary. As a remedy, another set of semantics, namely strong admissibility semantics has been introduced for AFs [8,21,25]. While the grounded extension collects all the arguments of a given AF that can be accepted without any doubt, strongly admissible extensions are subsets of the grounded extension that satisfy the same condition. Actually a strongly admissible extension explains why its arguments can be accepted without any doubt, without presenting further information of all arguments in the grounded extension. In AFs, the concept of strong admissibility semantics has first been defined in the work of Baroni and Giacomin [8], based on the notion of strong defence. Later in [21] this concept was introduced without referring to strong defence. Furthermore, in [25], Caminada and Dunne presented a labelling account of strong admissibility to answer the decision problems of AFs under grounded semantics.

The role and the relevance of strong admissibility semantics and grounded discussion games for AFs has been studied in [21,23,25]. That is, in these works it has been shown that strongly admissible extensions/labellings make a lattice with the maximum element being the grounded extension of a given AF. Therefore, the concept of strong admissibility semantics of AFs relates to grounded semantics of AFs in a similar way as the relation between admissible semantics of AFs and preferred semantics of AFs. That is, to answer the credulous decision problem of AFs under grounded semantics, it is sufficient to solve the decision problem for AFs under strongly admissible semantics, i.e., it is enough to indicate whether there exists a strongly admissible extension that contains a queried argument. Furthermore, it has been shown that the strong admissibility semantics and the corresponding discussion games may be the basis for an algorithm that can be used not only for answering the decision problem but also for human-machine interaction (cf. [12,29]). In addition, the computational complexity of strong admissibility of AFs has been analyzed [26,36].

It has been shown in [14] that each AF can be represented as an ADF; furthermore, it has been shown that ADFs provide all of Dung’s standard semantics, proposed in [34] for AFs, so there is no loss in semantic richness. By the use of general propositional formulas as argument acceptance conditions, ADFs allow for richer relations between arguments than AFs, which only allow attack. Because ADFs are at least as expressive as AFs, they can represent all important problem aspects that AFs can represent. However, some of the semantics of AFs have not yet been introduced for ADFs, namely, strongly admissible semantics. Because of the special structure of ADFs, the definition of strong admissibility semantics of AFs cannot be directly reused in ADFs. Because of the importance of the notion of strongly admissible semantics to investigate the acceptance of a queried argument under the grounded semantics, in the current work we introduce the concept of strongly admissible semantics of ADFs that satisfies/follows the same set of properties as this concept has in AFs, presented in Section 1.1. We do so not only because ADFs are generalisations of AFs, but also because ADFs are expressive enough to model a wide range of non-monotonic knowledge representation languages; furthermore, strongly admissible semantics play an important role in answering the credulous decision problem.

A main characteristic of strongly admissible semantics of ADFs is that they can be used to explain the answer to the question: ‘Why is an argument justified under grounded semantics of ADFs?’. For instance, suppose that an ADF is used to formalize a knowledge-base that presents methods to cure a disease or to make a decision in the legal domain. It is not enough to tell a patient or client that we pick a certain argument since it is presented in a semantics, but they to be convinced why this is the case. Moreover, having automated argumentation systems that can help people to make better choices is a goal of human-machine interaction [32,38]. To persuade agents to perform (or not to perform) a certain action, a user needs to have further explanation about the acceptance of arguments. To address this open problem, we previously considered grounded semantics of ADFs, since no one has any doubt on the evaluation of arguments in the grounded interpretation. Then, as a first remedy in [40], we introduced a discussion game to answer the credulous decision problem of ADFs under grounded semantics without constructing the full grounded interpretation of the given ADF. Subsequently, in the current work we propose the notion of strong admissibility semantics of ADFs. Both methods can be used to explain the truth values of arguments in the grounded interpretation. We think that grounded discussion games of ADFs and strong admissibility semantics of ADFs are two sides of the same coin. However, studying the relation between grounded discussion games, presented in [40], and the strong admissibility semantics of ADFs is beyond the scope of this work and is left for future research.

2.Formal background on argumentation frameworks

We assume that the reader is familiar with Dung’s abstract argumentation frameworks (AFs) [34], thus, we only briefly present the syntax of AFs. We then present the concept of strongly admissible semantics of AFs [8,21,25] and abstract dialectical frameworks (ADFs) [14,17,18].

2.1.Abstract argumentation frameworks

We start the preliminaries to our work by recalling the basic notion of Dung’s abstract argumentation frameworks (AFs). Subsequently, we introduce the extension-based definition of strong admissibility semantics of AFs due to Baroni and Giacomin [8], and the labelling-based definition of this concept due to Caminada and Dunne [25].

Definition 1

Definition 1([34]).

An abstract argumentation framework (AF) is a pair (A,R) in which A is a set of arguments and R⊆A×A is a binary relation representing attacks among arguments.

Let F=(A,R) be a given AF. For each a,b∈A, the relation (a,b)∈R is used to represent that a is an argument attacking the argument b. An argument a∈A is, on the other hand, defended by a set S⊆A of arguments (alternatively, the argument is acceptable with respect to S) (in F) if for each argument c∈A, it holds that if (c,a)∈R then there is an s∈S such that (s,c)∈R (s is called a defender of a). AF F is called a finite argumentation framework if A is a finite set of arguments. Note that in this work we assume that all AFs are finite.

Different semantics of AFs present which sets of arguments in a given AF can be jointly accepted.11 Set S⊆A is called a conflict-free set (extension) (in F) if there are no a,b∈S such that (a,b)∈R. The characteristic function ΓF:2A↦2A is defined as ΓF(S)={a|a is defended by S}.

Definition 2.

Let F=(A,R) be an AF. A conflict-free set S is

• admissible in F if S⊆ΓF(S);

• preferred in F if S is ⊆-maximal admissible;

• complete in F if S=ΓF(S);

• grounded in F if S is the ⊆-least fixed point of ΓF;

• ideal in F if it is a maximal admissible extension that is a subset of each preferred extension.

Example 1.

Let F=({a,b,c},{(a,b),(b,c)}) be an AF. In F, (a,b) means that argument a attacks b, and (b,c) means that b attacks c. Here, argument c is defended by set {a} (alternatively, c is acceptable with respect to {a}), since a attacks the attacker of c, namely b. The set of conflict-free sets of F is cf(F)={∅,{a},{b},{c},{a,c}}. Since ΓF2(∅)={a,c}, the unique grounded extension of F is {a,c}. The intuition is that a is not attacked by any argument, thus no one has any doubt to accept argument a. Argument c is attacked by b, however, it is defended by a, which was accepted by everyone. Thus, {a,c} is the unique grounded extension of F.

Definition 3

Definition 3(from [8]).

Given an argumentation framework F=(A,R), a∈A and S⊆A, it is said that a is strongly defended by S if and only if each attacker c∈A of a is attacked by some s∈S∖{a} such that s is strongly defended by S∖{a}.

In other words, a is strongly defended by S if for any attacker of a there exists a defender s for a in S that is not equal to a, i.e. s≠a, such that s is strongly defended by S∖{a}. In Example 1, argument c is strongly defended by set S={a,c}, since the attacker of c, namely b, is attacked by a∈S∖{c} and a is strongly defended by S∖{c}. Actually, a is strongly defended by S=∅, since a is not attacked by any argument.

Definition 4.

Given an AF (A,R) and set S⊆A, it is said that S is a strongly admissible extension of S if every s∈S is strongly defended by S.

In Example 1, sets S1=∅, S2={a}, and S3={a,c} are strongly admissible extensions of F; all of them are subsets of the grounded extension of F. However, set S′={c} is not a strongly admissible extension of F, since c∈S′ is not strongly defended by S′. Because argument c is attacked by b, however, no argument in S′∖{c} attacks b.

In [25], the concept of strongly admissible semantics of AFs is defined without having to refer to strong defence; we rephrase it in Definition 5, as follows.

Definition 5

Definition 5(from [25]).

Let F=(A,R) be an argumentation framework. We say that S⊆A is a strongly admissible extension of F if and only if every a∈S is defended by some S′⊆S∖{a} which in its turn is a strongly admissible extension.

It is shown in [8] that strongly admissible semantics of an AF forms a lattice with the empty set as the least element and the grounded extension as the maximum element; we recall it in Theorem 1.

Theorem 1

Theorem 1(from [8]).

Let F be an AF. The set of strongly admissible semantics of F forms a lattice with the empty set as the least element and the grounded extension as the maximum element.

Theorem 1 presents a significant result that leads to the distinction between strongly admissible semantics and admissible and complete semantics of AFs. In [34] it is shown that the admissible extensions of a given AF form a semi-lattice with the empty set as the least element and the preferred extensions as its maximal elements. Furthermore, it has been shown in [34] that the complete extensions of a given AF form a semi-lattice with the grounded extension as its least element and the preferred extensions as its maximal elements. Finally, in [25] and [8], the relation between strongly admissible semantics of an AF and its admissible, conflict-free and grounded semantics is clarified; let us recall the properties in Proposition 2.

Proposition 2

Proposition 2(based on [8,25]).

Let F be an AF. The following properties hold for semantics of AF:

• Each strongly admissible extension in F is an admissible extension and a conflict-free extension, however, the other direction does not hold.

• Each strongly admissible extension of F is an admissible extension and it is a subset of the grounded extension of F, however, the other direction does not hold.

Proof.

Let F be an AF.

• In Theorem 4 in [25] it has been proved that each strongly admissible extension in F is an admissible extension and a conflict-free extension. We provide a proof that the other direction does not hold, by giving a counter-example. Let F=({a,b},{(a,b),(b,a)}). Now the set S={a} is a conflict-free and admissible extension of F, however, it is not a strongly admissible extension in F. This is because there is no S′⊆S∖{a} that defends a against the attack of b.

• It has been proved in [8] that the strongly admissible semantics of an AF form a lattice with the grounded extension as the maximum element. However, it does not hold that any admissible extension of a given AF that is a subset of the grounded extension is a strongly admissible extension. We provide a proof by giving a counter-example. Let F=({a,b,c},{(a,b),(b,c),(c,b)}). The grounded extension of F is {a,c}; furthermore, S={c} is an admissible extension of F. However, S is not a strongly admissible extension of F, since there is no S′⊆S∖{c} that defends c against the attack of b. □

The notion of an ideal extension is presented in Definition 2. In Definition 3.48 in [8], first the notion of ideal set is defined, then the notion of ideal semantics is presented; we rephrase this definition here. An admissible extension e is called ideal iff it is a subset of each preferred extension of F. The ideal extension of F is a maximal (with respect to set-inclusion) ideal set. We show that the strongly admissible extensions differ from the ideal sets and the ideal extension of a given AF.

Proposition 3.

The notion of strongly admissible semantics of AFs differs from the notion of ideal semantics of AF.

Proof.

We provide a proof by an example. Let F=({a,b},{(a,b),(b,a),(b,b)}), as depicted in Fig. 1. The unique grounded extension of F is the empty set. The set of strongly admissible extensions of F is {∅}. However, the set of ideal sets of F is {∅,{a}}. Thus, {a} is the ideal extension of F. As we see, the set of strongly admissible extensions of F is neither equal with the set of ideal sets of F nor is it equal with the ideal extension of F.  □

Fig. 1.

AF of Proposition 3.

It is also possible to define the semantics of AFs in terms of argument labellings [20,30,58].

Definition 6

Definition 6([25, Definition 4]).

Let F=(A,R) be an argumentation framework. An argument labelling is a function L:A↦{in,out,undec}. An argument labelling is called an admissible labelling if and only if L is a total function and for each a∈A it holds that:

• if L(a)=in, then for each b that attacks a it holds that L(b)=out,

• if L(a)=out, then there exists a b that attacks a such that L(b)=in.

A labelling account of strong admissibility semantics of F is presented in [25]; we recall this definition in Definition 8, to use it in the proofs of theorems of Section 4, in order to show that strongly admissible semantics of ADFs form a generalization of strongly admissible semantics of AFs. To this end, let us first rephrase the concept of min-max numbering in Definition 7.22

Specifically, in Lemma 22 we use the notion of strongly admissible labelling of AFs, which is defined in terms of min-max numbering (Definition 8) to show that the map of each strongly admissible labelling in a given AF F is a strongly admissible interpretation of the associated ADF DF, and vice versa. That is, we show that there is a one-to-one relation between the set of strongly admissible labellings in a given AF F and the set of strongly admissible interpretations of the associated ADF DF.

Definition 7.

Let L be an admissible labelling of argumentation framework F=(A,R). A min-max numbering is a total function MML:in(L)∪out(L)↦N∪∞ such that for each a∈in(L)∪out(L) it holds that:

• if L(a)=in, then MML(a)=max({MML(b)|(b,a)∈R and L(b)=out})+1 (with max(∅) defined as 0);

• if L(a)=out, then MML(a)=min({MML(b)|(b,a)∈R and L(b)=in})+1 (with min(∅) defined as ∞).

Theorem 4

Theorem 4([25, Theorem 6]).

Every admissible labelling has a unique min-max numbering.

Definition 8

Definition 8([25, Definition 10]).

A strongly admissible labelling is an admissible labelling whose min-max numbering yields natural numbers only (so no argument is numbered ∞).

Example 2.

Let F=({a,b,c,d},{(a,b),(c,d),(d,c)}). By Definition 7, admissible labelling {a↦in,b↦out,c↦in,d↦out} has a unique min-max numbering {(a:1),(b:2),(c:∞),(d:∞)}. However, this admissible labelling is not a strongly admissible labelling in F, since the MML(c)=MML(d)=∞. On the other hand, the admissible labelling {a↦in,b↦out,c↦undec,d↦undec} has a unique min-max numbering {(a:1),(b:2)}, since both MML(a) and MML(b) are finite, so by Definition 8, it is a strongly admissible interpretation in F.

In [6], both extension-based and labelling-based approaches of semantics of AFs are presented. Moreover, two functions are defined to map extension-based semantics of a given AF F to labelling-based semantics and vice versa, to show that each extension-based semantics of AF has a labelling-based semantics reformulation and vice versa. Namely, Ext2Lab(λ) is used to present the extension form of labelling λ of F, and Lab2Ext(e) is used to present the labelling form of the extension e of F; we recall them in Definitions 9–10.

Definition 9

Definition 9([6, Definition 3.6]).

Let F=(A,R) and let S be an extension of F. For a∈A, we write a+={b|(a,b)∈R} and S+=∪{a+|a∈S}. If S is a conflict-free set of F, then the corresponding labelling is defined as Ext2Lab(S)={S,S+,A∖(S∪S+)}.

Function Ext2Lab(.) in Definition 9 is such that arguments of S are labelled in, elements of S+ are labelled out and all other arguments of A are labelled undec. The alternative way of presenting Ext2Lab(.) is as follows.

Ext2Lab(S)(a)=in if a∈S,out if a∈S+,undecotherwise.

Definition 10

Definition 10([6, Definition 2.7]).

Given an argumentation framework F=(A,R) and a labelling λ, the corresponding set of arguments Lab2Ext(λ) is defined as Lab2Ext(λ)=in(λ). That is, Lab2Ext(λ) is the set of all arguments that are labelled in in λ.

Proposition 5

Proposition 5([6, Proposition 3.14]).

For any argumentation framework F=(A,R), it holds that:

• if S is a strongly admissible set of F, then Ext2Lab(S) is a strongly admissible labelling of F;

• if λ is a strongly admissible labelling of F, then Lab2Ext(λ) is a strongly admissible set of F.

2.2.Abstract dialectical frameworks

In the current section, we briefly restate some of the key concepts of abstract dialectical frameworks that are derived from those given in [14,15,17,18].

Definition 11.

An abstract dialectical framework (ADF) is a tuple F=(A,L,C) where:

• A is a set of arguments (statements, positions), denoted by letters;

• L⊆A×A is a set of links between arguments;

• C={φa}a∈A is a collection of propositional formulas over arguments, called acceptance conditions.

An ADF can be represented by a graph in which nodes indicate arguments and links show the relation among arguments. Each argument a in an ADF is labelled by a propositional formula, called acceptance condition, φa over par(a) such that par(a)={b|(b,a)∈L}. An argument a is called an initial argument if par(a)={}. The acceptance condition of an argument clarifies under which condition the argument can be accepted [14,17,18]. Furthermore, acceptance conditions indicate the set of links implicitly. Thus, in a concrete example of ADFs, we oftentimes only define acceptance conditions explicitly and implicitly define links via the variables of the propositional formulas.

Remark.

ADF D=(A,L,C) is called a finite abstract dialectical framework if A is a finite set of arguments. Note that in this work we assume that all ADFs are finite.

Example 3.

An example of an ADF D=(A,L,C) is shown in Fig. 2, which contains four arguments, i.e., A={a,b,c,d}. Dependencies between arguments are shown by the directed edges in the associated graph, and acceptance conditions are shown as propositional formulas attached to each node. The acceptance condition of an argument clarifies the set of parents of the argument, thus, there is no need of presenting L in D explicitly. Furthermore, an acceptance condition of an argument indicates under which condition the argument can be accepted/denied. For instance, the acceptance condition of c, namely φc:¬b∧d, says that c depends on b and d, i.e., par(c)={b,d}, and it states that c can be accepted if b is denied and d is accepted. In this ADF, the arguments a and d are initial arguments, since par(a)=par(d)={}. The acceptance condition of a, namely φa:⊤, says that a is always accepted and the acceptance condition of d, namely φd:⊥, says that d is always denied.

Fig. 2.

ADF of Examples 3, 5 and 7.

An interpretation v (for D) is a function v:A↦{t,f,u} that maps arguments to one of the three truth values true (t), false (f), or undecided (u). The interpretation v is called trivial, and v is denoted by vu, if v(a)=u for each a∈A. Moreover, v is called a two-valued interpretation if for each a∈A either v(a)=t or v(a)=f.

Truth values can be ordered via the information ordering relation <i given by: u<it and u<if and no other pair of truth values are related by <i. Relation ⩽i is the reflexive and transitive closure of <i. The pair ({t,f,u},⩽i) is a complete meet-semilattice with the meet operator ⊓i, such that t⊓it=t and f⊓if=f, while it returns u otherwise. The meet of two interpretations v and w is then defined as (v⊓iw)(a)=v(a)⊓iw(a) for all a∈A.

Let V be the set of all interpretations for an ADF D. It is said that an interpretation v is an extension of another interpretation w, if w(a)⩽iv(a) for each a∈A, denoted by w⩽iv. Furthermore, if both v⩽iw and w⩽iv hold, then v and w are equivalent, denoted by v∼iw. Interpretations v and w are incomparable if neither w≰iv nor v≰iw, denoted by w≁iv.

For reasons of brevity, we will sometimes shorten the notion of three-valued interpretation v={a1↦t1,…,am↦tm} with arguments a1,…,am and truth values t1,…,tm as follows: v={ai|v(ai)=t}∪{¬ai|v(ai)=f}. For instance, v={a↦f,b↦t}={¬a,b}. Furthermore, in the current work we say that the truth value of a is presented in v, if v(a)∈{t,f} also denoted as v(a)=t/f. Interpretations can be ordered via ⩽i with respect to their information content.

Semantics for ADFs can be defined via the characteristic operator ΓD, which maps interpretations to interpretations. Given an interpretation v (for D), the partial valuation of φa by v is v(φa)=φav=φa[b/⊤:v(b)=t][b/⊥:v(b)=f], for b∈par(a).

Definition 12.

Let D be an ADF and let v be an interpretation of D. Applying ΓD on v leads to v′ such that for each a∈A, v′ is as follows:

ΓD(v)(a)=v′(a)=tif φav is irrefutable (i.e., φav is a tautology),fif φav is unsatisfiable (i.e., φav is a contradiction),uotherwise.

Intuitively, the characteristic operator ΓD assigns an argument a to t (f) if the partial evaluation of the acceptance condition of a by a given interpretation is irrefutable (unsatisfiable, respectively). Note that the operator ΓD is ⩽i-monotonic, that is, when v⩽iw for interpretations v and w, then ΓD(v)⩽iΓD(w).

Example 4.

Consider ADF D=({a,b,c,d},{φa:⊤,φb:a∧¬c,φc:¬b∧d,φd:⊥}) from Example 3 and the trivial interpretation vu of D. We calculate v′=ΓD(vu) over all the arguments of D. Consider argument a; since φa:⊤, it holds that φavu:⊤, that is, φavu is irrefutable. Thus, a is assigned to t in v′. However, since both of the parents of b, namely, a and c are assigned to u in vu, it holds that φbvu=φb, which is neither a tautology nor unsatisfiable. Thus, v′(b)=ΓD(vu)(b)=u. By the same reason, it holds that v′(c)=ΓD(vu)(c)=u. However, it holds that φdvu:⊥, that is, φdvu is unsatisfiable. Thus, v′(d)=ΓD(vu)(d)=f. Hence, v′={a↦t,b↦u,c↦u,d↦f}.

If we apply the characteristic operator ΓD over v′, then since ΓD is a monotonic operator, the truth values of a and d in ΓD(v′) are equal to v′(a) and v′(d), respectively. Since φcv′=¬b∧⊥≡⊥, it holds that ΓD(v′)(c)=f. However, since φbv′=⊤∧¬c=¬c, it holds that ΓD(v′)(b)=u. Thus, ΓD(v′)={a↦t,b↦u,c↦f,d↦f}.

The semantics of ADFs, as defined by [15], are based on (collections of) three-valued interpretations and can be defined via the characteristic operator as follows.

Definition 13.

Given an ADF D, an interpretation v is:

• conflict-free iff v(s)=t implies φsv is satisfiable and v(s)=f implies φsv is unsatisfiable;

• admissible in D iff v⩽iΓD(v);

• preferred in D iff v is ⩽i-maximal admissible;

• complete in D iff v=ΓD(v);

• the grounded interpretation of D iff v is the least fixed point of ΓD.

The set of all σ interpretations for an ADF F is denoted by σ(F), where σ∈{cf,adm,prf,com,grd} abbreviate the different semantics in the obvious manner. In any ADF D, it holds that prf(D)⊆com(D)⊆adm(D)⊆cf(D) and grd(D)⊆com(D).

The intuitions behind the semantics of ADFs are as follows. In ADFs an interpretation is called admissible if it does not contain any unjustifiable information. An interpretation is called preferred if it represents maximum information about arguments without losing admissibility. Thus, each admissible interpretation is contained in a preferred interpretation. That is, to answer the credulous decision problem under preferred semantics (i.e., to investigate whether there is a preferred interpretation that contains the truth value of a given argument), it is sufficient to answer the problem under admissible semantics. An interpretation is complete if it exactly contains the relevant justifiable information. Finally, an interpretation is grounded if it collects all the information that is beyond any doubt.

Example 5.

Let us consider again ADF D=({a,b,c,d},{φa:⊤,φb:a∧¬c,φc:¬b∧d,φd:⊥}) from Example 3. Furthermore, consider several three-valued interpretations {v0,v1,v2,v3,v,v′} as shown in Table 1. We investigate whether they are part of certain semantics. Since for each i with 0⩽i⩽3 it holds that vi⩽iΓD(vi), it holds that each vi for i with 0⩽i⩽3 is an admissible interpretation of D. In general, each admissible interpretation is a conflict-free interpretation. Thus, each vi for i with 0⩽i⩽3 is a conflict-free interpretation of D. The interpretation v3 is a complete interpretation of D, since ΓD(v3)=v3. Furthermore, v3 is the grounded interpretation of D, since it the least fixed point of ΓD. In addition, v3 is a maximal admissible interpretation of D, therefore, v3 is a preferred interpretation of D.

Note that the interpretation v is not a(n) admissible/preferred/complete/the grounded interpretation of D, since ΓD(v)={a↦t,b↦u,c↦f,d↦f}, that is, v≰iΓD(v). However, v is a conflict-free interpretation of D. The truth value of b is assigned to t in v. Thus, to show that v is a conflict-free interpretation of D, it is enough to check whether φbv is satisfiable. Since φbv is indeed satisfiable, it holds that v is a conflict-free interpretation of D.

Furthermore, for v′ it holds that ΓD(v′)={a,¬d}. Thus, since v′≰iΓD(v′), it holds that v′ is not a(n) admissible/preferred/complete/the grounded interpretation of D. To check whether v′ is a conflict-free interpretation, we have to check whether φdv′ is satisfiable. Since φdv′≡⊥ is unsatisfiable, it holds that v′ is not a conflict-free interpretation of D.

Table 1

Interpretations for the ADF from Example 5

Interpretation	a	b	c	d	ΓD	Part of semantics
v0=vu	u	u	u	u	ΓD(vu)=v1	cf,adm
v1	t	u	u	f	ΓD(v1)=v2	cf,adm
v2	t	u	f	f	ΓD(v2)=v3	cf,adm
v3	t	t	f	f	ΓD(v3)=v3	cf,adm,prf,grd,com
v	u	t	u	u	ΓD(v)=v2	cf
v′	u	u	u	t	ΓD(v′)=v1	−

The semantics for ADFs generalize the semantics for AFs. Definition 14 presents the associated ADF for a given AF.

Definition 14.

For an AF F=(A,R), define the ADF associated with F as DF=(A,R,C) with C={φa}a∈A such that for each a∈A the acceptance condition is as follows:

φa=⋀(b,a)∈R¬b

For instance, the associated ADF DF to the AF F presented in Example 1, i.e., F=({a,b,c},{(a,b),(b,c)}), is DF=(A,R,{φa:⊤,φb:¬a,φc:¬b}). In [17, Theorem 2], it is shown that: an extension is admissible, complete, preferred, grounded for F iff it is admissible, complete, preferred, grounded for DF. The notion of an argument being acceptable and the symmetric notion of an argument being deniable in an interpretation are defined as follows.

Definition 15.

Let D=(A,L,C) be an ADF and let v be an interpretation of D.

• An argument a∈A is called acceptable with respect to v if φav is irrefutable.

• An argument a∈A is called deniable with respect to v if φav is unsatisfiable.

For instance, considering ADF D of Example 3, it holds that a is acceptable with respect to v={a↦t,b↦u,c↦u,d↦f}.

One of the main decision problems of ADFs is whether an argument is credulously acceptable (deniable) under a type of semantics, presented in Definition 16.

Definition 16.

Given an ADF D=(A,L,C), an argument a∈A and a semantics σ∈{adm,prf,com,cf,grd}. Argument a is credulously acceptable (deniable) under σ if there exists a σ interpretation v of D such that v(a)=t (v(a)=f, respectively). This reasoning task is denoted by Credσ(a↦t/f,D).

Considering ADF of Example 3, it holds that b is credulously acceptable under σ for σ∈{adm,prf,com,cf,grd} in D. This is because v3, as it is shown in Table 1, is a σ-interpretation for σ∈{adm,prf,com,cf,grd} with v3(b)=t. However, b is not credulously deniable under σ for σ∈{adm,prf,com,grd} in D. The only preferred/complete/grounded interpretation of D is v3, which assigns b to t. Thus, b is not credulously deniable under σ-semantics, for σ∈{prf,com,grd}. Since each admissible interpretation must be equally or less informative than a preferred interpretation, b is not credulously deniable under admissible semantics of D.

Thanks to the fact that in an ADF D each preferred interpretation is a ⩽i-maximal admissible (complete) interpretation of D, it holds that the credulous decision problems under admissible, complete, and preferred semantics coincide.

In ADFs, relations between arguments can be classified into four types, reflecting the relationship of attack and/or support that exists between the arguments. These are listed in Definition 17. Further, we denote the update of an interpretation v with a truth value x∈{t,f,u} for an argument b by v|xb, i.e. v|xb(b)=x and v|xb(a)=v(a) for a≠b.

Definition 17.

Let D=(S,L,C) be an ADF. A relation (b,a)∈L is called

• supporting (in D) if for every two-valued interpretation v, v(φa)=t implies v|tb(φa)=t;

• attacking (in D) if for every two-valued interpretation v, v(φa)=f implies v|tb(φa)=f;

• redundant (in D) if it is both attacking and supporting;

• dependent (in D) if it is neither attacking nor supporting.

Example 6.

Consider the acceptance condition of φa:b∨¬c for argument a. By φa the set of parents of a is {b,c}. Thus, we clarify the type of (b,a) and (c,a). There are three satisfying two-valued interpretations, i.e., v1={b↦t,c↦t}, v2={b↦t,c↦f} and v3={b↦f,c↦f}, and one that does not satisfy the formula, i.e., v4={b↦f,c↦t}. By the definition of supporting links we have to check that whether vi(φa)=t for i with 1⩽i⩽3 implies vi|tb(φa)=t. Since for i with 1⩽i⩽3, vi(φa)=t implies vi|tb(φa)=t, it holds that (b,a) is a supporting link. Furthermore, since v4(φa)=f but v4|tb(φa)=t, link (b,a) is not an attack link.

Moreover, since v3(a)=t but v3|tc(φa)=f, it holds that (c,a) is not a support link. However, it holds that v4(φa)=f and v4|tc(φa)=f. Thus, (c,a) is only an attacking link.

As an example for a link that is both attacking and supporting, consider φa:b∨¬b. There are two satisfying two-valued interpretations for the formula, i.e., v1={b↦t} and v2={b↦f}. Since for i with 1⩽i⩽2 it holds that vi(φa)=t implies vi|tb(φa)=t, it holds that (b,a) is a supporting link. Furthermore, since there is no two-valued interpretation that does not satisfy the formula, the link (b,a) is also an attacking link. Thus, (b,a) is a redundant link in φa:b∨¬b.

As an example for a link that is neither an attacking nor supporting, consider φa:(¬c∨b)∧(c∨¬b). Let v={b↦f,c↦f} be a two-valued interpretation that satisfies the formula. However, v|tb(φa)=f. Thus, (b,a) is not a support link. Further, let v={b↦f,c↦t} be a two-valued interpretation that does not satisfy the formula. However, it holds that v|tb(φa)=t. Thus, (b,a) is not an attacking. Hence (b,a) is a dependent link.

3.The strongly admissible semantics for ADFs

In the following, we present the concept of strong admissibility semantics for ADFs. As we discussed in the introduction, we are aiming to generalize the notion of strong admissibility semantics of AFs, so that the concept of strong admissibility semantics of ADFs relates to grounded semantics of ADFs in a similar way as the concept of admissible semantics of ADFs relates to preferred semantics of ADFs. As we mentioned in the introduction, following the definition by Baroni and Giacomin [8], Caminada showed in [21,23] that strong admissibility plays a critical role in discussion games for AFs under grounded semantics [21,25]. In [40], we introduced a discussion game to answer the credulous decision problem of ADFs under grounded semantics without constructing the full grounded interpretation of the given ADF. However, the concept of strong admissibility semantics of ADFs has not been introduced in the literature so far. This was a motivation for us to present the notion of strong admissibility semantics for ADFs and study the characteristics of this concept. Similarly to the AF case, a strongly admissible interpretation of an ADF may be used not only to answer the credulous decision problem, but also to explain why an argument is justified in the grounded interpretation.

In ADFs, beside an argument being acceptable in an interpretation, there is a symmetric notion of an argument being deniable. In contrast with Definition 4, in which the concept of strong admissibility semantics of AFs is defined based on the concept of strongly defended arguments, in ADFs we define the concept of strong admissibility semantics based on the concept of strongly acceptable/deniable arguments. To this end, in Definition 18 we introduce the notion of strong justification (i.e., strongly accepted/denied) of an argument in an ADF in a given interpretation.

Note that in the following, v|P is equal to v(p) for any p∈P; however, it assigns all other arguments that do not belong to P to u, i.e., v|P=vu|v(p)p∈P.

Note that in Definition 18, the set of parents of a can be the empty set, i.e., P=∅. If the set P of parents of an argument is empty, then v|P=vu. In this case, a is strongly acceptable/deniable in v if φavu is irrefutable/unsatisfiable, respectively. In other words, if P=∅, then a is strongly acceptable/deniable in v if a is acceptable/deniable in v and v(a)=t/f. Furthermore, we say that a is not strongly justified in an interpretation v if there is no set of parents of a that satisfies the condition of Definition 18 for a.

Since the class of ADFs is a generalization of the class of AFs (see Definition 14), in the following, we informally discuss why Definition 18 can be viewed as a generalization of Definition 3 for AFs. In Section 4, we formally show that the strongly admissible semantics of ADFs is a proper generalization of strongly admissible semantics of AFs.

In the two items of Definition 18, the set P contains exactly those parents of a, excluding a, that satisfy v(a) and of which the truth value is presented in v. Definition 18 presents the same idea as Definition 3: that an argument a is strongly defended (accepted) if it can be defended by some arguments other than itself. Furthermore, each defender of a has to be strongly defended. Akin to AFs, in ADFs an argument a is strongly justifiable if its truth value is justified by some arguments other than itself, where each of those other arguments is strongly justified.

The notion of strong acceptability/deniability of arguments in a given interpretation is illustrated in Example 7.

Note that in Example 7, if we choose a set of parents of c equal to {b}, then we cannot show that c is strongly deniable in interpretation v. While the first condition of strong deniability holds for c, i.e., φcv|b≡⊥, the second condition does not hold, i.e., b is not strongly acceptable in v, as is shown in Example 7. This shows the importance of choosing a right set of parents that satisfies the conditions of Definition 18 for a queried argument.

However, there exists an alternative definition for strongly justified of arguments, which we present in Definition 31, in which there is no need of indicating a set of parents of a queried argument. In order to prove the main result of this section, which is that the set of strongly admissible interpretations forms a lattice, we need some auxiliary results that are proven based on the current definition of an argument being strongly justified in an interpretation, i.e., Definition 18.

In Definition 19, similar to Definition 4, we introduce the concept of strong admissibility of interpretation v of a given ADF, using the notion of strong justifiability of arguments presented in v.

To clarify the notion of strongly admissible interpretations of ADFs, we continue Example 7 in Example 8.

In Example 8, c is strongly deniable both in v2 and v3, however, v2 presents less information than v3. Interpretation v2 explains that c is strongly deniable in a strongly admissible interpretation, in other words, c is credulously deniable in the grounded interpretation of D, since its parent d is strongly deniable in v2. Based on the acceptance condition of c, namely φc:¬b∧d, this piece of information about parents of c is enough to convince a user about the truth value of c in a strongly admissible interpretation and the grounded interpretation as well. That is, to convince a user about the truth value of c in the grounded interpretation of D, there is no need of further information about the truth values of a and b in the grounded interpretation. We are interested in finding a strongly admissible interpretation with the least amount of information in which the truth value of a queried argument is satisfied.

Note that if argument a is strongly justified in an interpretation, then there exists a strongly admissible interpretation that is a least witness of strong justifiability of a. Intuitively, the reason is that the number of arguments of a given ADF is finite, so one can guess an interpretation v and check whether it the least witness of strong justifiability of a. More formally, to find a least witness of strong justifiability of a, follow the following steps:

Note that an argument may have more than one least witness of strong justification. For instance, let D=({a,b,c},{φa:⊤,φb:a∨b,φc:⊤}). Argument b is strongly acceptable in both v1={a,b} and v2={b,c}; furthermore, by Definition 20, both v1 and v2 are least witnesses of strong justifiability of b in D. We now define the maximum level of a in a least witness of strong justifiability of a; see Definition 21.

For instance, in Example 8, the maximum level of c with respect to the least witness v2 is 2. This is because the maximum level of d in v2 is 1. Intuitively, a least witness v of strong justification of a collects exactly the truth values of those ancestors of a that have a crucial role in the truth value of a. A maximum level of a in v presents the distance of a from an initial ancestor of a that may have an effect on the truth value of a in a strongly admissible interpretation of a given ADF. Example 9 is an instance of an ADF with a redundant link.

Example 9.

Let D=({a,b},{φa:b∨¬b,φb:b}) be an ADF, depicted in Fig. 3. We show that v={a↦t,b↦u} is a strongly admissible interpretation of D. To this end, we show that a is strongly acceptable in v with respect to E={a}. Now let P=∅. It is clear that φavu is irrefutable. Thus, a is strongly acceptable in v. Furthermore, v is a least witness of strong acceptability of a and by Definition 21, the maximum level of a in v is 1.

Fig. 3.

ADF of Examples 9.

Example 10 presents the associated ADF DF to the AF F presented in Example 2.

Lemma 6 shows that if v is a least witness of strong justification of a, then the maximum level of a in v is finite in a given ADF.

Corollary 7 is a direct result of Lemma 6 together with the second item of Definition 21.

Lemma 8 presents the monotonic characteristic of strongly justified arguments, i.e., if a is strongly justifiable in v and v⩽iv′, then a is strongly justifiable in v′.

A sequence of interpretations for a given ADF D, each member of which is strongly admissible, is presented in Lemma 9. In Lemma 10, it is shown that the maximum element of this sequence is the grounded interpretation of D.

In Theorem 11, we show that each strongly admissible interpretation is an admissible interpretation as well as conflict-free. However, the other direction of the following theorem does not work.