Strong admissibility for abstract dialectical frameworks

Abstract

Abstract dialectical frameworks (ADFs) have been introduced as a formalism for modeling argumentation allowing general logical satisfaction conditions and the relevant argument evaluation. Different criteria used to settle the acceptance of arguments are called semantics. Semantics of ADFs have so far mainly been defined based on the concept of admissibility. However, the notion of strongly admissible semantics studied for abstract argumentation frameworks has not yet been introduced for ADFs. In the current work we present the concept of strong admissibility of interpretations for ADFs. Further, we show that strongly admissible interpretations of ADFs form a lattice with the grounded interpretation as the maximal element. We also present algorithms to answer the following decision problems: (1) whether a given interpretation is a strongly admissible interpretation of a given ADF, and (2) whether a given argument is strongly acceptable/deniable in a given interpretation of a given ADF. In addition, we show that the strongly admissible semantics of ADFs forms a proper generalization of the strongly admissible semantics of AFs.

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.

1.1. Requirements of strong admissibility semantics

As mentioned before, it is important to investigate whether a queried argument is in the grounded extension of an AF. This is mainly because each AF has a unique grounded extension and no one has any doubt on the acceptance of the arguments of the grounded extension. Furthermore, in applications it is significant not only to answer whether a queried argument is in the grounded extension but also to explain why it is so.

On the one hand, some discussion games have been presented to answer this decision problem under the grounded semantics [22,23,27,45]. That is, a queried argument belongs to the grounded extension of a given AF iff it is possible to win the associated discussion game. A web-based implementation of grounded discussion games is presented in [12]. On the other hand, the notion of strongly admissible semantics of AFs has been presented in [8,21,25]. to deal with the same issue. Furthermore, the role and the relevance of strong admissibility semantics of AFs in the Standard Grounded Game [45,53] and the Grounded Persuasion Game [27,28] has been studied in [21,25].

Similar to AFs, in ADFs the concept of grounded semantics is an important point of view on the acceptance of arguments. Each ADF has a unique grounded interpretation that presents the truth values of arguments about which no one has any doubt. Thus, it is crucial to investigate the truth value of a queried argument in the grounded interpretation of an ADF. Furthermore, it is required to explain why a queried argument has a specific truth value in the grounded interpretation. To investigate this issue in [40], the notion of discussion game for grounded semantics of ADFs has been presented. This game works locally by considering those ancestors of a certain argument that can affect the evaluation of the argument in the grounded interpretation. In this way, the grounded decision problem can be answered without constructing the full grounded interpretation. However, the notion of strongly admissible semantics has not yet been presented for ADFs to explain the reason for a truth value of a queried argument in the grounded interpretation. We show that the notion of strongly admissible semantics of ADFs presented in this work will satisfy the following conditions, which are akin to the properties of the notion of strongly admissible semantics of AFs.

Strong admissibility is defined in terms of strongly justified arguments.

Strongly justified arguments are recursively reconstructed from their strongly justified parents.

Each ADF has at least one strongly admissible interpretation.

The set of strongly admissible semantics of ADFs forms a lattice with the least element being the trivial interpretation and the maximum element being the grounded interpretation.

Strongly admissible semantics is used to answer whether an argument is justified in the grounded interpretation of a given ADF. This is because this notion has a close relation to the grounded semantics, in the formally precise sense that the maximal element of the lattice of strongly admissible interpretations is the grounded interpretation.

The notion of strongly admissible semantics of ADFs differs from the notions of admissible, conflict-free, complete and grounded semantics of ADFs.

The notion of strongly admissible semantics for ADFs is a proper generalization of strongly admissible semantics for AFs.

Our result leads to the presentation of an algorithm to answer the decision problem whether a given interpretation is a strongly admissible interpretation in a given ADF. In addition, since some generalizations of Dung’s AFs can be seen as special cases of ADFs, for instance, SETAFs [48], as shown in [51,52], and bipolar AFs [31,49,50], the notion of strongly admissible semantics presented for ADFs may carry over to these special cases. However, the focus of this work is to present a formal proof of clarifying the relation between strongly admissible semantics of AFs and ADFs.

This paper is structured as follows. In Section 2, we present the relevant background about AFs and ADFs. Then, in Section 3, the main contribution of our work is to introduce the concept of strongly admissible semantics for ADFs. Subsequently, we show that in each ADF, the set of strongly admissible interpretations forms a lattice with the trivial interpretation as the unique minimal element and the grounded interpretation as the unique maximal element. In Section 4 we show that the concept of strongly admissible semantics of ADFs is a generalization of the notion of strongly admissible semantics of AFs.

Section 5 presents an alternative definition for strongly admissible semantics of ADFs that is presented without referring to strongly justified arguments, when compared to the definition in Section 3. This definition also leads to a straightforward algorithm to answer the verification problem of ADFs under strongly admissible semantics. We also present an alternative definition for investigating whether a given argument is strongly justified in a given interpretation, which does not have the difficulties of the definition of strongly justified of arguments in an interpretation that is presented in Section 3. This method also leads to an algorithm to answer whether a given argument is a strongly justified argument in a given interpretation.

In Section 6, we present a finer relation between the sequence of strongly admissible extensions of a given AF and the sequence of strongly admissible interpretations constructed in the associated ADF. Finally, in Section 7, we present the conclusion of our work and we present some future research questions arising from this work.

A preliminary version of this article appeared as [41,42]. As a first addition to these previous works, we prove that strongly admissible semantics of ADFs form a generalization of strongly admissible semantics of AFs, presented in Section 4. Moreover the present paper contains new technical results including answering the verification problem under strong admissibility semantics of ADFs without considering whether all of the arguments that are presented in the given interpretation are strongly justified, reported in Section 5. In addition, in Section 5, we present a new method to investigate whether a given argument is strongly justified in a given interpretation. Further, in Section 6, we study finer relations between the sequence of strongly admissible extensions constructed based on a given extension of an AF and the sequence of strongly admissible interpretations of the associated ADF.

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 ([34]).

An abstract argumentation framework (AF) is a pair $\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ in which A is a set of arguments and $\mathit{R}\subseteq \mathit{A}\times \mathit{A}$ is a binary relation representing attacks among arguments.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ be a given AF. For each $\mathit{a}\mathrm{,}\mathit{b}\in \mathit{A}$ , the relation $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}$ is used to represent that a is an argument attacking the argument b. An argument $\mathit{a}\in \mathit{A}$ is, on the other hand, defended by a set $\mathit{S}\subseteq \mathit{A}$ of arguments (alternatively, the argument is acceptable with respect to S) (in F) if for each argument $\mathit{c}\in \mathit{A}$ , it holds that if $\mathrm{(}\mathit{c}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}$ then there is an $\mathit{s}\in \mathit{S}$ such that $\mathrm{(}\mathit{s}\mathrm{,}\mathit{c}\mathrm{)}\in \mathit{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.1

¹

The reader interested in several types of semantics of AFs is referred to [5,34].

Set $\mathit{S}\subseteq \mathit{A}$ is called a conflict-free set (extension) (in F) if there are no $\mathit{a}\mathrm{,}\mathit{b}\in \mathit{S}$ such that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}$ . The characteristic function ${\mathrm{\Gamma }}_{\mathit{F}}:2^{\mathit{A}}\mapsto 2^{\mathit{A}}$ is defined as ${\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}=\{\mathit{a}|\mathit{a}\text{ is defended by }\mathit{S}\}$ .

Definition 2.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ be an AF. A conflict-free set S is

admissible in F if $\mathit{S}\subseteq {\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ ;

preferred in F if S is ⊆-maximal admissible;

complete in F if $\mathit{S}={\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ ;

grounded in F if S is the ⊆-least fixed point of ${\mathrm{\Gamma }}_{\mathit{F}}$ ;

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

Example 1.

Let $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\}\mathrm{)}$ be an AF. In F, $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ means that argument a attacks b, and $\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}$ means that b attacks c. Here, argument c is defended by set $\{\mathit{a}\}$ (alternatively, c is acceptable with respect to $\{\mathit{a}\}$ ), since a attacks the attacker of c, namely b. The set of conflict-free sets of F is $\mathit{\text{cf}}\mathrm{(}\mathit{F}\mathrm{)}=\{\varnothing \mathrm{,}\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\mathrm{,}\{\mathit{c}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{c}\}\}$ . Since ${\mathrm{\Gamma }}_{\mathit{F}}^2\mathrm{(}\varnothing \mathrm{)}=\{\mathit{a}\mathrm{,}\mathit{c}\}$ , the unique grounded extension of F is $\{\mathit{a}\mathrm{,}\mathit{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, $\{\mathit{a}\mathrm{,}\mathit{c}\}$ is the unique grounded extension of F.

Definition 3 (from [8]).

Given an argumentation framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ , $\mathit{a}\in \mathit{A}$ and $\mathit{S}\subseteq \mathit{A}$ , it is said that a is strongly defended by S if and only if each attacker $\mathit{c}\in \mathit{A}$ of a is attacked by some $\mathit{s}\in \mathit{S}\setminus \{\mathit{a}\}$ such that s is strongly defended by $\mathit{S}\setminus \{\mathit{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. $\mathit{s}\ne \mathit{a}$ , such that s is strongly defended by $\mathit{S}\setminus \{\mathit{a}\}$ . In Example 1, argument c is strongly defended by set $\mathit{S}=\{\mathit{a}\mathrm{,}\mathit{c}\}$ , since the attacker of c, namely b, is attacked by $\mathit{a}\in \mathit{S}\setminus \{\mathit{c}\}$ and a is strongly defended by $\mathit{S}\setminus \{\mathit{c}\}$ . Actually, a is strongly defended by $\mathit{S}=\varnothing$ , since a is not attacked by any argument.

Definition 4.

Given an AF $\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ and set $\mathit{S}\subseteq \mathit{A}$ , it is said that S is a strongly admissible extension of S if every $\mathit{s}\in \mathit{S}$ is strongly defended by S.

In Example 1, sets ${\mathit{S}}_1=\varnothing$ , ${\mathit{S}}_2=\{\mathit{a}\}$ , and ${\mathit{S}}_3=\{\mathit{a}\mathrm{,}\mathit{c}\}$ are strongly admissible extensions of F; all of them are subsets of the grounded extension of F. However, set ${\mathit{S}}^{\prime }=\{\mathit{c}\}$ is not a strongly admissible extension of F, since $\mathit{c}\in {\mathit{S}}^{\prime }$ is not strongly defended by ${\mathit{S}}^{\prime }$ . Because argument c is attacked by b, however, no argument in ${\mathit{S}}^{\prime }\setminus \{\mathit{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 (from [25]).

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ be an argumentation framework. We say that $\mathit{S}\subseteq \mathit{A}$ is a strongly admissible extension of F if and only if every $\mathit{a}\in \mathit{S}$ is defended by some ${\mathit{S}}^{\prime }\subseteq \mathit{S}\setminus \{\mathit{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 (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 (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 $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\}\mathrm{)}$ . Now the set $\mathit{S}=\{\mathit{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 ${\mathit{S}}^{\prime }\subseteq \mathit{S}\setminus \{\mathit{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 $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}$ . The grounded extension of F is $\{\mathit{a}\mathrm{,}\mathit{c}\}$ ; furthermore, $\mathit{S}=\{\mathit{c}\}$ is an admissible extension of F. However, S is not a strongly admissible extension of F, since there is no ${\mathit{S}}^{\prime }\subseteq \mathit{S}\setminus \{\mathit{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 $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}$ , as depicted in Fig. 1. The unique grounded extension of F is the empty set. The set of strongly admissible extensions of F is $\{\varnothing \}$ . However, the set of ideal sets of F is $\{\varnothing \mathrm{,}\{\mathit{a}\}\}$ . Thus, $\{\mathit{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 ([25, Definition 4]).

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

if $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{in}$ , then for each b that attacks a it holds that $\mathcal{L}\mathrm{(}\mathit{b}\mathrm{)}=\mathtt{out}$ ,

if $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{out}$ , then there exists a b that attacks a such that $\mathcal{L}\mathrm{(}\mathit{b}\mathrm{)}=\mathtt{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.2

²

Caminada and Dunne [25] describe the intuition behind the min-max number of an argument as follows: ‘The game-theoretic length of the path (consisting of alternately $\mathtt{in}$ and $\mathtt{out}$ labelled arguments) from the argument back to an unattacked ancestor argument. The player selecting the $\mathtt{in}$ labelled arguments aims to make the path as short as possible whereas the player selecting the $\mathtt{out}$ labelled arguments aims to make the path as long as possible.’

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 ${\mathit{D}}_{\mathit{F}}$ , 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 ${\mathit{D}}_{\mathit{F}}$ .

Definition 7.

Let $\mathcal{L}$ be an admissible labelling of argumentation framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ . A min-max numbering is a total function $\mathcal{M}{\mathcal{M}}_{\mathcal{L}}:\mathtt{in}\mathrm{(}\mathcal{L}\mathrm{)}\cup \mathtt{out}\mathrm{(}\mathcal{L}\mathrm{)}\mapsto \mathbb{N}\cup \infty$ such that for each $\mathit{a}\in \mathtt{in}\mathrm{(}\mathcal{L}\mathrm{)}\cup \mathtt{out}\mathrm{(}\mathcal{L}\mathrm{)}$ it holds that:

if $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{in}$ , then $\mathcal{M}{\mathcal{M}}_{\mathcal{L}}\mathrm{(}\mathit{a}\mathrm{)}=max\mathrm{(}\{\mathcal{M}{\mathcal{M}}_{\mathcal{L}}\mathrm{(}\mathit{b}\mathrm{)}|\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}\text{ and }\mathcal{L}\mathrm{(}\mathit{b}\mathrm{)}=\mathtt{out}\}\mathrm{)}+1$ (with $max\mathrm{(}\varnothing \mathrm{)}$ defined as 0);

if $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{out}$ , then $\mathcal{M}{\mathcal{M}}_{\mathcal{L}}\mathrm{(}\mathit{a}\mathrm{)}=min\mathrm{(}\{\mathcal{M}{\mathcal{M}}_{\mathcal{L}}\mathrm{(}\mathit{b}\mathrm{)}|\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}\text{ and }\mathcal{L}\mathrm{(}\mathit{b}\mathrm{)}=\mathtt{in}\}\mathrm{)}+1$ (with $min\mathrm{(}\varnothing \mathrm{)}$ defined as ∞).

Theorem 4 ([25, Theorem 6]).

Every admissible labelling has a unique min-max numbering.

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 $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathit{c}\mathrm{)}\}\mathrm{)}$ . By Definition 7, admissible labelling $\{\mathit{a}\mapsto \mathtt{in}\mathrm{,}\mathit{b}\mapsto \mathtt{out}\mathrm{,}\mathit{c}\mapsto \mathtt{in}\mathrm{,}\mathit{d}\mapsto \mathtt{out}\}$ has a unique min-max numbering $\{\mathrm{(}\mathit{a}:1\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}:2\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}:\infty \mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}:\infty \mathrm{)}\}$ . However, this admissible labelling is not a strongly admissible labelling in F, since the $\mathcal{M}{\mathcal{M}}_{\mathcal{L}}\mathrm{(}\mathit{c}\mathrm{)}=\mathcal{M}{\mathcal{M}}_{\mathcal{L}}\mathrm{(}\mathit{d}\mathrm{)}=\infty$ . On the other hand, the admissible labelling $\{\mathit{a}\mapsto \mathtt{in}\mathrm{,}\mathit{b}\mapsto \mathtt{out}\mathrm{,}\mathit{c}\mapsto \mathtt{undec}\mathrm{,}\mathit{d}\mapsto \mathtt{undec}\}$ has a unique min-max numbering $\{\mathrm{(}\mathit{a}:1\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}:2\mathrm{)}\}$ , since both $\mathcal{M}{\mathcal{M}}_{\mathcal{L}}\mathrm{(}\mathit{a}\mathrm{)}$ and $\mathcal{M}{\mathcal{M}}_{\mathcal{L}}\mathrm{(}\mathit{b}\mathrm{)}$ 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, $\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ is used to present the extension form of labelling λ of F, and $\mathit{\text{Lab2Ext}}\mathrm{(}\mathit{e}\mathrm{)}$ is used to present the labelling form of the extension e of F; we recall them in Definitions 9–10.

Definition 9 ([6, Definition 3.6]).

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ and let S be an extension of F. For $\mathit{a}\in \mathit{A}$ , we write ${\mathit{a}}^{+}=\{\mathit{b}|\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}\}$ and ${\mathit{S}}^{+}=\cup \{{\mathit{a}}^{+}|\mathit{a}\in \mathit{S}\}$ . If S is a conflict-free set of F, then the corresponding labelling is defined as $\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}=\{\mathit{S}\mathrm{,}{\mathit{S}}^{+}\mathrm{,}\mathit{A}\setminus \mathrm{(}\mathit{S}\cup {\mathit{S}}^{+}\mathrm{)}\}$ .

Function $\mathit{\text{Ext2Lab}}\mathrm{(}.\mathrm{)}$ in Definition 9 is such that arguments of S are labelled $\mathtt{in}$ , elements of ${\mathit{S}}^{+}$ are labelled $\mathtt{out}$ and all other arguments of A are labelled $\mathtt{undec}$ . The alternative way of presenting $\mathit{\text{Ext2Lab}}\mathrm{(}.\mathrm{)}$ is as follows. $$\begin{array}{c}\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\left\{\begin{array}{cc}\mathtt{in}\hfill & \text{ if }\mathit{a}\in \mathit{S}\mathrm{,}\hfill \\ \mathtt{out}\hfill & \text{ if }\mathit{a}\in {\mathit{S}}^{+}\mathrm{,}\hfill \\ \mathtt{undec}\hfill & \text{otherwise.}\hfill \end{array}\right.\end{array}$$

Definition 10 ([6, Definition 2.7]).

Given an argumentation framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ and a labelling λ, the corresponding set of arguments $\mathit{\text{Lab2Ext}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ is defined as $\mathit{\text{Lab2Ext}}\mathrm{(}\mathit{\lambda }\mathrm{)}=\mathtt{in}\mathrm{(}\mathit{\lambda }\mathrm{)}$ . That is, $\mathit{\text{Lab2Ext}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ is the set of all arguments that are labelled $\mathtt{in}$ in λ.

Proposition 5 ([6, Proposition 3.14]).

For any argumentation framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ , it holds that:

if S is a strongly admissible set of F, then $\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}$ is a strongly admissible labelling of F;

if λ is a strongly admissible labelling of F, then $\mathit{\text{Lab2Ext}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ 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 $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ where:

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

$\mathit{L}\subseteq \mathit{A}\times \mathit{A}$ is a set of links between arguments;

$\mathit{C}={\{{\mathit{\phi }}_{\mathit{a}}\}}_{\mathit{a}\in \mathit{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, ${\mathit{\phi }}_{\mathit{a}}$ over $\mathit{par}\mathrm{(}\mathit{a}\mathrm{)}$ such that $\mathit{par}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{b}|\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{L}\}$ . An argument a is called an initial argument if $\mathit{par}\mathrm{(}\mathit{a}\mathrm{)}=\{\}$ . 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 $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ 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 $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ is shown in Fig. 2, which contains four arguments, i.e., $\mathit{A}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{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 ${\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{d}$ , says that c depends on b and d, i.e., $\mathit{par}\mathrm{(}\mathit{c}\mathrm{)}=\{\mathit{b}\mathrm{,}\mathit{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 $\mathit{par}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{par}\mathrm{(}\mathit{d}\mathrm{)}=\{\}$ . The acceptance condition of a, namely ${\mathit{\phi }}_{\mathit{a}}:\top$ , says that a is always accepted and the acceptance condition of d, namely ${\mathit{\phi }}_{\mathit{d}}:\perp$ , says that d is always denied.

Fig. 2.

ADF of Examples 3, 5 and 7.

An interpretation v (for D) is a function $\mathit{v}:\mathit{A}\mapsto \{\mathbf{t}\mathrm{,}\mathbf{f}\mathrm{,}\mathbf{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 ${\mathit{v}}_{\mathbf{u}}$ , if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ for each $\mathit{a}\in \mathit{A}$ . Moreover, v is called a two-valued interpretation if for each $\mathit{a}\in \mathit{A}$ either $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ or $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ .

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

Let $\mathcal{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 $\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}{⩽}_{\mathit{i}}\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}$ for each $\mathit{a}\in \mathit{A}$ , denoted by $\mathit{w}{⩽}_{\mathit{i}}\mathit{v}$ . Furthermore, if both $\mathit{v}{⩽}_{\mathit{i}}\mathit{w}$ and $\mathit{w}{⩽}_{\mathit{i}}\mathit{v}$ hold, then v and w are equivalent, denoted by $\mathit{v}{\sim }_{\mathit{i}}\mathit{w}$ . Interpretations v and w are incomparable if neither $\mathit{w}{\nleqq }_{\mathit{i}}\mathit{v}$ nor $\mathit{v}{\nleqq }_{\mathit{i}}\mathit{w}$ , denoted by $\mathit{w}{\nsim }_{\mathit{i}}\mathit{v}$ .

For reasons of brevity, we will sometimes shorten the notion of three-valued interpretation $\mathit{v}=\{{\mathit{a}}_1\mapsto {\mathit{t}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}\mapsto {\mathit{t}}_{\mathit{m}}\}$ with arguments ${\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}$ and truth values ${\mathit{t}}_1\mathrm{,}\dots \mathrm{,}{\mathit{t}}_{\mathit{m}}$ as follows: $\mathit{v}=\{{\mathit{a}}_{\mathit{i}}|\mathit{v}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathbf{t}\}\cup \{\neg {\mathit{a}}_{\mathit{i}}|\mathit{v}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathbf{f}\}$ . For instance, $\mathit{v}=\{\mathit{a}\mapsto \mathbf{f}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\}=\{\neg \mathit{a}\mathrm{,}\mathit{b}\}$ . Furthermore, in the current work we say that the truth value of a is presented in v, if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ also denoted as $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . Interpretations can be ordered via ${⩽}_{\mathit{i}}$ with respect to their information content.

Semantics for ADFs can be defined via the characteristic operator ${\mathrm{\Gamma }}_{\mathit{D}}$ , which maps interpretations to interpretations. Given an interpretation v (for D), the partial valuation of ${\mathit{\phi }}_{\mathit{a}}$ by v is $\mathit{v}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}={\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}={\mathit{\phi }}_{\mathit{a}}[\mathit{b}\mathrm{/}\top :\mathit{v}\mathrm{(}\mathit{b}\mathrm{)}=\mathbf{t}][\mathit{b}\mathrm{/}\perp :\mathit{v}\mathrm{(}\mathit{b}\mathrm{)}=\mathbf{f}]$ , for $\mathit{b}\in \mathit{par}\mathrm{(}\mathit{a}\mathrm{)}$ .

Definition 12.

Let D be an ADF and let v be an interpretation of D. Applying ${\mathrm{\Gamma }}_{\mathit{D}}$ on v leads to ${\mathit{v}}^{\prime }$ such that for each $\mathit{a}\in \mathit{A}$ , ${\mathit{v}}^{\prime }$ is as follows: $$\begin{array}{c}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}={\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\left\{\begin{array}{cc}\mathbf{t}\hfill & \text{if }{\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}\text{ is irrefutable (i.e., }{\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}\text{ is a tautology)}\mathrm{,}\hfill \\ \mathbf{f}\hfill & \text{if }{\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}\text{ is unsatisfiable (i.e., }{\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}\text{ is a contradiction)}\mathrm{,}\hfill \\ \mathbf{u}\hfill & \text{otherwise.}\hfill \end{array}\right.\end{array}$$

Intuitively, the characteristic operator ${\mathrm{\Gamma }}_{\mathit{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 ${\mathrm{\Gamma }}_{\mathit{D}}$ is ${⩽}_{\mathit{i}}$ -monotonic, that is, when $\mathit{v}{⩽}_{\mathit{i}}\mathit{w}$ for interpretations v and w, then ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{w}\mathrm{)}$ .

Example 4.

Consider ADF $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{a}\wedge \neg \mathit{c}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{d}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\perp \}\mathrm{)}$ from Example 3 and the trivial interpretation ${\mathit{v}}_{\mathbf{u}}$ of D. We calculate ${\mathit{v}}^{\prime }={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ over all the arguments of D. Consider argument a; since ${\mathit{\phi }}_{\mathit{a}}:\top$ , it holds that ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}:\top$ , that is, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}$ is irrefutable. Thus, a is assigned to t in ${\mathit{v}}^{\prime }$ . However, since both of the parents of b, namely, a and c are assigned to u in ${\mathit{v}}_{\mathbf{u}}$ , it holds that ${\mathit{\phi }}_{\mathit{b}}^{{\mathit{v}}_{\mathbf{u}}}={\mathit{\phi }}_{\mathit{b}}$ , which is neither a tautology nor unsatisfiable. Thus, ${\mathit{v}}^{\prime }\mathrm{(}\mathit{b}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}=\mathbf{u}$ . By the same reason, it holds that ${\mathit{v}}^{\prime }\mathrm{(}\mathit{c}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{c}\mathrm{)}=\mathbf{u}$ . However, it holds that ${\mathit{\phi }}_{\mathit{d}}^{{\mathit{v}}_{\mathbf{u}}}:\perp$ , that is, ${\mathit{\phi }}_{\mathit{d}}^{{\mathit{v}}_{\mathbf{u}}}$ is unsatisfiable. Thus, ${\mathit{v}}^{\prime }\mathrm{(}\mathit{d}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{d}\mathrm{)}=\mathbf{f}$ . Hence, ${\mathit{v}}^{\prime }=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ .

If we apply the characteristic operator ${\mathrm{\Gamma }}_{\mathit{D}}$ over ${\mathit{v}}^{\prime }$ , then since ${\mathrm{\Gamma }}_{\mathit{D}}$ is a monotonic operator, the truth values of a and d in ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{)}$ are equal to ${\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}$ and ${\mathit{v}}^{\prime }\mathrm{(}\mathit{d}\mathrm{)}$ , respectively. Since ${\mathit{\phi }}_{\mathit{c}}^{{\mathit{v}}^{\prime }}=\neg \mathit{b}\wedge \perp \equiv \perp$ , it holds that ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{)}\mathrm{(}\mathit{c}\mathrm{)}=\mathbf{f}$ . However, since ${\mathit{\phi }}_{\mathit{b}}^{{\mathit{v}}^{\prime }}=\top \wedge \neg \mathit{c}=\neg \mathit{c}$ , it holds that ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}=\mathbf{u}$ . Thus, ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{)}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{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 $\mathit{v}\mathrm{(}\mathit{s}\mathrm{)}=\mathbf{t}$ implies ${\mathit{\phi }}_{\mathit{s}}^{\mathit{v}}$ is satisfiable and $\mathit{v}\mathrm{(}\mathit{s}\mathrm{)}=\mathbf{f}$ implies ${\mathit{\phi }}_{\mathit{s}}^{\mathit{v}}$ is unsatisfiable;

admissible in D iff $\mathit{v}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}$ ;

preferred in D iff v is ${⩽}_{\mathit{i}}$ -maximal admissible;

complete in D iff $\mathit{v}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}$ ;

the grounded interpretation of D iff v is the least fixed point of ${\mathrm{\Gamma }}_{\mathit{D}}$ .

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

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 $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{a}\wedge \neg \mathit{c}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{d}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\perp \}\mathrm{)}$ from Example 3. Furthermore, consider several three-valued interpretations $\{{\mathit{v}}_0\mathrm{,}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{,}{\mathit{v}}_3\mathrm{,}\mathit{v}\mathrm{,}{\mathit{v}}^{\prime }\}$ as shown in Table 1. We investigate whether they are part of certain semantics. Since for each i with $0⩽\mathit{i}⩽3$ it holds that ${\mathit{v}}_{\mathit{i}}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathit{i}}\mathrm{)}$ , it holds that each ${\mathit{v}}_{\mathit{i}}$ for i with $0⩽\mathit{i}⩽3$ is an admissible interpretation of D. In general, each admissible interpretation is a conflict-free interpretation. Thus, each ${\mathit{v}}_{\mathit{i}}$ for i with $0⩽\mathit{i}⩽3$ is a conflict-free interpretation of D. The interpretation ${\mathit{v}}_3$ is a complete interpretation of D, since ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_3\mathrm{)}={\mathit{v}}_3$ . Furthermore, ${\mathit{v}}_3$ is the grounded interpretation of D, since it the least fixed point of ${\mathrm{\Gamma }}_{\mathit{D}}$ . In addition, ${\mathit{v}}_3$ is a maximal admissible interpretation of D, therefore, ${\mathit{v}}_3$ is a preferred interpretation of D.

Note that the interpretation v is not a(n) admissible/preferred/complete/the grounded interpretation of D, since ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ , that is, $\mathit{v}{\nleqq }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}$ . 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 ${\mathit{\phi }}_{\mathit{b}}^{\mathit{v}}$ is satisfiable. Since ${\mathit{\phi }}_{\mathit{b}}^{\mathit{v}}$ is indeed satisfiable, it holds that v is a conflict-free interpretation of D.

Furthermore, for ${\mathit{v}}^{\prime }$ it holds that ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{)}=\{\mathit{a}\mathrm{,}\neg \mathit{d}\}$ . Thus, since ${\mathit{v}}^{\prime }{\nleqq }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{)}$ , it holds that ${\mathit{v}}^{\prime }$ is not a(n) admissible/preferred/complete/the grounded interpretation of D. To check whether ${\mathit{v}}^{\prime }$ is a conflict-free interpretation, we have to check whether ${\mathit{\phi }}_{\mathit{d}}^{{\mathit{v}}^{\prime }}$ is satisfiable. Since ${\mathit{\phi }}_{\mathit{d}}^{{\mathit{v}}^{\prime }}\equiv \perp$ is unsatisfiable, it holds that ${\mathit{v}}^{\prime }$ is not a conflict-free interpretation of D.

Table 1

Interpretations for the ADF from Example 5

Interpretation	a	b	c	d	${\mathrm{\Gamma }}_{\mathit{D}}$	Part of semantics
${\mathit{v}}_0={\mathit{v}}_{\mathbf{u}}$	u	u	u	u	${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}={\mathit{v}}_1$	$\mathit{\text{cf}}\mathrm{,}\mathit{\text{adm}}$
${\mathit{v}}_1$	t	u	u	f	${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_1\mathrm{)}={\mathit{v}}_2$	$\mathit{\text{cf}}\mathrm{,}\mathit{\text{adm}}$
${\mathit{v}}_2$	t	u	f	f	${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_2\mathrm{)}={\mathit{v}}_3$	$\mathit{\text{cf}}\mathrm{,}\mathit{\text{adm}}$
${\mathit{v}}_3$	t	t	f	f	${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_3\mathrm{)}={\mathit{v}}_3$	$\mathit{\text{cf}}\mathrm{,}\mathit{\text{adm}}\mathrm{,}\mathit{\text{prf}}\mathrm{,}\mathit{\text{grd}}\mathrm{,}\mathit{\text{com}}$
v	u	t	u	u	${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}={\mathit{v}}_2$	$\mathit{\text{cf}}$
${\mathit{v}}^{\prime }$	u	u	u	t	${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{)}={\mathit{v}}_1$	−

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

Definition 14.

For an AF $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ , define the ADF associated with F as ${\mathit{D}}_{\mathit{F}}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{,}\mathit{C}\mathrm{)}$ with $\mathit{C}={\{{\mathit{\phi }}_{\mathit{a}}\}}_{\mathit{a}\in \mathit{A}}$ such that for each $\mathit{a}\in \mathit{A}$ the acceptance condition is as follows: $${\mathit{\phi }}_{\mathit{a}}=\underset{\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}}{{\displaystyle \bigwedge }}\neg \mathit{b}$$

For instance, the associated ADF ${\mathit{D}}_{\mathit{F}}$ to the AF F presented in Example 1, i.e., $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\}\mathrm{)}$ , is ${\mathit{D}}_{\mathit{F}}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\neg \mathit{a}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\}\mathrm{)}$ . 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 ${\mathit{D}}_{\mathit{F}}$ . 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 $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF and let v be an interpretation of D.

An argument $\mathit{a}\in \mathit{A}$ is called acceptable with respect to v if ${\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}$ is irrefutable.

An argument $\mathit{a}\in \mathit{A}$ is called deniable with respect to v if ${\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}$ is unsatisfiable.

For instance, considering ADF D of Example 3, it holds that a is acceptable with respect to $\mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{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 $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ , an argument $\mathit{a}\in \mathit{A}$ and a semantics $\mathit{\sigma }\in \{\mathit{\text{adm}}\mathrm{,}\mathit{\text{prf}}\mathrm{,}\mathit{\text{com}}\mathrm{,}\mathit{\text{cf}}\mathrm{,}\mathit{\text{grd}}\}$ . Argument a is credulously acceptable (deniable) under σ if there exists a σ interpretation v of D such that $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ ( $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ , respectively). This reasoning task is denoted by ${\mathit{\text{Cred}}}_{\mathit{\sigma }}\mathrm{(}\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\mathrm{,}\mathit{D}\mathrm{)}$ .

Considering ADF of Example 3, it holds that b is credulously acceptable under σ for $\mathit{\sigma }\in \{\mathit{\text{adm}}\mathrm{,}\mathit{\text{prf}}\mathrm{,}\mathit{\text{com}}\mathrm{,}\mathit{\text{cf}}\mathrm{,}\mathit{\text{grd}}\}$ in D. This is because ${\mathit{v}}_3$ , as it is shown in Table 1, is a σ-interpretation for $\mathit{\sigma }\in \{\mathit{\text{adm}}\mathrm{,}\mathit{\text{prf}}\mathrm{,}\mathit{\text{com}}\mathrm{,}\mathit{\text{cf}}\mathrm{,}\mathit{\text{grd}}\}$ with ${\mathit{v}}_3\mathrm{(}\mathit{b}\mathrm{)}=\mathbf{t}$ . However, b is not credulously deniable under σ for $\mathit{\sigma }\in \{\mathit{\text{adm}}\mathrm{,}\mathit{\text{prf}}\mathrm{,}\mathit{\text{com}}\mathrm{,}\mathit{\text{grd}}\}$ in D. The only preferred/complete/grounded interpretation of D is ${\mathit{v}}_3$ , which assigns b to t. Thus, b is not credulously deniable under σ-semantics, for $\mathit{\sigma }\in \{\mathit{\text{prf}}\mathrm{,}\mathit{\text{com}}\mathrm{,}\mathit{\text{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 ${⩽}_{\mathit{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 $\mathit{x}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\mathrm{,}\mathbf{u}\}$ for an argument b by $\mathit{v}{|}_{\mathit{x}}^{\mathit{b}}$ , i.e. $\mathit{v}{|}_{\mathit{x}}^{\mathit{b}}\mathrm{(}\mathit{b}\mathrm{)}=\mathit{x}$ and $\mathit{v}{|}_{\mathit{x}}^{\mathit{b}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}$ for $\mathit{a}\ne \mathit{b}$ . Definition 17.

Let $\mathit{D}=\mathrm{(}\mathit{S}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF. A relation $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{L}$ is called

supporting (in D) if for every two-valued interpretation v, $\mathit{v}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ implies $\mathit{v}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ ;

attacking (in D) if for every two-valued interpretation v, $\mathit{v}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{f}$ implies $\mathit{v}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{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 ${\mathit{\phi }}_{\mathit{a}}:\mathit{b}\vee \neg \mathit{c}$ for argument a. By ${\mathit{\phi }}_{\mathit{a}}$ the set of parents of a is $\{\mathit{b}\mathrm{,}\mathit{c}\}$ . Thus, we clarify the type of $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ and $\mathrm{(}\mathit{c}\mathrm{,}\mathit{a}\mathrm{)}$ . There are three satisfying two-valued interpretations, i.e., ${\mathit{v}}_1=\{\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\}$ , ${\mathit{v}}_2=\{\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\}$ and ${\mathit{v}}_3=\{\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\}$ , and one that does not satisfy the formula, i.e., ${\mathit{v}}_4=\{\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\}$ . By the definition of supporting links we have to check that whether ${\mathit{v}}_{\mathit{i}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ for i with $1⩽\mathit{i}⩽3$ implies ${\mathit{v}}_{\mathit{i}}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ . Since for i with $1⩽\mathit{i}⩽3$ , ${\mathit{v}}_{\mathit{i}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ implies ${\mathit{v}}_{\mathit{i}}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ , it holds that $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ is a supporting link. Furthermore, since ${\mathit{v}}_4\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{f}$ but ${\mathit{v}}_4{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ , link $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ is not an attack link.

Moreover, since ${\mathit{v}}_3\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ but ${\mathit{v}}_3{|}_{\mathbf{t}}^{\mathit{c}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{f}$ , it holds that $\mathrm{(}\mathit{c}\mathrm{,}\mathit{a}\mathrm{)}$ is not a support link. However, it holds that ${\mathit{v}}_4\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{f}$ and ${\mathit{v}}_4{|}_{\mathbf{t}}^{\mathit{c}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{f}$ . Thus, $\mathrm{(}\mathit{c}\mathrm{,}\mathit{a}\mathrm{)}$ is only an attacking link.

As an example for a link that is both attacking and supporting, consider ${\mathit{\phi }}_{\mathit{a}}:\mathit{b}\vee \neg \mathit{b}$ . There are two satisfying two-valued interpretations for the formula, i.e., ${\mathit{v}}_1=\{\mathit{b}\mapsto \mathbf{t}\}$ and ${\mathit{v}}_2=\{\mathit{b}\mapsto \mathbf{f}\}$ . Since for i with $1⩽\mathit{i}⩽2$ it holds that ${\mathit{v}}_{\mathit{i}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ implies ${\mathit{v}}_{\mathit{i}}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ , it holds that $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ is a supporting link. Furthermore, since there is no two-valued interpretation that does not satisfy the formula, the link $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ is also an attacking link. Thus, $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ is a redundant link in ${\mathit{\phi }}_{\mathit{a}}:\mathit{b}\vee \neg \mathit{b}$ .

As an example for a link that is neither an attacking nor supporting, consider ${\mathit{\phi }}_{\mathit{a}}:\mathrm{(}\neg \mathit{c}\vee \mathit{b}\mathrm{)}\wedge \mathrm{(}\mathit{c}\vee \neg \mathit{b}\mathrm{)}$ . Let $\mathit{v}=\{\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\}$ be a two-valued interpretation that satisfies the formula. However, $\mathit{v}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{f}$ . Thus, $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ is not a support link. Further, let $\mathit{v}=\{\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\}$ be a two-valued interpretation that does not satisfy the formula. However, it holds that $\mathit{v}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ . Thus, $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ is not an attacking. Hence $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ 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, ${\mathit{v}}_{{|}_{\mathit{P}}}$ is equal to $\mathit{v}\mathrm{(}\mathit{p}\mathrm{)}$ for any $\mathit{p}\in \mathit{P}$ ; however, it assigns all other arguments that do not belong to P to u, i.e., ${\mathit{v}}_{{|}_{\mathit{P}}}={\mathit{v}}_{\mathbf{u}}{|}_{\mathit{v}\mathrm{(}\mathit{p}\mathrm{)}}^{\mathit{p}\in \mathit{P}}$ .

Definition 18.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF and let v be an interpretation of D. Argument a is a strongly justified argument in interpretation v with respect to set E if one of the following conditions hold:

$\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and there exists a subset of parents of a excluding E, namely $\mathit{P}\subseteq \mathit{par}\mathrm{(}\mathit{a}\mathrm{)}\setminus \mathit{E}$ such that (a) a is acceptable with respect to ${\mathit{v}}_{{|}_{\mathit{P}}}$ and (b) all $\mathit{p}\in \mathit{P}$ are strongly justified in v w.r.t. set $\mathit{E}\cup \{\mathit{p}\}$ .

$\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ and there exists a subset of parents of a excluding E, namely $\mathit{P}\subseteq \mathit{par}\mathrm{(}\mathit{a}\mathrm{)}\setminus \mathit{E}$ such that (a) a is deniable with respect to ${\mathit{v}}_{{|}_{\mathit{P}}}$ and (b) all $\mathit{p}\in \mathit{P}$ are strongly justified in v w.r.t. set $\mathit{E}\cup \{\mathit{p}\}$ .

An argument a is strongly acceptable, respectively strongly deniable, in v if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ , resp. $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ , and a is strongly justified in v with respect to set $\{\mathit{a}\}$ . We say that an argument is strongly justified in v if it is either strongly acceptable or deniable in v.

Note that in Definition 18, the set of parents of a can be the empty set, i.e., $\mathit{P}=\varnothing$ . If the set P of parents of an argument is empty, then $\mathit{v}{|}_{\mathit{P}}={\mathit{v}}_{\mathbf{u}}$ . In this case, a is strongly acceptable/deniable in v if ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}$ is irrefutable/unsatisfiable, respectively. In other words, if $\mathit{P}=\varnothing$ , then a is strongly acceptable/deniable in v if a is acceptable/deniable in v and $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{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 $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}$ 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.

Example 7.

Consider the ADF presented in Example 3, i.e., $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{a}\wedge \neg \mathit{c}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{d}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\perp \}\mathrm{)}$ , depicted in Fig. 2. Let $\mathit{v}=\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ . We show that c and d are strongly justified in v and b is not strongly justified in v. Since $\mathit{v}\mathrm{(}\mathit{c}\mathrm{)}=\mathit{v}\mathrm{(}\mathit{d}\mathrm{)}=\mathbf{f}$ , we show that c and d are strongly deniable in v. First, since ${\mathit{\phi }}_{\mathit{d}}^{{\mathit{v}}_{\mathbf{u}}}\equiv \perp$ and $\mathit{v}\mathrm{(}\mathit{d}\mathrm{)}=\mathbf{f}$ , it holds that d is strongly deniable in v.

Furthermore, to show that c is strongly deniable in v, we show that c is strongly deniable in v with respect to $\mathit{E}=\{\mathit{c}\}$ . We choose a subset of parents of c excluding c, namely, $\mathit{P}=\{\mathit{d}\}$ . It is easy to check that ${\mathit{\phi }}_{\mathit{c}}^{{\mathit{v}}_{{|}_{\mathit{P}}}}$ is unsatisfiable, i.e., ${\mathit{\phi }}_{\mathit{c}}^{{\mathit{v}}_{{|}_{\mathit{P}}}}\equiv {\mathit{\phi }}_{\mathit{c}}^{{\mathit{v}}_{{|}_{\mathit{d}}}}\equiv \perp$ . Now we have to show that each $\mathit{p}\in \mathit{P}$ is strongly justified in v. The only parent of c in P is d. Since $\mathit{d}\in \mathit{P}$ , $\mathit{v}\mathrm{(}\mathit{d}\mathrm{)}=\mathbf{f}$ and d is also strongly deniable in v, it holds that c is strongly deniable in v.

To show that b is not strongly justified in v, since $\mathit{v}\mathrm{(}\mathit{b}\mathrm{)}=\mathbf{t}$ , we show that b is not strongly acceptable in v. Toward a contradiction, assume that b is strongly acceptable in v. Thus, we have to choose a set P of parents of b that satisfies ${\mathit{\phi }}_{\mathit{b}}^{{\mathit{v}}_{{|}_{\mathit{P}}}}\equiv \top$ . Let $\mathit{P}=\mathit{par}\mathrm{(}\mathit{b}\mathrm{)}$ . Since ${\mathit{\phi }}_{\mathit{b}}^{{\mathit{v}}_{{|}_{\mathit{P}}}}\not\equiv \top$ , there is no subset of $\mathit{par}\mathrm{(}\mathit{b}\mathrm{)}$ that satisfies the conditions of Definition 18 for b. Therefore, b is not strongly acceptable in v.

Note that in Example 7, if we choose a set of parents of c equal to $\{\mathit{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., ${\mathit{\phi }}_{\mathit{c}}^{{\mathit{v}}_{{|}_{\mathit{b}}}}\equiv \perp$ , 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.

Definition 19.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF and let v be an interpretation of D. An interpretation v is a strongly admissible interpretation if for each a such that $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , we have that a is a strongly justified argument in v.

The set of all strongly admissible interpretations of ADF D is denoted by $\mathit{\text{sadm}}\mathrm{(}\mathit{D}\mathrm{)}$ .

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

Example 8.

Consider ADF of Example 7, i.e., $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{a}\wedge \neg \mathit{c}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{d}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\perp \}\mathrm{)}$ , depicted in Fig. 2. Let $\mathit{v}=\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ . As was shown in Example 7, c and d are strongly deniable in v. However, b is not strongly justified in v. Thus, v is not a strongly admissible interpretation of D. However, ${\mathit{v}}_1=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}$ , ${\mathit{v}}_2=\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ , ${\mathit{v}}_3=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ are strongly admissible interpretations of D. We show that b is strongly acceptable in ${\mathit{v}}_3$ . To this end, let $\mathit{P}=\{\mathit{a}\mathrm{,}\mathit{c}\}$ be a set of parents of b. First, it holds that ${\mathit{\phi }}_{\mathit{b}}^{{\mathit{v}}_{3_{{|}_{\mathit{P}}}}}\equiv \top$ . Thus, the first condition is satisfied for b. We also have to check whether each parent of b in P is also strongly justified in ${\mathit{v}}_3$ . To this end, we show that a is strongly acceptable in ${\mathit{v}}_3$ and c is strongly deniable in ${\mathit{v}}_3$ . The latter is obvious by the method that was presented in Example 7 to show that c is strongly deniable in v. In addition, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}\equiv \top$ , thus, a is strongly acceptable in ${\mathit{v}}_3$ . Hence, b and a are strongly justified in ${\mathit{v}}_3$ . Thus, ${\mathit{v}}_3$ is a strongly admissible interpretation of D. Furthermore, ${\mathit{v}}_3$ is a unique grounded interpretation of D.

In Example 8, c is strongly deniable both in ${\mathit{v}}_2$ and ${\mathit{v}}_3$ , however, ${\mathit{v}}_2$ presents less information than ${\mathit{v}}_3$ . Interpretation ${\mathit{v}}_2$ 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 ${\mathit{v}}_2$ . Based on the acceptance condition of c, namely ${\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{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.

Definition 20.

Let D be an ADF, let a be an argument and let v be a strongly admissible interpretation of D. Interpretation v is called a least witness of strong justifiability of a if the following conditions hold.

$\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ ;

there is no strongly admissible interpretation ${\mathit{v}}^{\prime }$ where ${\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ and ${\mathit{v}}^{\prime }{⩽}_{\mathit{i}}\mathit{v}$ .

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:

Guess an interpretation v.

Check whether v is a strongly admissible interpretation. If the answer is yes, then go to item 3, else go to item 1.

Check whether $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . If the answer is yes, then go to item 4, else go to item 1.

Pick ${\mathit{v}}^{\prime }$ where ${\mathit{v}}^{\prime }{\mathrm{<}}_{\mathit{i}}\mathit{v}$ and check if ${\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ and v is a strongly admissible interpretation. If the answer is yes, then replace v with ${\mathit{v}}^{\prime }$ and repeat this item, else pick another ${\mathit{v}}^{\prime }$ and repeat this item.

If there is no ${\mathit{v}}^{\prime }$ that satisfies item 4, then v is a least witness of strong justifiability of a.

For instance, in Example 8, interpretation ${\mathit{v}}_2$ is a least witness of strong justifiability (or deniability) of c. This is because ${\mathit{v}}_2$ contains the truth values of c and d, and the truth value of d is the necessary and sufficient piece of information needed for denying c in the grounded interpretation.

Note that an argument may have more than one least witness of strong justification. For instance, let $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{a}\vee \mathit{b}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\top \}\mathrm{)}$ . Argument b is strongly acceptable in both ${\mathit{v}}_1=\{\mathit{a}\mathrm{,}\mathit{b}\}$ and ${\mathit{v}}_2=\{\mathit{b}\mathrm{,}\mathit{c}\}$ ; furthermore, by Definition 20, both ${\mathit{v}}_1$ and ${\mathit{v}}_2$ 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.

Definition 21.

Let D be an ADF, let v be a strongly admissible interpretation of D that is a least witness of strong justification of a, and let $\mathit{P}=\mathit{par}\mathrm{(}\mathit{a}\mathrm{)}\cap \mathrm{(}{\mathit{v}}^{\mathbf{t}}\cup {\mathit{v}}^{\mathbf{f}}\mathrm{)}$ . The maximum level of a with respect to a least v is a function that assigns a natural number to a, denoted by ${\mathcal{M}}_{\mathit{v}}$ , as follows:

if $\mathit{P}=\varnothing$ , then ${\mathcal{M}}_{\mathit{v}}\mathrm{(}\mathit{a}\mathrm{)}=1$ ;

if $\mathit{P}\ne \varnothing$ , then ${\mathcal{M}}_{\mathit{v}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{m}\mathit{a}\mathit{x}\{{\mathcal{M}}_{\mathit{v}}\mathrm{(}\mathit{p}\mathrm{)}|\mathit{p}\in \mathit{P}\}+1$

For instance, in Example 8, the maximum level of c with respect to the least witness ${\mathit{v}}_2$ is 2. This is because the maximum level of d in ${\mathit{v}}_2$ 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 $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\mathit{b}\vee \neg \mathit{b}\mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{b}\}\mathrm{)}$ be an ADF, depicted in Fig. 3. We show that $\mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\}$ is a strongly admissible interpretation of D. To this end, we show that a is strongly acceptable in v with respect to $\mathit{E}=\{\mathit{a}\}$ . Now let $\mathit{P}=\varnothing$ . It is clear that ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}$ 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 ${\mathit{D}}_{\mathit{F}}$ to the AF F presented in Example 2.

Example 10.

Consider AF $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathit{c}\mathrm{)}\}\mathrm{)}$ and the associated ADF ${\mathit{D}}_{\mathit{F}}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\neg \mathit{a}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{d}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\neg \mathit{c}\}\mathrm{)}$ . The set of all strongly admissible interpretations of ${\mathit{D}}_{\mathit{F}}$ is as follows: $\mathit{\text{sadm}}\mathrm{(}{\mathit{D}}_{\mathit{F}}\mathrm{)}=\{\{\}\mathrm{,}\{\mathit{a}\}\mathrm{,}\{\mathit{a}\mathrm{,}\neg \mathit{b}\}\}$ . For instance, interpretation $\mathit{v}=\{\mathit{a}\mathrm{,}\neg \mathit{b}\}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ . To substantiate our claim, we show that a is strongly acceptable in v and b is strongly deniable in v. The former one is clear, since ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}\equiv \top$ . For the latter one, let $\mathit{P}=\{\mathit{a}\}$ be a set of parents of b. First, it holds that ${\mathit{\phi }}_{\mathit{b}}^{{\mathit{v}}_{{|}_{\mathit{a}}}}\equiv \perp$ ; second, a is strongly acceptable in v. Thus, b is strongly deniable in v. Hence, v is a strongly admissible interpretation of D. Furthermore, v is a least witness of strong deniability of b and the maximum level of b in v is 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.

Lemma 6.

Let D be an ADF, let a be an argument, and let v be a strongly admissible interpretation of D that is a least witness of strong justification of a. It holds that a has a finite maximum level in v.

Proof.

Toward a contradiction, assume that a is an argument with infinite maximum level in v. Therefore, by Definition 21, the set of parents of a, namely P with ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{{|}_{\mathit{P}}}}$ , is a non-empty set. Further, there exists an argument p in $\mathit{P}\setminus \{\mathit{a}\}$ with infinite maximum level. By the same reason, p has a parent with infinite maximum level that is neither equal to a nor p, and so on. Thus, a has an infinite number of ancestors. This contradicts the assumption that D is a finite ADF. Thus, the assumption that a has an infinite maximum level is wrong. □

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

Corollary 7.

Let D be an ADF, let a be an argument, and let v be a strongly admissible interpretation of D that is a least witness of strong justification of a. Let the maximum level of a in v be m, and let $\mathit{P}=\mathit{par}\mathrm{(}\mathit{a}\mathrm{)}\cap \mathrm{(}{\mathit{v}}^{\mathbf{t}}\cup {\mathit{v}}^{\mathbf{f}}\mathrm{)}$ , then the maximum level of each parent of a, i.e., each $\mathit{p}\in \mathit{P}$ , in v is less than m.

Lemma 8 presents the monotonic characteristic of strongly justified arguments, i.e., if a is strongly justifiable in v and $\mathit{v}{⩽}_{\mathit{i}}{\mathit{v}}^{\prime }$ , then a is strongly justifiable in ${\mathit{v}}^{\prime }$ .

Lemma 8.

Let D be an ADF. If $\mathit{a}\in \mathit{A}$ is strongly justifiable in interpretation v of D and $\mathit{v}{⩽}_{\mathit{i}}{\mathit{v}}^{\prime }$ , then a is also strongly justifiable in ${\mathit{v}}^{\prime }$ .

Proof.

We show the lemma for the case that a is strongly acceptable in v; the proof method for the case that a is strongly deniable in v is similar. Assume that v is also a least witness of strong justification of a. We complete the proof by induction on the maximum level of argument a in v.

Base case: let a be an argument of the maximum level 1 that is strongly acceptable with respect to v. Therefore, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}\equiv \top$ . Thus, a is clearly strongly acceptable with respect to ${\mathit{v}}^{\prime }$ .

Induction hypothesis: Assume that the property holds for each argument of the maximum level j with $1⩽\mathit{j}\mathrm{<}\mathit{i}$ in v, i.e., if a is an argument with the maximum level j in v, then a is strongly justified in ${\mathit{v}}^{\prime }$ .

Inductive step: We show that this property also holds for arguments of level i. That is, if a is an argument with the maximum level i in v, then a is strongly acceptable in ${\mathit{v}}^{\prime }$ . Let a be an argument of the maximum level i. Since a is strongly acceptable in v, by Lemma 8, the maximum level i of a is a finite number. Since a is strongly acceptable in v, there exists a set of parents P of a excluding a where a is acceptable with respect to ${\mathit{v}}_{{|}_{\mathit{P}}}$ and all $\mathit{p}\in \mathit{P}$ are strongly justified in v. Since $\mathit{v}{⩽}_{\mathit{i}}{\mathit{v}}^{\prime }$ , it holds that $\mathit{P}\subseteq {{\mathit{v}}^{\prime }}^{\mathbf{t}}\cup {{\mathit{v}}^{\prime }}^{\mathbf{f}}$ . Thus, it holds that a is acceptable with respect to ${\mathit{v}}_{{|}_{\mathit{P}}}^{\prime }$ . We have to show that each $\mathit{p}\in \mathit{P}$ is strongly justified in ${\mathit{v}}^{\prime }$ . By Corollary 7, the maximum level of each $\mathit{p}\in \mathit{P}$ is at most $\mathit{i}-1$ in v. Thus, by induction hypothesis, p is strongly justified in ${\mathit{v}}^{\prime }$ . Therefore, the second condition of strong acceptability of a in ${\mathit{v}}^{\prime }$ also holds. Thus, a is strongly acceptable in ${\mathit{v}}^{\prime }$ . □

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.

Lemma 9.

Let D be an ADF, let ${\mathit{v}}_0={\mathit{v}}_{\mathbf{u}}$ and let ${\mathit{v}}_{\mathit{i}}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathit{i}-1}\mathrm{)}$ for $\mathit{i}\mathrm{>}0$ . For each $0⩽\mathit{i}$ it holds that:

${\mathit{v}}_{\mathit{i}}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{i}+1}$ ;

${\mathit{v}}_{\mathit{i}}$ is strongly admissible interpretation of D.

Proof.

The first item holds because the characteristic operator is a monotonic function.

We show by induction on i that each ${\mathit{v}}_{\mathit{i}}$ is a strongly admissible interpretation.

Base case: For $\mathit{i}=0$ , it is clear that ${\mathit{v}}_0={\mathit{v}}_{\mathbf{u}}$ is a strongly admissible interpretation.

Induction hypothesis: Assume that each ${\mathit{v}}_{\mathit{j}}$ for j with $0⩽\mathit{j}\mathrm{<}\mathit{i}$ is a strongly admissible interpretation.

Inductive step: We show that ${\mathit{v}}_{\mathit{i}}$ is a strongly admissible interpretation. Let a be an argument that is assigned to either t or f in ${\mathit{v}}_{\mathit{i}}$ . We show that a is strongly justifiable in ${\mathit{v}}_{\mathit{i}}$ . If $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{i}-1}$ , then there is nothing to prove, since by the induction hypothesis ${\mathit{v}}_{\mathit{i}-1}$ is a strongly admissible interpretation. Thus, a is strongly justified in ${\mathit{v}}_{\mathit{i}-1}$ , and since ${\mathit{v}}_{\mathit{i}-1}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{i}}$ , by Lemma 8, a is strongly justifiable in ${\mathit{v}}_{\mathit{i}}$ .

Assume that $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{\mathit{i}}$ and $\mathit{a}\mapsto \mathbf{u}\in {\mathit{v}}_{\mathit{i}-1}$ . We show that a is strongly acceptable in ${\mathit{v}}_{\mathit{i}}$ . For the case that $\mathit{a}\mapsto \mathbf{f}\in {\mathit{v}}_{\mathit{i}}$ , the proof follows a similar method. Since ${\mathit{v}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ , we can conclude that ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathit{i}-1}}$ is irrefutable. Let P be a subset of parents of a the truth value of which appears in ${\mathit{v}}_{\mathit{i}-1}$ and ${\mathit{\phi }}_{\mathit{a}}^{{{\mathit{v}}_{\mathit{i}-1}}_{|\mathit{P}}}\equiv \top$ . Otherwise, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathit{i}-1}}$ cannot be irrefutable. Assume that $\mathit{P}\ne \{\}$ , otherwise, there is nothing to prove. Let $\mathit{p}\in \mathit{P}$ . Since $\mathit{p}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{i}-1}$ for each $\mathit{p}\in \mathit{P}$ , p is strongly justifiable in ${\mathit{v}}_{\mathit{i}}$ by the induction hypothesis. Thus, by Lemma 8, p is strongly justifiable in ${\mathit{v}}_{\mathit{i}}$ . Thus, both conditions of Definition 18 hold for a in ${\mathit{v}}_{\mathit{i}}$ . Therefore, for an arbitrary argument a, if ${\mathit{v}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , then it holds that a is strongly justifiable in ${\mathit{v}}_{\mathit{i}}$ . Thus, ${\mathit{v}}_{\mathit{i}}$ is a strongly admissible interpretation. Hence, every interpretation in the sequence ${\mathit{v}}_{\mathbf{u}}\mathrm{,}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{,}\dots$ is a strongly admissible interpretation. □

Lemma 10.

Let D be an ADF.

D has at least one strongly admissible interpretation.

The least strong admissible interpretation of D, with respect to the ${⩽}_{\mathit{i}}$ ordering, is the trivial interpretation.

The maximal strongly admissible interpretation in the sequence of interpretations as in Lemma  9 , with respect to the ${⩽}_{\mathit{i}}$ ordering, is the unique grounded interpretation of D.

Proof.

The first and the second item of the lemma are clear by Lemma 9, which says that ${\mathit{v}}_{\mathbf{u}}$ is a strongly admissible interpretation.

By definition, the grounded interpretation of D is the least fixed-point of the characteristic operator. By Lemma 9, each element of the sequence ${\mathrm{\Gamma }}_{\mathit{D}}^{\mathit{n}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , for n with $\mathit{n}\mathrm{>}0$ , is a strongly admissible interpretation. Since the number of arguments is finite, this sequence has a limit; that is, there exists an m with $\mathit{m}\mathrm{>}0$ where ${\mathrm{\Gamma }}_{\mathit{D}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}}^{\mathit{m}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Therefore, the limit of this sequence, namely ${\mathrm{\Gamma }}_{\mathit{D}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , which is the grounded interpretation of D, is also a strongly admissible interpretation. Note that the nth power of ${\mathrm{\Gamma }}_{\mathit{D}}$ is defined inductively, that is, ${\mathrm{\Gamma }}_{\mathit{D}}^{\mathit{n}}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}}^{\mathit{n}-1}\mathrm{)}$ . □

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.

Theorem 11.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF and let v be a strongly admissible interpretation of D. Then the following hold:

v is an admissible interpretation of D.

v is a conflict-free interpretation of D.

Proof.

Let v be a strongly admissible interpretation of D. We show that v is an admissible interpretation. Toward a contradiction, assume that v is not an admissible interpretation, that is, $\mathit{v}{\nleqq }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathrm{(}}\mathit{D}\mathrm{)}\mathrm{(}\mathit{v}\mathrm{)}$ . Therefore, there exists an a such that $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ but ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}\ne \mathbf{t}\mathrm{/}\mathbf{f}$ . By the assumption, v is a strongly admissible interpretation. That is, if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , then a is strongly acceptable/deniable in v. Thus, there exists a subset of parents P of a such that a is acceptable with respect to ${\mathit{v}}_{{|}_{\mathit{P}}}$ if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ , and a is deniable with respect to ${\mathit{v}}_{{|}_{\mathit{P}}}$ if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ . However, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{{|}_{\mathit{P}}}}\equiv \top$ implies that ${\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}$ is irrefutable and ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{{|}_{\mathit{P}}}}\equiv \perp$ implies that ${\mathit{\phi }}_{\mathit{a}}^{\mathit{v}}$ is unsatisfiable. The former implies that if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ , then ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ ; the latter one implies that if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ , then ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ . This contradicts the assumption that there exists an a such that $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}\ne \mathbf{t}\mathrm{/}\mathbf{f}$ . Thus, the assumption that v is not an admissible interpretation is wrong. Hence, if v is a strongly admissible interpretation, then it is also an admissible interpretation.

If v is a strongly admissible interpretation, then by the first item of this theorem, it is an admissible interpretation. By the fact that in ADFs every admissible interpretation is a conflict-free interpretation, based on the definition of conflict-freeness (presented in Definition 13), we conclude that v is a conflict-free interpretation, as well. □

Example 11 indicates the distinction between the notion of strong admissibility semantics of ADFs and the notions of admissible and conflict-free semantics of ADFs. Example 11.

let $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\neg \mathit{b}\vee \mathit{a}\mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\neg \mathit{a}\}\mathrm{)}$ be a given ADF. The interpretation $\mathit{v}=\{\mathit{a}\mapsto \mathbf{f}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\}$ is an admissible interpretation of D. However, a is not strongly deniable, nor is b strongly acceptable in v. Thus, v is not a strongly admissible interpretation of D. Furthermore, ${\mathit{v}}^{\prime }=\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\}$ is a conflict-free interpretation of D that is neither an admissible nor a strongly admissible interpretation. The only strongly admissible interpretation of D, which is also the grounded interpretation of D, is the trivial interpretation.

3.1. The strongly admissible interpretations of an ADF form a lattice

Although the sequence of interpretations presented in Lemma 9 produces a sequence of strongly admissible interpretations of a given ADF D, this sequence does not contain all of the strongly admissible interpretations of D. For instance, in ADF $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{a}\wedge \neg \mathit{c}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{d}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\perp \}\mathrm{)}$ , presented in Example 7, it holds that $\mathit{v}=\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ is a strongly admissible interpretation of D. However, v is not equal to any of the elements of the sequence ${\mathit{v}}_{\mathbf{u}}\mathrm{,}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{,}\dots$ (for D), as in Lemma 9. In this section we show that the strongly admissible interpretations of an ADF form a lattice.

Theorem 12 indicates that any strongly admissible interpretation of an ADF D is bounded by an element of the sequence of strongly admissible interpretations presented in Lemma 9.

Theorem 12.

Let D be an ADF, let w be an interpretation of D, and let ${\mathit{v}}_{\mathit{i}}$ for $0⩽\mathit{i}$ be the sequence of interpretations presented in Lemma  9 . If w is a strongly admissible interpretation of D, then there exists the least $\mathit{m}⩾0$ such that $\mathit{w}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{m}}$ .

Proof.

Assume that w is a strongly admissible interpretation of D. Let $\mathit{S}=\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}$ be the set of arguments the truth values of which appear in w, i.e., $\mathit{S}={\mathit{w}}^{\mathbf{t}}\cup {\mathit{w}}^{\mathbf{f}}$ . For each i with $1⩽\mathit{i}⩽\mathit{n}$ , it holds that ${\mathit{a}}_{\mathit{i}}$ is strongly justified in w. Thus, for each ${\mathit{a}}_{\mathit{i}}$ there is a least witness of strong justification, namely ${\mathit{w}}_{\mathit{i}}$ where ${\mathit{w}}_{\mathit{i}}{⩽}_{\mathit{i}}\mathit{w}$ . Let ${\mathit{m}}_{\mathit{i}}$ be the maximum level of ${\mathit{a}}_{\mathit{i}}$ in ${\mathit{m}}_{\mathit{i}}$ and let m be the greatest of ${\mathit{m}}_{\mathit{i}}$ ’s, i.e., $\mathit{m}=max\{{\mathit{m}}_{\mathit{i}}|{\mathit{m}}_{\mathit{i}}\text{ is the maximum level of }{\mathit{a}}_{\mathit{i}}\text{ in }{\mathit{w}}_{\mathit{i}}\}$ . We claim that $\mathit{w}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{m}}$ . To prove our claim, we show that if ${\mathit{a}}_{\mathit{i}}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{w}$ , then ${\mathit{a}}_{\mathit{i}}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{m}}$ . We show our claim by induction on the maximum level of arguments.

Base case: Let a be a strongly justified argument in w with the maximum level of 1 in a ${\mathit{w}}_{\mathit{i}}$ . We show that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{m}}$ , i.e., a is a strongly justified argument in ${\mathit{v}}_{\mathit{m}}$ . Since the maximum level of a in a ${\mathit{w}}_{\mathit{i}}$ is 1, Definition 21 implies that $\mathit{P}=\varnothing$ . Thus, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}\equiv \top \mathrm{/}\perp$ , that is, ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_0\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . Hence, $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_1$ . Since the set of ${\mathit{v}}_{\mathit{i}}$ as in Lemma 9 forms a sequence of interpretations, it holds that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{m}}$ , for $\mathit{m}⩾1$ .

Induction hypothesis: Suppose that for all j with $1⩽\mathit{j}⩽\mathit{k}\mathrm{<}\mathit{m}$ and any a being a strongly justified argument in w with the maximum level of j in a ${\mathit{w}}_{\mathit{i}}$ , it holds that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{j}}$ (and also $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{m}}$ , for $\mathit{m}⩾\mathit{j}$ ).

Induction step: Let a be a strongly justified argument in w with the maximum level of $\mathit{k}+1$ in a ${\mathit{w}}_{\mathit{i}}$ . We show that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{k}+1}$ (and also $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{m}}$ , for $\mathit{m}⩾\mathit{k}+1$ ). By Lemma 6 the maximum level of a in a ${\mathit{w}}_{\mathit{i}}$ (i.e., $\mathit{k}+1$ ) is a finite number, thus, there exists a non-empty set $\mathit{P}\subseteq \mathit{par}\mathrm{(}\mathit{a}\mathrm{)}$ such that ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{w}}_{{|}_{\mathit{P}}}}\equiv \top \mathrm{/}\perp$ . Since p, with $\mathit{p}\in \mathit{P}$ , is a parent of a, by Definition 18, p is also a strongly justified argument in w. Thus, by Corollary 7 the maximum level of each p is strictly less than the maximum level of a i.e. the maximum level of p in a ${\mathit{w}}_{\mathit{i}}$ is at most k. Then, by the induction hypothesis, $\mathit{p}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{k}}$ , for each $\mathit{p}\in \mathit{P}$ . Therefore, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{w}}_{{|}_{\mathit{P}}}}\equiv {\mathit{\phi }}_{\mathit{a}}^{{{\mathit{v}}_{\mathit{k}}}_{{|}_{\mathit{P}}}}$ . Further, ${\mathit{\phi }}_{\mathit{a}}^{{{\mathit{v}}_{\mathit{k}}}_{{|}_{\mathit{P}}}}\equiv {\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathit{k}}}$ because ${{\mathit{v}}_{\mathit{k}}}_{{|}_{\mathit{P}}}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{k}}$ and ${\mathrm{\Gamma }}_{\mathit{D}}$ is a monotonic function. Therefore, $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{k}+1}$ (and also $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathit{v}}_{\mathit{m}}$ for $\mathit{m}⩾\mathit{k}+1$ ). That is, there exists an $\mathit{m}⩾0$ , such that $\mathit{w}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{m}}$ .

Further, we have to show that the natural number m assumed in the beginning of the proof is the least natural number that satisfies the condition of the theorem. Toward a contradiction assume that there exists an ${\mathit{m}}^{\prime }\mathrm{<}\mathit{m}$ such that $\mathit{w}{⩽}_{\mathit{i}}{\mathit{v}}_{{\mathit{m}}^{\prime }}$ . By our assumption the greatest maximum level of an argument of S, namely a is m in a ${\mathit{w}}_{\mathit{i}}$ . Thus, either ${\mathrm{\Gamma }}_{\mathit{D}}^{{\mathit{m}}^{\prime }}\mathrm{(}{\mathit{v}}_0\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ , or there exists $\mathit{p}\in \mathit{par}\mathrm{(}\mathit{a}\mathrm{)}\cap \mathit{S}$ such that ${\mathit{v}}_{{\mathit{m}}^{\prime }}\mathrm{(}\mathit{p}\mathrm{)}=\mathbf{u}$ . In both cases it holds that, $\mathit{w}{\nleqq }_{\mathit{i}}{\mathit{v}}_{{\mathit{m}}^{\prime }}$ . That is, m is the least natural number that satisfies the condition of the theorem, i.e, $\mathit{w}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{m}}$ and there is not ${\mathit{m}}^{\prime }\mathrm{<}\mathit{m}$ such that $\mathit{w}{⩽}_{\mathit{i}}{\mathit{v}}_{{\mathit{m}}^{\prime }}$ . □

To show that the set of strongly admissible interpretations of a given ADF form a lattice, first, in Theorem 15 we show that every two strongly admissible interpretations of D have a unique supremum. To this end, we first introduce the notion of join of two strongly admissible interpretations; see Definition 22.

Definition 22.

Let D be an ADF and let v and w be two strongly admissible interpretations of D. The join $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is defined as $$\begin{array}{c}\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}=\left\{\begin{array}{cc}\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}\hfill & \text{if }\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{v}\mathrm{,}\hfill \\ \mathit{w}\mathrm{(}\mathit{a}\mathrm{)}\hfill & \text{if }\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{w}\mathrm{,}\hfill \\ \mathbf{u}\hfill & \text{otherwise.}\hfill \end{array}\right.\end{array}$$

Proposition 13.

The join of two strongly admissible interpretations of D is a well-defined function.

Proof.

Let D be an ADF and let v and w be two strongly admissible interpretations of D. We show that the join operator is a well-defined function. That is, we have to show that there is no a that has two different values via $\mathrm{(}\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}$ . Toward a contradiction, assume that there is an a that has two different outputs via $\mathrm{(}\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}$ . That is, a is assigned to t in one of the interpretations and to f in another one. For instance, $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and $\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ . By Theorem 12, there exist the least natural numbers k and m such that $\mathit{v}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{k}}$ and $\mathit{w}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{m}}$ , respectively. Since $\mathit{v}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{k}}$ and $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ , $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{\mathit{k}}$ . Furthermore, since $\mathit{w}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{m}}$ and $\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ , $\mathit{a}\mapsto \mathbf{f}\in {\mathit{v}}_{\mathit{m}}$ . That is, ${\mathit{v}}_{\mathit{k}}{\nleqq }_{\mathit{i}}{\mathit{v}}_{\mathit{m}}$ and ${\mathit{v}}_{\mathit{m}}{\nleqq }_{\mathit{i}}{\mathit{v}}_{\mathit{k}}$ . This is a contradiction by Lemma 9, which says that either ${\mathit{v}}_{\mathit{k}}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{m}}$ or ${\mathit{v}}_{\mathit{m}}{⩽}_{\mathit{i}}{\mathit{v}}_{\mathit{k}}$ , because ${\mathit{v}}_{\mathit{k}}$ and ${\mathit{v}}_{\mathit{m}}$ are elements of the sequence of interpretations presented in Lemma 9. Thus, the assumption that there exists a that is acceptable in a strongly admissible interpretation of D but that is deniable in another strongly admissible of D is wrong. Thus, $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is a well-defined function. □

Lemma 14 presents that the join of two strongly admissible interpretations of a given ADF is also a strongly admissible interpretation of that ADF.

Lemma 14.

Let D be an ADF and let v and w be strongly admissible interpretations of D. Then $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is also a strongly admissible interpretation of D.

Proof.

Toward a contradiction, assume that $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is not a strongly admissible interpretation of D. Thus, there exists an a such that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ but it is not strongly justifiable in $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ . By Definition 22, either $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{v}$ or $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{w}$ . Since v and w are strongly admissible interpretations, a is strongly justifiable in v or w. Since $\mathit{v}{⩽}_{\mathit{i}}\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ and $\mathit{w}{⩽}_{\mathit{i}}\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ , by Lemma 8, a is strongly justifiable in $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ . This contradicts the assumption that a is not strongly justifiable in $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ . Thus, the assumption that $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is not a strongly admissible interpretation was wrong. That is, the join of two strongly admissible interpretations of D is a strongly admissible interpretation of D.  □

Theorem 15.

Let D be an ADF. Every two strongly admissible interpretations of D have a unique supremum.

Proof.

Let D be an ADF and let v and w be two strongly admissible interpretations of D. We show that $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is a supremum of v and w. By Definition 22, $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is an upper bound of v and w. By Lemma 14, $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is a strongly admissible interpretation of D. It remains to show that $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is a least upper bound of v and w. Toward a contradiction, assume that $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is not the least upper bound of v and w. That is, there exists a strongly admissible interpretation ${\mathit{w}}^{\prime }$ of D such that $\mathit{v}{⩽}_{\mathit{i}}{\mathit{w}}^{\prime }$ , $\mathit{w}{⩽}_{\mathit{i}}{\mathit{w}}^{\prime }$ and ${\mathit{w}}^{\prime }{\mathrm{<}}_{\mathit{i}}\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ . Thus there exists a with $\mathit{a}\mapsto \mathbf{u}\in {\mathit{w}}^{\prime }$ and $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ . However, $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ implies that either $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{v}$ or $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{w}$ . That is, either $\mathit{v}{\nleqq }_{\mathit{i}}{\mathit{w}}^{\prime }$ or $\mathit{w}{\nleqq }_{\mathit{i}}{\mathit{w}}^{\prime }$ . This contradicts the assumption that ${\mathit{w}}^{\prime }$ is the least upper bound of v and w. Thus, the assumption that $\mathit{v}{\bigsqcup }_{\mathit{i}}\mathit{w}$ is not the least upper bound of v and w was wrong. □

Subsequently, to show that the set of strongly admissible interpretations of ADF D form a lattice, in Theorem 17 we show that every two strongly admissible interpretations of D have an infimum. To this end, in Definition 23, we present the concept of the maximum strongly admissible interpretation contained in an interpretation of D.

Definition 23.

Let D be an ADF and let v be an interpretation of D. Interpretation w is called a unique maximum strongly admissible interpretation contained in v with respect to ${⩽}_{\mathit{i}}$ ordering if the following conditions hold:

w is a strongly admissible interpretation of D such that $\mathit{w}{⩽}_{\mathit{i}}\mathit{v}$ ;

If $\mathit{w}{\nsim }_{\mathit{i}}\mathit{v}$ , then there is no strongly admissible interpretation ${\mathit{w}}^{\prime }$ of D such that $\mathit{w}{\mathrm{<}}_{\mathit{i}}{\mathit{w}}^{\prime }{⩽}_{\mathit{i}}\mathit{v}$ .

Lemma 16.

Let D be an ADF and let v be an interpretation of D. Then there exists a unique maximum strongly admissible interpretation contained in v, with respect to the ${⩽}_{\mathit{i}}$ ordering.

Proof.

Each interpretation of D has at least as much information as the trivial interpretation. Thus, each v of D has at least as much information as ${\mathit{v}}_{\mathbf{u}}$ , which is a strongly admissible interpretation. Since the number of arguments of D is finite, there exists at least one maximal strongly admissible interpretation of D (with respect to the ${⩽}_{\mathit{i}}$ ordering), let us call it w, contained in a given interpretation v. We show that this w is unique. Toward a contradiction, assume that there are two maximal strongly admissible interpretations that satisfy the condition of the lemma, namely w and ${\mathit{w}}^{\prime }$ . By Lemma 14, $\mathit{w}{\bigsqcup }_{\mathit{i}}{\mathit{w}}^{\prime }$ is a strongly admissible interpretation of D. Since $\mathit{w}{⩽}_{\mathit{i}}\mathit{v}$ and ${\mathit{w}}^{\prime }{⩽}_{\mathit{i}}\mathit{v}$ , it also holds that $\mathit{w}{\bigsqcup }_{\mathit{i}}{\mathit{w}}^{\prime }{⩽}_{\mathit{i}}\mathit{v}$ . However, $\mathit{w}{⩽}_{\mathit{i}}\mathit{w}{\bigsqcup }_{\mathit{i}}{\mathit{w}}^{\prime }$ , ${\mathit{w}}^{\prime }{⩽}_{\mathit{i}}\mathit{w}{\bigsqcup }_{\mathit{i}}{\mathit{w}}^{\prime }$ and $\mathit{w}{\bigsqcup }_{\mathit{i}}{\mathit{w}}^{\prime }{⩽}_{\mathit{i}}\mathit{v}$ together with the assumption that w and ${\mathit{w}}^{\prime }$ are maximal strongly admissible interpretations contained in v lead to $\mathit{w}{\sim }_{\mathit{i}}\mathit{w}{\bigsqcup }_{\mathit{i}}{\mathit{w}}^{\prime }$ and ${\mathit{w}}^{\prime }{\sim }_{\mathit{i}}\mathit{w}{\bigsqcup }_{\mathit{i}}{\mathit{w}}^{\prime }$ . That is, $\mathit{w}{\sim }_{\mathit{i}}{\mathit{w}}^{\prime }$ . Thus, the maximum strongly admissible interpretation which is contained in v is unique. □

Theorem 17.

Let D be an ADF. Every two strongly admissible interpretations of D have a unique infimum.

Proof.

Let D be an ADF and let v and ${\mathit{v}}^{\prime }$ be two strongly admissible interpretations of D. Let $\mathit{w}=\mathit{v}{\sqcap }_{\mathit{i}}{\mathit{v}}^{\prime }$ . By Lemma 16, there exists a unique maximum strongly admissible interpretation ${\mathit{w}}^{\prime }$ with ${\mathit{w}}^{\prime }{⩽}_{\mathit{i}}\mathit{w}$ . That is, ${\mathit{w}}^{\prime }$ is a lower bound of v and ${\mathit{v}}^{\prime }$ . It remains to show that ${\mathit{w}}^{\prime }$ is the greatest lower bound of v and ${\mathit{v}}^{\prime }$ . Toward a contradiction, assume that there exists a ${\mathit{w}}^{″}$ that is the greatest lower bound of v and ${\mathit{v}}^{\prime }$ . That is, ${\mathit{w}}^{″}{⩽}_{\mathit{i}}\mathit{v}$ and ${\mathit{w}}^{″}{⩽}_{\mathit{i}}{\mathit{v}}^{\prime }$ . Then by the definition, ${\mathit{w}}^{″}{⩽}_{\mathit{i}}\mathrm{(}\mathit{v}{\sqcap }_{\mathit{i}}{\mathit{v}}^{\prime }=\mathit{w}\mathrm{)}$ . By the assumption, ${\mathit{w}}^{\prime }$ is the maximum strongly admissible interpretation that is less or equal to w, thus, ${\mathit{w}}^{″}{⩽}_{\mathit{i}}{\mathit{w}}^{\prime }$ . Thus, ${\mathit{w}}^{\prime }$ is an infimum of v and ${\mathit{v}}^{\prime }$ . □

Theorem 18.

Let D be an ADF. The strongly admissible interpretations of D form a lattice with respect to the ${⩽}_{\mathit{i}}$ -ordering, with the least element ${\mathit{v}}_{\mathbf{u}}$ and the top element $\mathit{\text{grd}}\mathrm{(}\mathit{D}\mathrm{)}$ .

Proof.

We have to show that each pair of strongly admissible interpretations of D has a supremum and an infimum. Theorem 15 shows the former one and Theorem 17 indicates the latter one. Thus, the strongly admissible interpretations of D form a lattice with respect to the ${⩽}_{\mathit{i}}$ -ordering. In Lemma 10, it is shown that ${\mathit{v}}_{\mathbf{u}}$ is the least strongly admissible interpretation and the grounded interpretation of D is the largest strongly admissible interpretation of the sequence of the interpretations presented in Lemma 9. This fact, together with Theorem 12, shows that the grounded interpretation D is the greatest element of this lattice. It is trivial that ${\mathit{v}}_{\mathbf{u}}$ is the least element of this lattice. □

Corollary 19.

The maximal strongly admissible interpretation of ADF D, with respect to the ${⩽}_{\mathit{i}}$ ordering, is the unique grounded interpretation of D.

The set of strongly admissible interpretations of ADF $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{a}\wedge \neg \mathit{c}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{d}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\perp \}\mathrm{)}$ given in Example 7 form a lattice, depicted in Fig. 4. The top element of this lattice is the grounded interpretation of D $\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\neg \mathit{c}\mathrm{,}\neg \mathit{d}\}$ .

Fig. 4.

Complete lattice of the strongly admissible interpretations of the ADF of Example 7.

4. Strong admissibility for ADFs generalizes strong admissibility for AFs

In this section we show that the concept of strong admissibility semantics for ADFs is a proper generalization of the concept of strong admissiblity semantics for AFs [25]. The technical proofs of Propositions 20 and 21 and Lemma 22 are available in the Appendix.

Given an AF $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ and its corresponding ADF ${\mathit{D}}_{\mathit{F}}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{,}\mathit{C}\mathrm{)}$ (see Definition 14), the set of all possible conflict-free extensions of F is denoted by $\mathcal{E}$ and the set of all possible conflict-free interpretations of ${\mathit{D}}_{\mathit{F}}$ is denoted by $\mathcal{V}$ . The functions ${\mathit{\text{Ext2Int}}}_{\mathit{F}}$ and ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}$ in Definitions 24–25, are modifications of the labelling functions as given in [6], which we recalled in Definitions 9–10. Function ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ represents the interpretation associated with a given extension S in F, and function ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}\mathit{v}\mathrm{)}$ indicates the extension associated with a given interpretation v of ${\mathit{D}}_{\mathit{F}}$ .

Definition 24.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ be an AF, and let S be an extension of F. The truth value assigned to each argument $\mathit{a}\in \mathit{A}$ by the three-valued interpretation ${\mathit{v}}_{\mathit{S}}$ associated with S is given by ${\mathit{\text{Ext2Int}}}_{\mathit{F}}:\mathcal{E}\to \mathcal{V}$ as follows. $$\begin{array}{c}{\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\left\{\begin{array}{cc}\mathbf{t}\hfill & \text{ if }\mathit{a}\in \mathit{S}\mathrm{,}\hfill \\ \mathbf{f}\hfill & \text{ if }\exists \mathit{b}\in \mathit{A}\text{ such that }\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}\text{ and }\mathit{b}\in \mathit{S}\mathrm{,}\hfill \\ \mathbf{u}\hfill & \text{otherwise.}\hfill \end{array}\right.\end{array}$$

Proposition 20.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ be an AF, let ${\mathit{D}}_{\mathit{F}}$ be its associated ADF, and let S be a conflict-free extension of F. Then ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ is well-defined.

Note that in Definition 24, the basic condition that S has to be a conflict-free extension is a necessary condition for ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ being well-defined. For instance, let $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}$ . Set $\mathit{S}=\{\mathit{a}\mathrm{,}\mathit{b}\}$ is an extension of F. However, S does not satisfy the conflict-free property. On the other hand, ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\}$ . In other words, the correspondence between extensions and interpretations via ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}.\mathrm{)}$ is well-defined for conflict-free sets of arguments. This is the reason why we restrict $\mathcal{E}$ and $\mathcal{V}$ to the set of all conflict-free extensions of F and the set of all conflict-free interpretations of ${\mathit{D}}_{\mathit{F}}$ , respectively. By Theorem 4 in [25], every strongly admissible extension of an AF is a conflict-free extension. Thus, if S is a strongly admissible extension of AF F, then, by Proposition 20, ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ is well-defined.

So extensions of F can be represented as interpretations of ${\mathit{D}}_{\mathit{F}}$ . Also an interpretation of ${\mathit{D}}_{\mathit{F}}$ can be represented as an extension via the following function.

Definition 25.

Let ${\mathit{D}}_{\mathit{F}}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{,}\mathit{C}\mathrm{)}$ be the ADF associated with AF F, and let v be an interpretation of ${\mathit{D}}_{\mathit{F}}$ , that is, $\mathit{v}\in \mathcal{V}$ . The associated extension ${\mathit{S}}_{\mathit{v}}$ of v is obtained via application of ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}:\mathcal{V}\to \mathcal{E}$ on v, as follows: $${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}\mathit{v}\mathrm{)}=\{\mathit{a}\in \mathit{A}|\mathit{a}\mapsto \mathbf{t}\in \mathit{v}\}$$

To present the correspondence between strongly admissible extensions of F and strongly admissible interpretations of the associated ${\mathit{D}}_{\mathit{F}}$ , we first present the correspondence between strongly admissible labellings of F and strongly admissible interpretations of the associated ${\mathit{D}}_{\mathit{F}}$ in Lemma 22. To this end, we define two functions, $\mathit{\text{Lab2Int}}$ and $\mathit{\text{Int2Lab}}$ to indicate the correspondence between labellings and interpretations in Definitions 26 and 27. Note that $\mathcal{L}$ denotes the set of labellings of AF F.

Definition 26.

The function $\mathit{L}\mathit{a}\mathit{b}2\mathit{I}\mathit{n}\mathit{t}\mathrm{(}·\mathrm{)}:\mathcal{L}\mapsto \mathcal{V}$ maps three-valued labellings to three-valued interpretations such that

$\mathit{L}\mathit{a}\mathit{b}2\mathit{I}\mathit{n}\mathit{t}\mathrm{(}\mathit{\lambda }\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ iff $\mathit{\lambda }\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{in}$ ,

$\mathit{L}\mathit{a}\mathit{b}2\mathit{I}\mathit{n}\mathit{t}\mathrm{(}\mathit{\lambda }\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ iff $\mathit{\lambda }\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{out}$ , and

$\mathit{L}\mathit{a}\mathit{b}2\mathit{I}\mathit{n}\mathit{t}\mathrm{(}\mathit{\lambda }\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ iff $\mathit{\lambda }\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{undec}$ .

Definition 27.

The function $\mathit{\text{Int2Lab}}\mathrm{(}·\mathrm{)}:\mathcal{V}\mapsto \mathcal{L}$ maps three-valued interpretations to three-valued labellings such that

$\mathit{\text{Int2Lab}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{in}$ iff $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ ;

$\mathit{\text{Int2Lab}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{out}$ iff $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ ;

$\mathit{\text{Int2Lab}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{undec}$ iff $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ .

In Proposition 21 we show that $\mathit{\text{Int2Lab}}$ is the inverse of $\mathit{\text{Lab2Int}}$ .

Proposition 21.

$\mathit{\text{Lab2Int}}\mathrm{(}\mathit{\text{Int2Lab}}\mathrm{(}.\mathrm{)}\mathrm{)}={\mathit{id}}_{\mathcal{V}}$ and $\mathit{\text{Int2Lab}}\mathrm{(}\mathit{\text{Lab2Int}}\mathrm{(}.\mathrm{)}\mathrm{)}={\mathit{id}}_{\mathcal{L}}$ .

Lemma 22.

For any argument framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ and its associated ADF ${\mathit{D}}_{\mathit{F}}$ , the following properties hold:

if λ is a strongly admissible labelling of F, then $\mathit{\text{Lab2Int}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ ;

if v is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ , then $\mathit{\text{Int2Lab}}\mathrm{(}\mathit{v}\mathrm{)}$ is a strongly admissible labelling of F.

Theorem 23 is a direct result of Propositions 5, 21, and Lemma 22. It presents the correspondence between strongly admissible extensions of F and strongly admissible interpretations of the associated ${\mathit{D}}_{\mathit{F}}$ .

Theorem 23.

For any argument framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ and its associated ADF ${\mathit{D}}_{\mathit{F}}$ , the following properties hold:

If S is a strongly admissible extension of F, then ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ ;

If v is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ , then ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}\mathit{v}\mathrm{)}$ is a strongly admissible extension of F.

Proof.

It is enough to show that ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}=\mathit{\text{Lab2Int}}\mathrm{(}\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{)}$ .

(1) Let a be an argument such that $\mathit{a}\in \mathit{S}$ . By Definition 24, $\mathit{a}\in \mathit{S}$ if and only if $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ . In other words, $\mathit{a}\in \mathit{S}$ if and only if $\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{in}$ if and only if $\mathit{\text{Lab2Int}}\mathrm{(}\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}=\mathbf{t}$ . (2) Let a be an argument such that $\mathit{a}\notin \mathit{S}$ and there exists a parent of a, namely ${\mathit{p}}_{\mathit{a}}$ , with ${\mathit{p}}_{\mathit{a}}\in \mathit{S}$ . By Definition 24, $\mathit{a}\notin \mathit{S}$ and ${\mathit{p}}_{\mathit{a}}\in \mathit{S}$ if and only if $\mathit{a}\mapsto \mathbf{f}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ . In other words, $\mathit{a}\notin \mathit{S}$ and ${\mathit{p}}_{\mathit{a}}\in \mathit{S}$ if and only if $\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{out}$ if and only if $\mathit{\text{Lab2Int}}\mathrm{(}\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}=\mathbf{f}$ .

Thus, ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}=\mathit{\text{Lab2Int}}\mathrm{(}\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{)}$ . Hence, by Proposition 5, if S is a strongly admissible extension of F, then $\mathit{\lambda }=\mathit{\text{Ext2Lab}}\mathrm{(}\mathit{S}\mathrm{)}$ is a strongly admissible labelling of F. Furthermore, by Lemma 22, if λ is a strongly admissible labelling of F, then $\mathit{\text{Lab2Int}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ . That is, ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ .

By the similar method as the one presented in the proof of the previous item, we have ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}\mathit{v}\mathrm{)}=\mathit{\text{Lab2Ext}}\mathrm{(}\mathit{\text{Int2Lab}}\mathrm{(}\mathit{v}\mathrm{)}\mathrm{)}$ . By Lemma 22, if v is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ , then $\mathit{\lambda }=\mathit{\text{Int2Lab}}\mathrm{(}\mathit{v}\mathrm{)}$ is a strongly admissible labelling of F. By Proposition 5, if λ is a strongly admissible labelling of F, then $\mathit{\text{Lab2Ext}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ is a strongly admissible extension of F. Hence, ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}\mathit{v}\mathrm{)}$ is a strongly admissible extension of F. □

We have already shown that the projection of a strongly admissible extension/labelling of AF F via ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}.\mathrm{)}\mathrm{/}\mathit{\text{Lab2Int}}\mathrm{(}.\mathrm{)}$ is a strongly admissible interpretation of the associated ${\mathit{D}}_{\mathit{F}}$ . The commutative diagrams in Fig. 5 show the relation between strong admissibility semantics of AF F and strong admissibility semantics of its associated ADF ${\mathit{D}}_{\mathit{F}}$ . In the following, the set of strongly admissible extensions of F, the set of strongly admissible labellings of F, and the set of strongly admissible interpretations of ${\mathit{D}}_{\mathit{F}}$ are denoted by $\mathit{\text{sadm}}\mathrm{(}\mathit{F}\mathrm{)}$ , ${\mathit{\text{sadm}}}_{\mathcal{L}}\mathrm{(}\mathit{F}\mathrm{)}$ , and $\mathit{\text{sadm}}\mathrm{(}{\mathit{D}}_{\mathit{F}}\mathrm{)}$ , respectively.

Fig. 5.

The left diagram shows that strong admissibility semantics of F project to strong admissibility semantics of ${\mathit{D}}_{\mathit{F}}$ , via ${\mathit{\text{Ext2Int}}}_{\mathit{F}}$ . The right diagram shows that strong admissibility semantics of ${\mathit{D}}_{\mathit{F}}$ project to strong admissibility semantics of F, via ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}$ .

The direct result of Theorem 23 is that the strong admissibility semantics of ADFs form a proper generalization of strong admissibility semantics of AFs, as presented in Corollary 24.

Corollary 24.

Let F be an AF and let ${\mathit{D}}_{\mathit{F}}$ be its associated ADF. An extension S is a strongly admissible semantics of F if and only if $\mathit{v}={\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ .

However, Corollary 24 does not claim that there is a one-to-one relation between the set of strong admissibility extensions of F and the set of strong admissibility interpretations of ${\mathit{D}}_{\mathit{F}}$ . In other words, for the strong admissibility semantics, neither ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}.\mathrm{)}$ nor ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}.\mathrm{)}$ is a bijective function. The reason is that for the strong admissibility semantics, the function ${\mathit{\text{Ext2Int}}}_{\mathit{F}}$ is not a surjective function and function ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}$ is not an injective function, as clarified in Example 12.3 ³

In [6,25], it is shown that $\mathit{\text{Ext2Lab}}$ is not a surjective function and function $\mathit{\text{Lab2Ext}}$ is not an injective function, for strong admissibility semantics of a given AF.

Example 12.

Let $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\}\mathrm{)}$ . The associated ADF of F is ${\mathit{D}}_{\mathit{F}}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\neg \mathit{a}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\neg \mathit{c}\}\mathrm{)}$ . The interpretation $\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ , but it is not a projection of any strongly admissible extension of F via ${\mathit{\text{Ext2Int}}}_{\mathit{F}}$ . Thus, ${\mathit{\text{Ext2Int}}}_{\mathit{F}}$ is not a surjective function. Furthermore, both of the strongly admissible interpretations of ${\mathit{D}}_{\mathit{F}}$ , namely, ${\mathit{v}}_1=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}$ and ${\mathit{v}}_2=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ , are mapped to the strongly admissible extension $\{\mathit{a}\mathrm{,}\mathit{c}\}$ via ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}$ . Thus, ${\mathit{D}}_{\mathit{F}}$ is not an injective function. In other words, we did not claim that ${\mathit{\text{Ext2Int}}}_{\mathit{F}}$ is an inverse of ${\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}$ for strongly admissible semantics. For instance, in this example ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{\text{Int2Ext}}}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_1\mathrm{)}\mathrm{)}={\mathit{v}}_2$ .

Although $\mathit{\text{Int2Ext}}\mathrm{(}.\mathrm{)}$ is not an injective function, by the second item of Theorem 23, function $\mathit{\text{Int2Ext}}\mathrm{(}.\mathrm{)}$ maps any strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ to a strongly admissible extension of F. That is, $\mathit{\text{Int2Ext}}\mathrm{(}.\mathrm{)}$ may map an element of $\mathit{\text{sadm}}\mathrm{(}{\mathit{D}}_{\mathit{F}}\mathrm{)}$ to an element of $\mathit{\text{sadm}}\mathrm{(}\mathit{F}\mathrm{)}$ . On the other hand, it is possible that there exists an element of $\mathit{\text{sadm}}\mathrm{(}{\mathit{D}}_{\mathit{F}}\mathrm{)}$ that is not an image of any element of $\mathit{\text{sadm}}\mathrm{(}\mathit{F}\mathrm{)}$ by $\mathit{\text{Ext2Int}}\mathrm{(}.\mathrm{)}$ , since $\mathit{\text{Ext2Int}}\mathrm{(}.\mathrm{)}$ is not a surjective function. However, the image of any element of $\mathit{\text{sadm}}\mathrm{(}\mathit{F}\mathrm{)}$ by $\mathit{\text{Ext2Int}}\mathrm{(}.\mathrm{)}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ , by the first item of Theorem 23. These results together lead to Corollary 25.

Corollary 25.

The concept of strong admissibility semantics of ADFs is a generalization of the concept of strong admissibility semantics of AFs.

5. Algorithm for strong admissibility semantics of ADFs

Definition 19 says that an interpretation v is strongly admissible in a given ADF D if and only if for each argument a that is presented in v, i.e., $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , we have that a is a strongly justified argument in v. In the following, we present an alternative method to answer the verification problem under strong admissibility semantics of ADFs. In this method of investigating whether the given interpretation v is a strongly admissible interpretation of D, there is no need to check whether each argument is strongly justified in v. The results of this section lead to algorithms to answer the following decision problems.

The verification problem: whether a given interpretation is a strongly admissible interpretation of a given ADF.

The strong justification problem: whether a given argument a is a strongly justified argument in a given interpretation.

To this end, we introduce ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}$ a variant of the characteristic operator restricted to a given interpretation v, presented in Definition 28.

Definition 28.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be a given ADF and let $\mathit{v}\mathrm{,}\mathit{w}$ be interpretations of D. Let ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}\mathrm{(}\mathit{w}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{w}\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}$ where ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{n}}\mathrm{(}\mathit{w}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{n}-1}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{)}$ for n with $\mathit{n}⩾1$ . Note that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^0\mathrm{(}\mathit{w}\mathrm{)}=\mathit{w}$ . We call the collection of the interpretations of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{n}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ for $\mathit{n}⩾1$ , the set of interpretations constructed based on v in D.

In Lemma 26, we show that each interpretation in the set of interpretations constructed based on v is a strongly admissible interpretation.

Lemma 26.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be a given ADF and let v be an interpretation of D. Let ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{n}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ be the sequence of interpretations constructed based on v, as in Definition  28 . For each i with $\mathit{i}⩾0$ it holds that;

${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ ;

${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is a strongly admissible interpretation of D;

if ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , then a is strongly justifiable in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

Proof.

We show the first item by induction on i.

Base case: By Definition 28, for $\mathit{i}=0$ it holds that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^0\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}={\mathit{v}}_{\mathbf{u}}$ and it is clear that ${\mathit{v}}_{\mathbf{u}}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^1\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

Induction hypothesis: Suppose that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ for each j with $0⩽\mathit{j}\mathrm{<}\mathit{i}$ .

Inductive step: We show that this property holds for $\mathit{j}=\mathit{i}$ , i.e., ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . From the fact that the characteristic operator is monotonic together with the induction hypothesis, it follows that ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{)}$ , for j with $0⩽\mathit{j}\mathrm{<}\mathit{i}$ . Thus, ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{)}$ and further, ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}$ . That is, ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

We show the second item by induction on i.

Base case: For $\mathit{i}=0$ it is clear that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^0\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}={\mathit{v}}_{\mathbf{u}}$ is a strongly admissible interpretation of D.

Induction hypothesis: Suppose that for each j with $0⩽\mathit{j}\mathrm{<}\mathit{i}$ it holds that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is a strongly admissible interpretation of D.

Inductive step: We prove that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is also a strongly admissible interpretation of D. To this end, we show that if the truth value of a is presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , then a is a strongly justified argument in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . We assume that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ , otherwise if the truth value of a is presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , then a is strongly acceptable in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ and there is nothing to prove (because by induction hypothesis ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is a strongly admissible interpretation of D). We show that a is strongly acceptable in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . For the case that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ the proof follows a similar method. Since ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ , we can conclude that ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{)}=\mathbf{t}$ , that is, the evaluation of ${\mathit{\phi }}_{\mathit{a}}$ under ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is irrefutable. Thus, there exists a non-empty subset of parents of a, namely P such that the truth value of each $\mathit{p}\in \mathit{P}$ is presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Since by induction hypothesis ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is strongly admissible if the truth value of an argument is presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , then that argument is strongly justified in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . That is, each $\mathit{p}\in \mathit{P}$ is also strongly justified in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . This satisfies the conditions of Definition 18. Thus, every interpretation in the sequence ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ for i with $\mathit{i}⩾0$ is a strongly admissible interpretation.

Toward a contradiction, assume that there exists an i and an argument a such that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ but a is not a strongly justified argument in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Thus, by Definition 19, ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is not a strongly admissible interpretation of D. This contradicts the second item of the current lemma, in which we showed that for each i with $\mathit{i}⩾0$ , it holds that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is a strongly admissible interpretation of D. Thus the assumption that there exists an argument a such that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ but a is not a strongly justified argument in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ was wrong. Thus, if ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , then a is a strongly justified argument in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . □

Remark.

the sequence of interpretations ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ as Definition 28, is named the sequence of strongly admissible interpretations constructed based on v in D.

Proposition 27 presents that for each interpretation v the sequence of interpretations constructed based on v is a finite sequence and therefore has a limit.

Proposition 27.

Let D be an ADF and let v be an interpretation of D. Let ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ) be the sequence of strongly admissible interpretations constructed based on v in D. Then there is an m with $\mathit{m}⩾0$ such that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

Proof.

Let ${\mathit{v}}_{\mathbf{u}}\mathrm{,}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^1\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{,}\dots$ be the sequence of strongly admissible interpretations constructed based on v in D. Since ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ for $\mathit{i}⩾0$ , by the first item of Lemma 26, and the number of arguments of D is finite, the sequence ${\mathit{v}}_{\mathbf{u}}\mathrm{,}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^1\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{,}\dots$ has to stop. That is, there exists $\mathit{m}⩾0$ such that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . □

Definition 29.

Let D be an ADF and let v be an interpretation of D. Let ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ) be the sequence of strongly admissible interpretations constructed based on v in D. Consider an m with $\mathit{m}⩾0$ such that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Then, $\mathit{w}={\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is called the limit of the sequence of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ) which is the least fixed-point of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}$ .

Theorem 28 proposes the necessary and sufficient condition for an interpretation being a strongly admissible interpretation.

Theorem 28.

Let D be an ADF and let v be an interpretation of D. Let ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ) be the sequence of strongly admissible interpretations constructed based on v in D. Interpretation v is a strongly admissible interpretation if and only if v is the limit of the sequence of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ), (i.e., there exists an m such that $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ ).

Proof.

‘→’ Assume that v is a strongly admissible interpretation of D. By Proposition 27, there exists an m ( $\mathit{m}⩾0$ ) such that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . We show that $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

By the definition of the constructed sequence of interpretations based on v in Definition 28 it is clear that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{⩽}_{\mathit{i}}\mathit{v}$ for $\mathit{i}⩾0$ . Therefore, ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{⩽}_{\mathit{i}}\mathit{v}$ .

It remains to show that $\mathit{v}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Toward a contradiction assume that $\mathit{v}{\nleqq }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . This means that there exists a such that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in \mathit{v}$ , but $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\notin {\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Since v is a strongly admissible interpretation, a is a strongly justified argument in v. Thus, by Definition 18, there exists a non-empty subset of parents of a, namely P such that the truth value of each $\mathit{p}\in \mathit{P}$ is presented in v, such that P satisfies the condition of Definition 18 for a. This means that each $\mathit{p}\in \mathit{P}$ is also a strongly justified argument in v. Note that if $\mathit{P}=\varnothing$ the fact that a is strongly justified in v implies that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^1\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , i.e., $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Thus, P has to be a non-empty set to satisfy the assumption that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\notin {\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

If the truth value of arguments of P are presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , then there exists a j with $0⩽\mathit{j}⩽\mathit{m}$ such that the truth value of arguments of P are also presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . If so, it holds that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}+1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . This contradicts the assumption that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\notin {\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

Hence, there exists $\mathit{p}\in \mathit{P}$ such that the truth value of p is not presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . The fact that p is a strongly justified argument in v implies that there exists a non-empty subset of parents of p, namely ${\mathit{P}}_1$ such that the truth value of elements of ${\mathit{P}}_1$ are presented in v, such that ${\mathit{P}}_1$ satisfies the condition of Definition 18 for p. Using the same method of reasoning for p, we conclude that there exists a parent of p, namely ${\mathit{p}}_1$ such that the truth value of ${\mathit{p}}_1$ is not presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

Following the same method of reasoning, we find that there exists a sequence of ancestors of a, namely $\mathit{p}\mathrm{,}{\mathit{p}}_1\mathrm{,}\dots$ such that the truth value of none of them is presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Since the number of arguments of A is finite, the sequence $\mathit{p}\mathrm{,}{\mathit{p}}_1\mathrm{,}\dots$ cannot be an infinite sequence. If the sequence $\mathit{p}\mathrm{,}{\mathit{p}}_1\mathrm{,}\dots$ is finite, then for some i, ${\mathit{P}}_{\mathit{i}}=\varnothing$ . If ${\mathit{P}}_{\mathit{i}}=\varnothing$ , then by Definition 18, ${\mathit{\phi }}_{{\mathit{p}}_{\mathit{i}-1}}^{{\mathit{v}}_{\mathbf{u}}}$ is irrefutable/unsatisfiable. This means that ${\mathit{p}}_{\mathit{i}-1}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^1\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . This contradicts the assumption that the truth values of arguments of sequence $\mathit{p}\mathrm{,}{\mathit{p}}_1\mathrm{,}\dots$ are not presented in ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Thus, the assumption that $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\notin {\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is wrong. Hence, $\mathit{v}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ .

‘←’ Assume that $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . We show that v is a strongly admissible interpretation. Lemma 26 says that each ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , for $\mathit{i}⩾0$ , is a strongly admissible interpretation of D. Thus, ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ is a strongly admissible interpretation of D. As $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ it follows that v is a strongly admissible interpretation of D. □

Based on the above observations, one can characterise a strongly admissible interpretation v as the least fixed point of the corresponding operator ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}$ . That is, we can verify an interpretation by computing this sequence of strongly admissible interpretations. By Theorem 28, to investigate whether interpretation v is a strongly admissible there is no need of indicating whether each argument which is presented in v is a strongly justified argument in v. That is, there is no need of following Definition 18 to answer the verification problem for strong admissibility semantics of ADFs. That is, by Theorem 28, it is enough to investigate whether $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , where ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ ( $\mathit{i}⩾0$ ) is a sequence of strongly admissible interpretations constructed based on v in D. Example 13 illustrates the role of Theorem 28 and the sequence of strongly admissible interpretations constructed based on a given interpretation.

Example 13.

Consider the ADF given in Example 7, i.e., $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{{\mathit{\phi }}_{\mathit{a}}:\top \mathrm{,}{\mathit{\phi }}_{\mathit{b}}:\mathit{a}\wedge \neg \mathit{c}\mathrm{,}{\mathit{\phi }}_{\mathit{c}}:\neg \mathit{b}\wedge \mathit{d}\mathrm{,}{\mathit{\phi }}_{\mathit{d}}:\perp \}\mathrm{)}$ . To investigate whether interpretation $\mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ is a strongly admissible interpretation, we follow the method presented in Theorem 28 by constructing the sequence of strongly admissible interpretations constructed based on v, as in Definition 28. That is, we investigate whether there exists an m such that $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . The sequence of strongly admissible interpretations constructed based on v is as follows. $$\begin{array}{l}{\mathit{v}}_1={\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}=\{\mathit{a}\mathrm{,}\neg \mathit{d}\}{\sqcap }_{\mathit{i}}\{\mathit{a}\mathrm{,}\neg \mathit{c}\mathrm{,}\neg \mathit{d}\}=\{\mathit{a}\mathrm{,}\neg \mathit{d}\}\mathrm{,}\\ {\mathit{v}}_2={\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^2\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}\mathrm{(}{\mathit{v}}_1\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_1\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}=\{\mathit{a}\mathrm{,}\neg \mathit{c}\mathrm{,}\neg \mathit{d}\}{\sqcap }_{\mathit{i}}\{\mathit{a}\mathrm{,}\neg \mathit{c}\mathrm{,}\neg \mathit{d}\}=\{\mathit{a}\mathrm{,}\neg \mathit{c}\mathrm{,}\neg \mathit{d}\}\end{array}$$ Since v is the limit of the sequence ${\mathit{v}}_1\mathrm{,}{\mathit{v}}_2$ , i.e., $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^2\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , (i.e., v is a least fixed point of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}$ ), interpretation v is a strongly admissible interpretation of D.

On the other hand, we investigate that ${\mathit{v}}^{\prime }=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}$ is not a strongly admissible interpretation of D. The sequence of interpretation constructed based on ${\mathit{v}}^{\prime }$ are as follow. $$\begin{array}{l}{\mathit{v}}_1={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}{\sqcap }_{\mathit{i}}{\mathit{v}}^{\prime }=\{\mathit{a}\mathrm{,}\neg \mathit{d}\}{\sqcap }_{\mathit{i}}\{\mathit{a}\mathrm{,}\mathit{b}\}=\{\mathit{a}\}\mathrm{,}\\ {\mathit{v}}_2={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_1\mathrm{)}{\sqcap }_{\mathit{i}}{\mathit{v}}^{\prime }=\{\mathit{a}\mathrm{,}\neg \mathit{d}\}{\sqcap }_{\mathit{i}}\{\mathit{a}\mathrm{,}\mathit{b}\}=\{\mathit{a}\}.\end{array}$$ Thus, the sequence of interpretations constructed based on ${\mathit{v}}^{\prime }$ leads to ${\mathit{v}}_2=\{\mathit{a}\}$ , which is not equal to ${\mathit{v}}^{\prime }$ , i.e., ${\mathit{v}}^{\prime }{\nsim }_{\mathit{i}}{\mathit{v}}_2$ (that is, ${\mathit{v}}^{\prime }$ is not a least fixed point of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}{\mathit{v}}^{\prime }}$ ). Hence, ${\mathit{v}}^{\prime }$ is not a strongly admissible interpretation of D. The reason is that the truth value of b is presented in ${\mathit{v}}^{\prime }$ , however, with a similar reason as was presented in Example 7, it is easy to show that b is not strongly acceptable in ${\mathit{v}}^{\prime }$ .

Lemma 26 and Theorem 28 lead us to present an algorithm to answer the decision problem of whether interpretation v is a strongly admissible interpretation, presented in Algorithm 1.

Algorithm 1

Algorithm to decide whether v is a strongly admissible interpretation of D

The results of this section lead to an alternative definition for strongly admissible semantics of ADFs, presented in Definition 30.

Definition 30.

Let D be an ADF and let v be an interpretation of D. Let ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ) be the sequence of strongly admissible interpretations constructed based on v in D. Interpretation v is a strongly admissible interpretation if v is the limit of the sequence of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ), (i.e., if there exists an m such that $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ ).

In the current section we presented an alternative definition (i.e., Definition 30) of strongly admissible interpretations of a given ADF in which there is no need to investigate that all the arguments the truth values of which are presented in a given interpretation are strongly justifiable. If a given interpretation v is a strongly admissible interpretation of D, then it is clear that a is strongly acceptable in v if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and it is strongly deniable in v if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ . In contrast, when v is not strongly admissible, it may contain some arguments that are strongly justifiable in v. For instance, in Example 13, a is strongly acceptable in ${\mathit{v}}^{\prime }$ , however, ${\mathit{v}}^{\prime }$ is not a strongly admissible interpretation of D, because b is not strongly acceptable in ${\mathit{v}}^{\prime }$ . Algorithm 2 presents a method to answer whether an argument is strongly justifiable in a given interpretation. Note that in this method, presented in Definition 31, in contrast with Definition 18 there is no need to find a set of ancestors of a given argument to answer the decision problem. Theorem 29 shows why the method presented in Algorithm 2 and Definition 31 works to answer the decision problem whether an argument is strongly justifiable in a given interpretation.

Theorem 29.

Let D be an ADF and let v be an interpretation of D. Let ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ) be the sequence of strongly admissible interpretations constructed based on v in D. Assume that ${\mathit{v}}^{\prime }$ is the limit of the sequence of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ). It holds that ${\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ if and only if a is a strongly justified argument in v.

Proof.

First, we assume that ${\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ ; and we show that a is a strongly justified argument in v. Since ${\mathit{v}}^{\prime }$ is the limit of the sequence ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ), there exists an m with $\mathit{m}⩾0$ where ${\mathit{v}}^{\prime }={\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . By the third item of Lemma 26, if ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , then a is a strongly justified argument of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{m}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , i.e., a is a strongly justified argument of ${\mathit{v}}^{\prime }$ . Thus, if ${\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , since ${\mathit{v}}^{\prime }{⩽}_{\mathit{i}}\mathit{v}$ , by Lemma 8 it holds that a is a strongly justified argument of v.

Second, we assume that a is a strongly justified argument in v; we show that ${\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . Since a is a strongly justified argument in v, there exists a least witness of strong justifiability of a, namely ${\mathit{w}}_{\mathit{a}}$ . We claim that if the maximum level of a in ${\mathit{w}}_{\mathit{a}}$ is i (i.e., ${\mathcal{M}}_{{\mathit{w}}_{\mathit{a}}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{i}$ ), then ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . We show this claim by induction on the maximum level of a.

Base case: If a is a strongly justified argument in v and ${\mathcal{M}}_{{\mathit{w}}_{\mathit{a}}}\mathrm{(}\mathit{a}\mathrm{)}=1$ in a ${\mathit{w}}_{\mathit{a}}$ , then we show that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^1\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . If ${\mathcal{M}}_{{\mathit{w}}_{\mathit{a}}}\mathrm{(}\mathit{a}\mathrm{)}=1$ , then ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{\mathbf{u}}}\equiv \top \mathrm{/}\perp$ , i.e., $\mathit{a}\mapsto \mathbf{t}\mathrm{/}\mathbf{f}\in {\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . Since $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , it holds that ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^1\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ .

Induction hypothesis: For all j with for $0⩽\mathit{j}\mathrm{<}\mathit{i}$ , if a is a strongly justified argument in v and the maximum level of a in a ${\mathit{w}}_{\mathit{a}}$ is j, then ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ .

Inductive step: If a is a strongly justified argument in v and the maximum level of a in a ${\mathit{w}}_{\mathit{a}}$ is i, then ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . Let P be a set of parents of a that satisfies the conditions of Definition 18 for a, that is, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{{|}_{\mathit{P}}}}\equiv \top \mathrm{/}\perp$ , where each $\mathit{p}\in \mathit{P}$ is a strongly justified in v. By Corollary 7, the level of each parent of a in the ${\mathit{w}}_{\mathit{a}}$ is at most $\mathit{i}-1$ . For each $\mathit{p}\in \mathit{P}$ , since $\mathit{v}\mathrm{(}\mathit{p}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ and the maximum level of p in ${\mathit{w}}_{\mathit{a}}$ is at most $\mathit{i}-1$ , by the induction hypothesis, we have ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}-1}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{p}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . Hence, ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ .

Algorithm 2

Algorithm to decide whether a is a strongly justified argument in v

Thus, if a is a strongly justified argument in v and the maximum level of a in a ${\mathit{w}}_{\mathit{a}}$ is i, then ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ . Since ${\mathit{v}}^{\prime }$ is the limit of the sequence of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , it holds that ${\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ .  □

Theorem 29 leads to present an alternative definition of strong acceptability/deniability of arguments, presented in Definition 31, in which to answer whether a given argument is a strongly justified argument in a given interpretation there is no need to find a proper set P of parents of the argument in question to satisfy the conditions of Definition 18.

Definition 31.

Let D be an ADF and let v be an interpretation of D. Let ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ) be the sequence of strongly admissible interpretations constructed based on v in D. Assume that ${\mathit{v}}^{\prime }$ is the limit of the sequence of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ). Argument a, with $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\mathrm{/}\mathbf{f}$ , is a strongly justified argument in v if $\mathit{v}\mathrm{(}\mathit{a}\mathrm{)}={\mathit{v}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}$ .

6. Sequence of strongly admissible extensions for AFs and ADFs

In Section 4 we showed that the concept of strongly admissible semantics of ADFs forms a generalization of the concept of strongly admissible semantics of AFs. Furthermore, we indicated that there is no one-to-one relation between the set of strongly admissible extensions of AF F and the set of strongly admissible interpretations of the associated ADF ${\mathit{D}}_{\mathit{F}}$ . In this section we clarify the relation between the sequence of strongly admissible extensions of a given AF F and the sequence of strongly admissible interpretations of the associated ADF ${\mathit{D}}_{\mathit{F}}$ .

In Lemma 26, we constructed a sequence of strongly admissible interpretations ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ) based on a given interpretation v in an ADF. In Theorem 28, we proved that v is a strongly admissible interpretation of a given ADF if and only if v is the limite of the sequence ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ (for $\mathit{i}⩾0$ ). There is a similar method to indicate whether a given extension is a strongly admissible extension of a given AF, presented in [25]. In the following, we first represent the necessary notations from [25]. Then we investigate the relation between the sequence of extensions presented in [25] for an AF and the sequence of interpretations for the associated ADF presented in the current work.

In [25, Lemma 2], it is presented that, in a given AF F, for an arbitrary extension S of ${\mathrm{\Gamma }}_{\mathit{F}}$ , each extension in the sequence ${\mathit{H}}^0=\varnothing$ , ${\mathit{H}}^{\mathit{i}+1}={\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}\cap \mathit{S}$ is a strongly admissible extension of F. We recall this lemma in Lemma 30. Note that in the following, ${\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}.\mathrm{)}$ is the characteristic function of AFs, as it is defined in Section 2.1.

Lemma 30 ([25, Lemma 2]).

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ and let $\mathit{S}\subseteq \mathit{A}$ . Let ${\mathit{H}}^0=\varnothing$ and ${\mathit{H}}^{\mathit{i}+1}={\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}\cap \mathit{S}$ ( $\mathit{i}⩾0$ ). For each $\mathit{i}\mathrm{>}0$ it holds that

${\mathit{H}}^{\mathit{i}}\subseteq {\mathit{H}}^{\mathit{i}+1}$ ;

${\mathit{H}}^{\mathit{i}}$ is strongly admissible;

${\mathit{H}}^{\mathit{i}}$ strongly defends each of its arguments.

Let S be a strongly admissible extension of F and let $\mathit{v}={\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ . The main goal of the rest of this section is to show the exact relation between the sequence of strongly admissible extensions of F, namely ${\mathit{H}}^{\mathit{i}}$ as in Lemma 30, and the sequence of the strongly admissible interpretations of ${\mathit{D}}_{\mathit{F}}$ , namely ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , as in Definition 28. In Theorem 1 of [25], it was shown that S is a strongly admissible extension of F if and only if $\mathit{S}={\bigcup }_{\mathit{i}=0}^{\infty }{\mathit{H}}^{\mathit{i}}$ ; we rephrase it in Theorem 31.

Theorem 31 ([25, Theorem 1]).

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ , let $\mathit{S}\subseteq \mathit{A}$ and let ${\mathit{H}}^{\mathit{i}}$ $\mathrm{(}\mathit{i}⩾0\mathrm{)}$ be as in Lemma  30 . S is strongly admissible iff $\mathit{S}={\bigcup }_{\mathit{i}=0}^{\infty }{\mathit{H}}^{\mathit{i}}$ .

Since the number of arguments of F is finite and ${\mathit{H}}^{\mathit{i}}\subseteq {\mathit{H}}^{\mathit{i}+1}$ , we conclude that there exists $\mathit{j}⩾0$ such that $\mathit{S}={\mathit{H}}^{\mathit{j}}$ iff S is a strongly admissible extension of F. It is easy to check that ${\mathit{\text{Ext2Int}}}_{\mathit{F}}$ is a monotonic function over ${\mathit{H}}^{\mathit{i}}$ , that is, if ${\mathit{H}}^{\mathit{i}}\subseteq {\mathit{H}}^{\mathit{j}}$ , then ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}{⩽}_{\mathit{i}}{\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{j}}\mathrm{)}$ . Before presenting the formal relation between the sequence of strongly admissible extensions of F (in the sense of Theorem 31) and the sequence of strongly admissible interpretations of ${\mathit{D}}_{\mathit{F}}$ (in the sense of Theorem 28), we clarify this relation by an example, in Example 14.

Example 14.

Consider $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\}\mathrm{)}$ and extension $\mathit{S}=\{\mathit{a}\mathrm{,}\mathit{c}\}$ . We show that S is a strongly admissible extension of F via Theorem 31. That is, we construct the sequence of extensions ${\mathit{H}}^{\mathit{i}}$ and we show that $\mathit{S}={\bigcup }_{\mathit{i}=0}^{\infty }{\mathit{H}}^{\mathit{i}}$ . Furthermore, in the right-hand column we show the associated interpretation to each extension via Definition 24. $$\begin{array}{llll}\hfill & {\mathit{H}}^0=\{\}& \hfill & \mathit{\text{Ext2Int}}\mathrm{\left(}{\mathit{H}}^0\mathrm{\right)}=\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\\ \hfill & {\mathit{H}}^1={\mathrm{\Gamma }}_{\mathit{F}}\mathrm{\left(}{\mathit{H}}^0\mathrm{\right)}\cap \mathit{S}=\{\mathit{a}\}\cap \{\mathit{a}\mathrm{,}\mathit{c}\}=\{\mathit{a}\}& \hfill & \mathit{\text{Ext2Int}}\mathrm{\left(}{\mathit{H}}^1\mathrm{\right)}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\\ \hfill & {\mathit{H}}^2={\mathrm{\Gamma }}_{\mathit{F}}\mathrm{\left(}{\mathit{H}}^1\mathrm{\right)}\cap \mathit{S}=\{\mathit{a}\mathrm{,}\mathit{c}\}\cap \{\mathit{a}\mathrm{,}\mathit{c}\}=\{\mathit{a}\mathrm{,}\mathit{c}\}& \hfill & \mathit{\text{Ext2Int}}\mathrm{\left(}{\mathit{H}}^2\mathrm{\right)}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}\end{array}$$ Since $\mathit{S}={\mathit{H}}^2$ , i.e., S is a unique fixed point of ${\bigcup }_{\mathit{i}=0}^{\infty }{\mathit{H}}^{\mathit{i}}$ , it is a strongly admissible extension of F. The interpretation associated with S in ${\mathit{D}}_{\mathit{F}}$ via Definition 24 is $\mathit{\text{Ext2Int}}\mathrm{(}\mathit{S}\mathrm{)}=\mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}$ . By Theorem 23, we already know that v is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ . In other words, we illustrate that v is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ via Definition 30. To this end, we construct the sequence of strongly admissible interpretations ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ based on v. It is expected that there is a one-to-one relation between $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ and the elements of the sequence of ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ in Definition 30. $$\begin{array}{ll}\hfill & {\mathit{v}}_0={\mathit{v}}_{\mathbf{u}}\\ \hfill & {\mathit{v}}_1={\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_0\mathrm{)}\sqcap \mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\sqcap \mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\\ \hfill & {\mathit{v}}_2={\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_1\mathrm{)}\sqcap \mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\sqcap \mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\\ \hfill & {\mathit{v}}_3={\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_2\mathrm{)}\sqcap \mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\sqcap \mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\\ \hfill & {\mathit{v}}_4={\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_3\mathrm{)}\sqcap \mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}\sqcap \mathit{v}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{t}\mathrm{,}\mathit{d}\mapsto \mathbf{f}\}\end{array}$$ In fact, by Theorem 28, it holds that v is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ , since $\mathit{v}{\sim }_{\mathit{i}}{\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}\mathrm{,}\mathit{v}}^4\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ . However, the guess that each ${\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , for $\mathit{i}⩾0$ , is equal to $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ was wrong. Since as we can see, on the one hand, $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^1\mathrm{)}$ contains the truth value of initial arguments that are in S and the arguments that are attacked by ${\mathit{H}}^1$ , i.e., the children of arguments of ${\mathit{H}}^1$ . On the other hand, ${\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}\mathrm{,}\mathit{v}}^1\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ contains the truth values of initial arguments that are presented in v and do not contain the truth values of children of initial arguments presented in v. In other words, ${\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_1\mathrm{)}$ produces the truth values of children of initial arguments presented in ${\mathit{v}}_1$ . That is, ${\mathit{v}}_2={\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_1\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}$ contains the truth values of initial arguments and their children that are presented in v. Thus, it seems that, for $\mathit{i}⩾0$ , it holds that each $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ is equal to ${\mathit{v}}_{2\mathit{i}}$ . For instance, in the current example $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^1\mathrm{)}={\mathit{v}}_2$ and $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^2\mathrm{)}={\mathit{v}}_4$ . Further, in this example the projection of each strongly admissible extension of F via $\mathit{\text{Ext2Int}}\mathrm{(}.\mathrm{)}$ is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ . However, for instance, ${\mathit{v}}_1$ is not a projection of any strongly admissible extension. This shows that $\mathit{\text{Ext2Int}}\mathrm{(}.\mathrm{)}$ is not a surjective function, as presented earlier in Example 12.

Theorem 32.

Let F be an AF and let ${\mathit{D}}_{\mathit{F}}$ be its associated ADF. Let S be a strongly admissible extension of F and let ${\mathit{H}}^{\mathit{i}}$ be as in Lemma  30 . Let $\mathit{\text{Ext2Int}}\mathrm{(}\mathit{S}\mathrm{)}=\mathit{v}$ and let ${\mathit{v}}_{\mathit{i}}={\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ be the sequence of interpretations as in Definition  28 . Then it holds that $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}={\mathit{v}}_{2\mathit{i}}$ , for each $\mathit{i}⩾0$ .

Proof.

For $\mathit{i}⩾0$ , we show that $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}={\mathit{v}}_{2\mathit{i}}$ by induction on i.

Base case: It is obvious that $\mathit{\text{Ext2Int}}\mathrm{(}{\mathit{H}}^0\mathrm{)}={\mathit{v}}_{\mathbf{u}}={\mathit{v}}_0$ .

Induction hypothesis: assume that ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{j}}\mathrm{)}={\mathit{v}}_{2\mathit{j}}$ for each j with $0⩽\mathit{j}\mathrm{<}\mathit{i}$ .

Inductive step: we have to show that ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}={\mathit{v}}_{2\mathit{i}}$ . To show the inductive step, we show that $\mathit{a}\mapsto \mathit{x}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ if and only if $\mathit{a}\mapsto \mathit{x}\in {\mathit{v}}_{2\mathit{i}}$ , for $\mathit{x}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ .

First we show that $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ if and only if $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{2\mathit{i}}$ . We claim that $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ if and only if $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{2\mathit{i}-1}$ . Assume that $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ , i.e., $\mathit{a}\in {\mathit{H}}^{\mathit{i}}$ . Since ${\mathit{H}}^{\mathit{i}}={\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}-1}\mathrm{)}\cap \mathit{S}$ , it holds that $\mathit{a}\in {\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}-1}\mathrm{)}$ and $\mathit{a}\in \mathit{S}$ . Relation $\mathit{a}\in {\mathrm{\Gamma }}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}-1}\mathrm{)}$ implies that a is defended by ${\mathit{H}}^{\mathit{i}-1}$ . Thus, for each p such that $\mathrm{(}\mathit{p}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}$ , there exists a defender of a, namely ${\mathit{c}}_{\mathit{p}}$ , such that $\mathrm{(}{\mathit{c}}_{\mathit{p}}\mathrm{,}\mathit{p}\mathrm{)}\in \mathit{R}$ , ${\mathit{c}}_{\mathit{p}}\in {\mathit{H}}^{\mathit{i}-1}$ and since ${\mathit{H}}^{\mathit{i}-1}$ is a strongly admissible extension, ${\mathit{c}}_{\mathit{p}}\ne \mathit{a}$ . Since defender ${\mathit{c}}_{\mathit{p}}$ belongs to ${\mathit{H}}^{\mathit{i}-1}$ , it holds that ${\mathit{c}}_{\mathit{p}}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}-1}\mathrm{)}$ and each parent of a is assigned to f in ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}-1}\mathrm{)}$ . By the induction hypothesis, ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}-1}\mathrm{)}={\mathit{v}}_{2\mathrm{(}\mathit{i}-1\mathrm{)}}={\mathit{v}}_{2\mathit{i}-2}$ . That is, for each p such that $\mathrm{(}\mathit{p}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}$ , it holds that $\mathit{p}\mapsto \mathbf{f}\in {\mathit{v}}_{2\mathit{i}-2}$ . Thus, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{2\mathit{i}-2}}\equiv \top$ , that is, $\mathit{a}\mapsto \mathbf{t}\in {\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_{2\mathit{i}-2}\mathrm{)}$ . Since $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ , it holds that $\mathit{a}\mapsto \mathbf{t}\in {\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_{2\mathit{i}-2}\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}$ . Thus, $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{2\mathit{i}-1}$ .

We have already shown that if $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ , then $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{2\mathit{i}-1}$ . Since all the relations are equivalence relations, the other direction works as well. That is, if $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{2\mathit{i}-1}$ then $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ . Thus, $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ iff $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{2\mathit{i}-1}$ . We use this equation in the proof of the next item. Further, since the characteristic function is a monotonic function, $\mathit{a}\mapsto \mathbf{t}\in {\mathit{v}}_{2\mathit{i}-1}$ implies that $\mathit{a}\mapsto \mathbf{t}\in {\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_{2\mathit{i}-1}\mathrm{)}$ . Hence, $\mathit{a}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ if and only if $\mathit{a}\mapsto \mathbf{t}\in \mathrm{(}{\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_{2\mathit{i}-1}\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}\mathrm{)}={\mathit{v}}_{2\mathit{i}}$ .

We show that $\mathit{a}\mapsto \mathbf{f}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ if and only if $\mathit{a}\mapsto \mathbf{f}\in {\mathit{v}}_{2\mathit{i}}$ . Assume that $\mathit{a}\mapsto \mathbf{f}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ . By the definition of the ${\mathit{\text{Ext2Int}}}_{\mathit{F}}$ function, there exists a parent of a, namely p, such that $\mathit{p}\in {\mathit{H}}^{\mathit{i}}$ , i.e., $\mathit{p}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ . As shown in the first item, $\mathit{p}\mapsto \mathbf{t}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ if and only if $\mathit{p}\mapsto \mathbf{t}\in {\mathit{v}}_{2\mathit{i}-1}$ . Thus, ${\mathit{\phi }}_{\mathit{a}}^{{\mathit{v}}_{2\mathit{i}-1}}\equiv \perp$ . Hence, $\mathit{a}\mapsto \mathbf{f}\in {\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_{2\mathit{i}-1}\mathrm{)}$ . On the other hand, $\mathit{a}\mapsto \mathbf{f}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ implies that $\mathit{a}\mapsto \mathbf{f}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ , since ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}={\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{F}\mathrm{(}{\mathit{H}}^{\mathit{i}-1}\mathrm{)}\mathrm{)}\sqcap {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ . That is, $\mathit{a}\mapsto \mathbf{f}\in \mathrm{(}{\mathrm{\Gamma }}_{{\mathit{D}}_{\mathit{F}}}\mathrm{(}{\mathit{v}}_{2\mathit{i}-1}\mathrm{)}{\sqcap }_{\mathit{i}}\mathit{v}\mathrm{)}={\mathit{v}}_{2\mathit{i}}$ . Thus, if $\mathit{a}\mapsto \mathbf{f}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ , then $\mathit{a}\mapsto \mathbf{f}\in {\mathit{v}}_{2\mathit{i}}$ . Since all the relations are equivalence relations, $\mathit{a}\mapsto \mathbf{f}\in {\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}$ if and only if $\mathit{a}\mapsto \mathbf{f}\in {\mathit{v}}_{2\mathit{i}}$ .

To conclude, ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}={\mathit{v}}_{2\mathit{i}}$ , for $\mathit{i}⩾0$ . □

In Section 4, we showed that an extension is a strongly admissible extension of AF F if and only if ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ is a strongly admissible interpretation of the associated ADF ${\mathit{D}}_{\mathit{F}}$ . Thus, the map of each ${\mathit{H}}^{\mathit{i}}$ via ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}.\mathrm{)}$ , such that ${\mathit{H}}^{\mathit{i}}$ is as in Lemma 30, is a strongly admissible interpretation of ${\mathit{D}}_{\mathit{F}}$ . However, by Theorem 32, ${\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{\mathit{j}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ as in Lemma 26 is a map of an ${\mathit{H}}^{\mathit{i}}$ if and only if j is an even number, i.e., ${\mathit{\text{Ext2Int}}}_{\mathit{F}}\mathrm{(}{\mathit{H}}^{\mathit{i}}\mathrm{)}={\mathrm{\Gamma }}_{\mathit{D}\mathrm{,}\mathit{v}}^{2\mathit{i}}\mathrm{(}{\mathit{v}}_{\mathbf{u}}\mathrm{)}$ , for i with $\mathit{i}⩾0$ .

7. Conclusion

In this work we have defined the concept of strong admissibility semantics for ADFs, based on the concept of strongly justified arguments. From a theoretical perspective, in Section 3, we observe that the strongly admissible interpretations of a given ADF form a lattice with the trivial interpretation as the unique minimal element and the grounded interpretation as the unique maximal element. Furthermore, in Section 4 we prove that the concept of strong admissibility semantics of ADFs forms a proper generalization of the concept of strong admissibility semantics of AFs [8,21].

In addition, in Section 5 we present an alternative definition for an interpretation being strongly admissible without checking whether all the arguments that are presented in that interpretation are strongly justified. This leads to Algorithm 1 to answer the verification problem under strong admissibility semantics of ADFs. Moreover, based on the new definition of strongly admissible interpretations of ADFs, we present an alternative definition for an argument being strongly justified in a given interpretation, in which there is no need to find a set of arguments that satisfies the conditions of Definition 18, for a given argument. This definition leads to Algorithm 2, to answer the decision problem whether a given argument is a strongly justified argument in a given interpretation.

In Section 6, we indicate further relations between the sequence of strongly admissible extensions of an AF F and the sequence of strongly admissible interpretations of the associated ADF ${\mathit{D}}_{\mathit{F}}$ . That is, we show that there is no one-to-one relation between the sequence of strongly admissible extensions constructed based on a strongly admissible extension S of a given AF F and the sequence of strongly admissible interpretations constructed based on $\mathit{\text{Ext2Int}}\mathrm{(}\mathit{S}\mathrm{)}$ of the associated ADF ${\mathit{D}}_{\mathit{F}}$ .

It is a possible topic of future research to show that the notion of strong admissibility semantics of ADFs can be reused for those generalizations of AFs that can be represented in ADFs, namely SETAFs [48] and bipolar AFs [31].

In addition, we proved that each grounded interpretation is the unique maximal element of the lattice of strongly admissible interpretations. Thus, it seems that the concept of strong admissibility can play a significant role in the dialectical proof procedures that we have introduced for grounded semantics in [40]. The idea of the grounded discussion games presented in [40] is that a discussion game can serve as an explanation why a particular argument should be accepted/denied in the grounded interpretation of a given ADF.

Since the grounded semantics is the unique maximal element of the lattice constructed by strongly admissible interpretations, the concept of strong admissibility is related to grounded semantics in a similar way as the concept of admissibility is related to preferred semantics. That is, to answer the credulous decision problem of an ADF under the grounded semantics, there is no need to construct the full grounded interpretation of the given ADF. Instead, it is enough to construct a strongly admissible interpretation of the given ADF that satisfies the decision problem. In other words, answering the credulous decision problem of ADFs under the grounded semantics is equivalent to answering the same decision problem under the strong admissibility semantics. Similarly, to answer the credulous decision problem of ADFs under preferred semantics, it is enough to investigate whether there exists an admissible interpretation in order to solve the decision problem. We used this method in preferred discussion games in [39] to answer the credulous decision problem of ADFs under preferred semantics.

On the other hand, the grounded discussion game (GDG) presented in [40] was defined over ADFs without any redundant links, to answer whether a given argument is credulously justifiable under the grounded semantics of an ADF. However, the concept of strongly admissible semantics is presented for all kinds of ADFs. Thus, we will investigate whether the concept of strongly admissible semantics is at the basis of the proof procedures of the grounded discussion games for ADFs without any redundant links.

Intuitively, it seems that the grounded discussion game and a strongly admissible interpretation are two sides of the same coin to investigate whether a queried argument is credulously justified in the grounded interpretation of an ADF. Moreover, both methods can be used to explain ‘why is an argument credulously justified in the grounded interpretation?’ Thus, a motivation for future work is to study the relation between these two approaches.

In addition, another possible question that can be answered using the concept of strongly admissible semantics of ADFs is whether a grounded discussion game contains the least possible amount of information about the truth values of ancestors of the argument in question to answer the credulous decision problem under grounded semantics; in other words, whether the grounded discussion game presents the shortest explanation that answers the credulous decision problem under strongly admissible/grounded semantics for a given argument in an ADF. This question is interesting, since specifically when the proponent wins the game, we are eager to know whether the proponent presents the least possible amount of information to convince the opponent about the truth of their initial claim, i.e., acceptance/denial of an argument in the grounded interpretation.

Computational complexity results of different semantics of AFs and ADFs are presented in [35,43,49,56]. Computational complexity of strongly admissible semantics of AFs is studied in [36]. Further, in [26], the computational complexity of identifying strongly admissible labellings with bounded or minimal size is studied. As a future work, it would be interesting to clarify the computational complexity of investigating: (1) whether a given interpretation is a strongly admissible interpretation, (2) whether a given argument is credulously/skeptically justifiable under the strongly semantics of a given ADFs.