Revisiting initial sets in abstract argumentation

Abstract

We revisit the notion of initial sets by Xu and Cayrol (In Proceedings of the 1st Chinese Conference on Logic and Argumentation (CLAR’16) 2016), i. e., non-empty minimal admissible sets in abstract argumentation frameworks. Initial sets are a simple concept for analysing conflicts in an abstract argumentation framework and to explain why certain arguments can be accepted. We contribute with new insights on the structure of initial sets and devise a simple non-deterministic construction principle for any admissible set, based on iterative selection of initial sets of the original framework and its induced reducts. In particular, we characterise many existing admissibility-based semantics via this construction principle, thus providing a constructive explanation on the structure of extensions. We also investigate certain problems related to initial sets with respect to their computational complexity.

1. Introduction

Formal argumentation [3,6] encompasses approaches for non-monotonic reasoning that focus on the role of arguments and their interactions. The most well-known approach is that of abstract argumentation frameworks [19] that model arguments as vertices in a directed graph, where a directed edge from an argument a to an argument b denotes an attack from a to b. Although conceptually simple, abstract argumentation frameworks can be used in a variety of argumentative scenarios such as persuasion dialogues [16], explanations in recommendation systems [31], mathematical modelling [11], or as a target formalism of structured argumentation formalisms [28,35]. Formal semantics are given to abstract argumentation frameworks by extensions, i. e., sets of arguments that can jointly be accepted and represent a coherent standpoint on the conflicts between the arguments. Different variants of such semantics have been proposed [5], but there are also other (non set-based) approaches such as ranking-based semantics [1] and probabilistic approaches [26].

A particular advantage of approaches to formal argumentation is the capability to explain the reasoning behind certain conclusions using human-accessible concepts such as arguments and counterarguments. Works such as [2,27,29,31–33,36] have already explored certain aspects of the explanatory power of approaches to formal argumentation. Amgoud and Prakken [2] and Rago et. al [31] develop argumentation formalisms for decision-making that augment recommendations with arguments. In [33] an extension to abstract argumentation frameworks is developed that explicitly includes a relationship for an “explanation”, while Liao and van der Torre [27] define “explanation semantics” for ordinary abstract argumentation frameworks. Saribatur, Wallner, and Woltran [32] as well as Niskanen and Järvisalo [29] address computational problems and develop a notion for explaining non-acceptability of arguments to, e. g., verify results of an argumentation solver. Finally, [36] presents strong explanations as a mechanism to explain acceptability of (sets of) arguments.

In this paper, we revisit one of the fundamental concepts underlying approaches to formal argumentation (and abstract argumentation in particular) for the purpose of explaining, namely admissibility. Informally speaking, a set of arguments is admissible if each of its members is defended against any attack from the outside (we will provide formal details in Section 2). Many popular semantics for abstract argumentation rely on the notion of admissibility. In particular, a preferred extension is a maximal (wrt. set inclusion) admissible set and preferred semantics satisfies many desirable properties [5]. However, since a preferred extension is a maximal admissible set, it can hardly be used for explaining why a certain argument is acceptable: such an extension may contain many irrelevant arguments and its size alone distracts from the particular reasons why a certain member is acceptable. Our aim is to investigate why certain arguments are contained in, e. g., a preferred extension and how we can decompose such large extensions into smaller sets that allow us to justify the reasoning process behind such complex semantics. As a tool for our investigation, we consider initial sets, i. e., non-empty admissible sets that are minimal wrt. set inclusion. Initial sets have been introduced in [38] and further analysed in [39,40]. We contribute to this analysis with new insights on the structure of initial sets and, in particular, to the use of initial sets for the task of explanation. In fact, initial sets can exactly be used for the purpose mentioned before [38]: they allow us to decompose large extensions into smaller fragments, each of them representing a single resolved issue in the argumentation framework and thus showcases the reasoning behind certain semantics. This has been done already in some form in [38–40] but we present a new, and arguably more elegant, formalisation of that idea that allows us to derive new results as well. Using the notion of a reduct [8], we can concisely represent any admissible set as a sequence of initial sets of the original framework and derived reducts. Moreover, we characterise many admissibility-based semantics through a step-wise construction process using certain selections of initial sets (this has been hinted at using the original formalisation for complete and preferred semantics in [40]). We round up our analysis with a characterisation of the computational complexity of certain tasks related to initial sets, which is also missing so far from the literature.

In summary, the contributions of this paper are as follows:

We revisit initial sets and investigate further properties (Section 3)

We provide a characterisation result of admissible sets and many admissibility-based semantics (Section 4)

We analyse certain computational problems wrt. their complexity (Section 5)

Section 2 introduces preliminaries on abstract argumentation and Section 6 concludes this paper.

Complete proofs can be found in the appendix. A short paper presenting the main ideas of this work has been published before in [34].

2. Abstract argumentation

Let $\mathfrak{A}$ denote a universal set of arguments. An abstract argumentation framework $\mathsf{AF}$ is a tuple $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ where $\mathsf{A}\subseteq \mathfrak{A}$ is a finite set of arguments and $\mathsf{R}$ is a relation $\mathsf{R}\subseteq \mathsf{A}\times \mathsf{A}$ [19]. Let $\mathfrak{AF}$ denote the set of all abstract argumentation frameworks. For two arguments $\mathit{a}\mathrm{,}\mathit{b}\in \mathsf{A}$ the relation $\mathit{a}\mathsf{R}\mathit{b}$ means that argument a attacks argument b. For $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ and ${\mathsf{AF}}^{\prime }=\mathrm{(}{\mathsf{A}}^{\prime }\mathrm{,}{\mathsf{R}}^{\prime }\mathrm{)}$ we write ${\mathsf{AF}}^{\prime }⊑\mathsf{AF}$ iff ${\mathsf{A}}^{\prime }\subseteq \mathsf{A}$ and ${\mathsf{R}}^{\prime }=\mathsf{R}\cap \mathrm{(}{\mathsf{A}}^{\prime }\times {\mathsf{A}}^{\prime }\mathrm{)}$ . For a set $\mathit{X}\subseteq \mathsf{A}$ , we denote by $\mathsf{AF}{|}_{\mathit{X}}=\mathrm{(}\mathit{X}\mathrm{,}\mathsf{R}\cap \mathrm{(}\mathit{X}\times \mathit{X}\mathrm{)}\mathrm{)}$ the projection of $\mathsf{AF}$ on X. For a set $\mathit{S}\subseteq \mathsf{A}$ we define $$\begin{array}{ll}\hfill & {\mathit{S}}^{+}=\{\mathit{a}\in \mathsf{A}\mid \exists \mathit{b}\in \mathit{S}:\mathit{b}\mathsf{R}\mathit{a}\}\\ \hfill & {\mathit{S}}^{-}=\{\mathit{a}\in \mathsf{A}\mid \exists \mathit{b}\in \mathit{S}:\mathit{a}\mathsf{R}\mathit{b}\}\end{array}$$ If S is a singleton set, we omit brackets for readability, i. e., we write ${\mathit{a}}^{-}$ ( ${\mathit{a}}^{+}$ ) instead of ${\{\mathit{a}\}}^{-}$ ( ${\{\mathit{a}\}}^{+}$ ). For two sets S and ${\mathit{S}}^{\prime }$ we write $\mathit{S}\mathsf{R}{\mathit{S}}^{\prime }$ iff ${\mathit{S}}^{+}\cap {\mathit{S}}^{\prime }\ne \varnothing$ . We say that a set $\mathit{S}\subseteq \mathsf{A}$ is conflict-free if for all $\mathit{a}\mathrm{,}\mathit{b}\in \mathit{S}$ it is not the case that $\mathit{a}\mathsf{R}\mathit{b}$ . A set S defends an argument $\mathit{b}\in \mathsf{A}$ if for all a with $\mathit{a}\mathsf{R}\mathit{b}$ there is $\mathit{c}\in \mathit{S}$ with $\mathit{c}\mathsf{R}\mathit{a}$ . A conflict-free set S is called admissible if S defends all $\mathit{a}\in \mathit{S}$ . Let $\mathsf{\text{adm}}\mathrm{(}\mathsf{AF}\mathrm{)}$ denote the set of admissible sets of $\mathsf{AF}$ .

Different semantics can be phrased by imposing constraints on admissible sets [5]. In particular, an admissible set E

is a complete (co) extension iff for all $\mathit{a}\in \mathsf{A}$ , if E defends a then $\mathit{a}\in \mathit{E}$ ,

is a grounded (gr) extension iff E is complete and minimal,

is a stable (st) extension iff $\mathit{E}\cup {\mathit{E}}^{+}=\mathsf{A}$ ,

is a preferred (pr) extension iff E is maximal.

is a semi-stable (sst) extension iff $\mathit{E}\cup {\mathit{E}}^{+}$ is maximal,

is an ideal (id) extension iff E is the maximal admissible set with $\mathit{E}\subseteq {\mathit{E}}^{\prime }$ for each preferred extension ${\mathit{E}}^{\prime }$ .

is a strongly admissible (sa) extension iff $\mathit{E}=\varnothing$ or each $\mathit{a}\in \mathit{E}$ is defended by some strongly admissible ${\mathit{E}}^{\prime }\subseteq \mathit{E}\setminus \{\mathit{a}\}$ .

All statements on minimality/maximality are meant to be with respect to set inclusion. For $\mathit{\sigma }\in \{\mathsf{\text{co}}\mathrm{,}\mathsf{\text{gr}}\mathrm{,}\mathsf{\text{st}}\mathrm{,}\mathsf{\text{pr}}\mathrm{,}\mathsf{\text{sst}}\mathrm{,}\mathsf{\text{id}}\mathrm{,}\mathsf{\text{sa}}\}$ let $\mathit{\sigma }\mathrm{(}\mathsf{AF}\mathrm{)}$ denote the set of σ-extensions of $\mathsf{AF}$ . We say a semantics σ is admissibility-based if $\mathit{\sigma }\mathrm{(}\mathsf{AF}\mathrm{)}\subseteq \mathsf{\text{adm}}\mathrm{(}\mathsf{AF}\mathrm{)}$ for all $\mathsf{AF}$ . Note that all semantics above are admissibility-based but there are also others such as CF2 semantics [7] and weak admissibility-based semantics [8].

3. Revisiting initial sets

Admissibility captures the basic intuition for an explanation why a certain argument can be regarded as acceptable. More concretely, if S is an admissible set then $\mathit{a}\in \mathit{S}$ is accepted because all arguments in S are accepted, every attacker of a is attacked back by some argument in S. However, admissibility alone is not sufficient to model explainability as it does not take relevance into account.

Example 1.

Consider the argumentation framework ${\mathsf{AF}}_0$ depicted in Fig. 1. There are eight admissible sets containing the argument e: $$\begin{array}{l}{\mathit{S}}_1=\{\mathit{b}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{h}\mathrm{,}\mathit{i}\}{\mathit{S}}_2=\{\mathit{b}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{i}\}{\mathit{S}}_3=\{\mathit{b}\mathrm{,}\mathit{e}\mathrm{,}\mathit{h}\mathrm{,}\mathit{i}\}\\ {\mathit{S}}_4=\{\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{h}\mathrm{,}\mathit{i}\}{\mathit{S}}_5=\{\mathit{b}\mathrm{,}\mathit{e}\mathrm{,}\mathit{i}\}{\mathit{S}}_6=\{\mathit{f}\mathrm{,}\mathit{e}\mathrm{,}\mathit{i}\}\\ {\mathit{S}}_7=\{\mathit{h}\mathrm{,}\mathit{e}\mathrm{,}\mathit{i}\}{\mathit{S}}_8=\{\mathit{e}\mathrm{,}\mathit{i}\}\end{array}$$ ${\mathit{S}}_1$ is also a preferred extension. However, it is also clear that arguments b, f, and h are not integral for defending e and the set ${\mathit{S}}_8$ presents a concise description of what is needed in order to deem e as acceptable (wrt. admissibility), namely only e and i.

In the following, we take relevance into account by considering minimal (wrt. set inclusion) admissible sets. Of course, a notion of minimal admissible set without further constraints is not a useful concept as the empty set is always admissible and constitutes the unique minimal admissible set. Non-empty minimal admissible sets have been coined initial sets by Xu and Cayrol in [38].

Fig. 1.

${\mathsf{AF}}_0$ from example 1.

Definition 1 ([38]).

For $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ , a set $\mathit{S}\subseteq \mathsf{A}$ with $\mathit{S}\ne \varnothing$ is called an initial set if S is admissible and there is no admissible ${\mathit{S}}^{\prime }⊊\mathit{S}$ with ${\mathit{S}}^{\prime }\ne \varnothing$ . Let $\mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ denote the set of initial sets of $\mathsf{AF}$ .

Example 2.

We continue Example 1. There are four initial sets of ${\mathsf{AF}}_0$ : $\{\mathit{f}\}$ , $\{\mathit{h}\}$ , $\{\mathit{d}\mathrm{,}\mathit{j}\}$ , and $\{\mathit{e}\mathrm{,}\mathit{i}\}$ .

As the previous example shows, an initial set is not supposed to provide a “solution” to the whole argumentation represented in an abstract argumentation framework, but “solves” a single atomic conflict (or in the case of $\{\mathit{h}\}$ points to an obvious deterministic inference step). In fact, we can identify three different types of initial sets.

Definition 2.

For $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ and $\mathit{S}\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ , we say that

S is unattacked iff ${\mathit{S}}^{-}=\varnothing$ ,

S is unchallenged iff ${\mathit{S}}^{-}\ne \varnothing$ and there is no ${\mathit{S}}^{\prime }\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ with ${\mathit{S}}^{\prime }\mathsf{R}\mathit{S}$ ,

S is challenged iff there is ${\mathit{S}}^{\prime }\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ with ${\mathit{S}}^{\prime }\mathsf{R}\mathit{S}$ .

Note that only unattacked initial sets have been considered explicitly in [40]; in particular, note that every unattacked initial set S is a singleton $\mathit{S}=\{\mathit{a}\}$ . Observe that the notions of unattacked, unchallenged, and challenged initial sets are mutually exclusive and exhaustive. Let ${\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ , ${\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ , and ${\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ denote the set of unattacked, unchallenged, and challenged initial sets, respectively. So we have $\mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}={\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\cup {\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\cup {\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ . Moreover, for $\mathit{S}\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ let $$\begin{array}{ll}\hfill \mathsf{\text{conflicts}}\mathrm{(}\mathit{S}\mathrm{,}\mathsf{AF}\mathrm{)}& =\{{\mathit{S}}^{\prime }\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}\mid {\mathit{S}}^{\prime }\mathsf{R}\mathit{S}\}\end{array}$$ denote the set of conflicting initial sets of S, which is always empty in the case of unattacked and unchallenged initial sets. Note that $\mathit{S}\mathsf{R}{\mathit{S}}^{\prime }$ implies ${\mathit{S}}^{\prime }\mathsf{R}\mathit{S}$ for any $\mathit{S}\mathrm{,}{\mathit{S}}^{\prime }\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ as ${\mathit{S}}^{\prime }$ is admissible and therefore defends itself.

Example 3.

We continue Example 2. Here we have $$\begin{array}{l}{\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}=\{\{\mathit{h}\}\}\\ {\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}=\{\{\mathit{f}\}\}\\ {\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}=\{\{\mathit{d}\mathrm{,}\mathit{j}\}\mathrm{,}\{\mathit{e}\mathrm{,}\mathit{i}\}\}\end{array}$$ and $\{\mathit{d}\mathrm{,}\mathit{j}\}$ and $\{\mathit{e}\mathrm{,}\mathit{i}\}$ are in conflict with each other, i. e., $\mathsf{\text{conflicts}}\mathrm{(}\{\mathit{d}\mathrm{,}\mathit{j}\}\mathrm{,}\mathsf{AF}\mathrm{)}=\{\{\mathit{e}\mathrm{,}\mathit{i}\}\}$ and $\mathsf{\text{conflicts}}\mathrm{(}\{\mathit{e}\mathrm{,}\mathit{i}\}\mathrm{,}\mathsf{AF}\mathrm{)}=\{\{\mathit{d}\mathrm{,}\mathit{j}\}\}$ .

Before we continue with characterising arbitrary admissible sets using initial sets in Section 4, we first contribute some new results on the structure of initial sets, therefore extending the analysis from [38–40].

Initial sets have an interesting property with respect to strongly connected components as follows. Recall that we can decompose an abstract argumentation framework $\mathsf{AF}$ into its strongly connected components. More precisely, an abstract argumentation framework ${\mathsf{AF}}^{\prime }=\mathrm{(}{\mathsf{A}}^{\prime }\mathrm{,}{\mathsf{R}}^{\prime }\mathrm{)}$ is a strongly connected component (SCC) of $\mathsf{AF}$ , if ${\mathsf{AF}}^{\prime }⊑\mathsf{AF}$ s.t. there is a directed path between any pair $\mathit{a}\mathrm{,}\mathit{b}\in {\mathsf{A}}^{\prime }$ in ${\mathsf{AF}}^{\prime }$ and there is no larger ${\mathsf{AF}}^{″}$ with that property. Let $\mathsf{\text{SCC}}\mathrm{(}\mathsf{AF}\mathrm{)}$ be the set of SCCs of $\mathsf{AF}$ .

Example 4.

Consider again the argumentation framework ${\mathsf{AF}}_0$ from Fig. 1. ${\mathsf{AF}}_0$ decomposes as follows into SCCs: $\mathsf{\text{SCC}}\mathrm{(}{\mathsf{AF}}_0\mathrm{)}=\{{\mathsf{AF}}_0{|}_{\{\mathit{d}\mathrm{,}\mathit{e}\mathrm{,}\mathit{i}\mathrm{,}\mathit{j}\}}\mathrm{,}{\mathsf{AF}}_0{|}_{\{\mathit{c}\}}\mathrm{,}{\mathsf{AF}}_0{|}_{\{\mathit{h}\}}\mathrm{,}{\mathsf{AF}}_0{|}_{\{\mathit{g}\mathrm{,}\mathit{f}\mathrm{,}\mathit{a}\}}\mathrm{,}{\mathsf{AF}}_0{|}_{\{\mathit{b}\}}\}$

The following result shows that initial sets are always completely contained in a single SCC.

Proposition 1.

If S is an initial set of $\mathsf{AF}$ then there is ${\mathsf{AF}}^{\prime }=\mathrm{(}{\mathsf{A}}^{\prime }\mathrm{,}{\mathsf{R}}^{\prime }\mathrm{)}\in \mathsf{\text{SCC}}\mathrm{(}\mathsf{AF}\mathrm{)}$ s.t. $\mathit{S}\subseteq {\mathsf{A}}^{\prime }$ .

If S is an initial set let $\mathsf{\text{SCC}}\mathrm{(}\mathit{S}\mathrm{)}$ denote its SCC as in the above proposition. Initial sets can actually be characterised by their SCC as follows.

Proposition 2.

S is an initial set of $\mathsf{AF}$ if and only if S is an initial set of $\mathsf{\text{SCC}}\mathrm{(}\mathit{S}\mathrm{)}=\mathrm{(}{\mathsf{A}}^{\prime }\mathrm{,}{\mathsf{R}}^{\prime }\mathrm{)}$ and ${\mathit{S}}^{-}\subseteq {\mathsf{A}}^{\prime }$ .

In other words, a set S is an initial set iff it is an initial set of a single SCC and it is not attacked by arguments outside of the SCC.

We close this investigation on the relationship of initial sets with SCCs by making some straightforward observations regarding the types of initial sets.

Proposition 3.

Let $\mathit{S}\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ and $\mathsf{\text{SCC}}\mathrm{(}\mathit{S}\mathrm{)}=\mathrm{(}{\mathsf{A}}^{\prime }\mathrm{,}{\mathsf{R}}^{\prime }\mathrm{)}$ .

If S is unattacked then $|{\mathsf{A}}^{\prime }|=1$ .

If S is challenged or unchallenged then $|{\mathsf{A}}^{\prime }|\mathrm{>}1$ .

If S is challenged and ${\mathit{S}}^{\prime }\in \mathsf{\text{conflicts}}\mathrm{(}\mathit{S}\mathrm{,}\mathsf{AF}\mathrm{)}$ then $\mathsf{\text{SCC}}\mathrm{(}\mathit{S}\mathrm{)}=\mathsf{\text{SCC}}\mathrm{(}{\mathit{S}}^{\prime }\mathrm{)}$ .

In particular, the final observation in the previous proposition states that conflicts between initial sets are always within a single SCC.

4. Characterising admissibility-based semantics through initial sets

In [38,40] it has been shown that any admissible set (and in particular every complete and preferred extension) can be constructed by (1) selecting a set of non-conflicting initial sets, (2) adding further defended arguments, and (3) iterating this procedure taking so-called “J-acceptable” sets into account. In particular, the described mechanism involves iterative application of the characteristic function [19], computation of the grounded extension, and said notion of J-acceptability to provide those characterisations (and some further concepts). In this section, we provide a (arguably) more elegant formalisation of these ideas that allows us to derive characterisations of further semantics as well as some impossibility results. Results that are (partly) due to works [38–40] are annotated as such, all remaining results are new.

Our characterisations rely on the notion of the reduct [8].

Definition 3.

For $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ and $\mathit{S}\subseteq \mathsf{A}$ , the S-reduct ${\mathsf{AF}}^{\mathit{S}}$ of $\mathsf{AF}$ is defined via ${\mathsf{AF}}^{\mathit{S}}=\mathsf{AF}{|}_{\mathsf{A}\setminus \mathrm{(}\mathit{S}\cup {\mathit{S}}^{+}\mathrm{)}}$ .

As a single initial set S solves an atomic conflict in an abstract argumentation framework $\mathsf{AF}$ , “committing” to it by moving to ${\mathsf{AF}}^{\mathit{S}}$ may reveal further conflicts and thus new initial sets. We can make the following observations on this aspect.

Proposition 4.

Let $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ be an abstract argumentation framework and $\mathit{S}\mathrm{,}{\mathit{S}}^{\prime }\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ with $\mathit{S}\ne {\mathit{S}}^{\prime }$ .

If ${\mathit{S}}^{\prime }\in {\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ then ${\mathit{S}}^{\prime }\in {\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}{\mathsf{AF}}^{\mathit{S}}\mathrm{)}$

If ${\mathit{S}}^{\prime }\in \mathsf{\text{conflicts}}\mathrm{(}\mathit{S}\mathrm{,}\mathsf{AF}\mathrm{)}$ then ${\mathit{S}}^{\prime }\notin \mathsf{\text{IS}}\mathrm{(}{\mathsf{AF}}^{\mathit{S}}\mathrm{)}$

If ${\mathit{S}}^{\prime }\notin \mathsf{\text{conflicts}}\mathrm{(}\mathit{S}\mathrm{,}\mathsf{AF}\mathrm{)}$ then ${\mathit{S}}^{\prime }\cap \bigcup \mathsf{\text{IS}}\mathrm{(}{\mathsf{AF}}^{\mathit{S}}\mathrm{)}\ne \varnothing$

The above observations give an impression on how initial sets behave under reducts. So unattacked initial sets are always retained (item 1), conflicting initial sets are always removed (item 2), and non-conflicting initial sets are “essentially” retained (item 3). More precisely, while it may not be guaranteed that non-conflicting initial sets are still initial sets in the reduct, their arguments are still potentially acceptable, as the following example shows.

Example 5.

Consider the argumentation framework ${\mathsf{AF}}_1$ depicted in Fig. 2. We have $$\begin{array}{ll}\hfill \mathsf{\text{IS}}\mathrm{(}{\mathsf{AF}}_1\mathrm{)}& =\{\{\mathit{a}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{e}\}\}\end{array}$$ and $\{\mathit{b}\mathrm{,}\mathit{d}\}$ and $\{\mathit{e}\}$ are conflicting (there are no further conflicts). Now we have $$\begin{array}{ll}\hfill \mathsf{\text{IS}}\mathrm{\left(}{\mathsf{AF}}_1^{\{\mathit{e}\}}\mathrm{\right)}& =\{\{\mathit{c}\}\}\end{array}$$ So the initial set $\{\mathit{a}\mathrm{,}\mathit{c}\}$ of ${\mathsf{AF}}_1$ is not retained in ${\mathsf{AF}}_1^{\{\mathit{e}\}}$ , despite $\{\mathit{a}\mathrm{,}\mathit{c}\}$ and $\{\mathit{e}\}$ not being in conflict. However, we have that $\{\mathit{c}\}\subseteq \{\mathit{a}\mathrm{,}\mathit{c}\}$ is an initial set of ${\mathsf{AF}}_1^{\{\mathit{e}\}}$ . Furthermore, $\{\mathit{a}\}$ (the “remaining” argument of the initial set $\{\mathit{a}\mathrm{,}\mathit{c}\}$ ) is actually the unique initial set of ${\mathrm{(}{\mathsf{AF}}_1^{\{\mathit{e}\}}\mathrm{)}}^{\{\mathit{c}\}}$ .

Fig. 2.

${\mathsf{AF}}_1$ from Example 5.

The following results show that by an iterative selection of initial sets on the corresponding reducts, we can re-construct every admissible set. These observations have been hinted at in [38–40], but no formal proof had been provided. We make up for that now.

Theorem 1.

Let $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ be an abstract argumentation framework and $\mathit{S}\subseteq \mathsf{A}$ . S is admissible if and only if either

$\mathit{S}=\varnothing$ or

$\mathit{S}={\mathit{S}}_1\cup {\mathit{S}}_2$ , ${\mathit{S}}_1\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ and ${\mathit{S}}_2$ is admissible in ${\mathsf{AF}}^{{\mathit{S}}_1}$ .

Proof.

Let S be an admissible set and $\mathit{S}\ne \varnothing$ . By definition of initial sets, there is ${\mathit{S}}_1\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ with ${\mathit{S}}_1\subseteq \mathit{S}$ . It remains to show that ${\mathit{S}}_2=\mathit{S}\setminus {\mathit{S}}_1$ is admissible in ${\mathsf{AF}}^{{\mathit{S}}_1}$ . Let $\mathit{a}\in {\mathit{S}}_2$ and let ${\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}\in \mathsf{A}$ be the attackers of a in $\mathsf{AF}$ . Since S is admissible, there are arguments ${\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\in \mathit{S}$ so that ${\mathit{c}}_{\mathit{i}}$ attacks ${\mathit{b}}_{\mathit{i}}$ , $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{n}$ (possibly some of the ${\mathit{c}}_{\mathit{i}}$ are identical). Without loss of generality, assume ${\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{k}}\in {\mathit{S}}_1$ for some $\mathit{k}⩽\mathit{n}$ . Then ${\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{k}}$ are not present in ${\mathsf{AF}}^{{\mathit{S}}_1}$ , thus a must only be defended against ${\mathit{b}}_{\mathit{k}+1}\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}$ in ${\mathsf{AF}}^{{\mathit{S}}_1}$ . However, since ${\mathit{S}}_2=\mathit{S}\setminus {\mathit{S}}_1$ we have that ${\mathit{c}}_{\mathit{k}+1}\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\in {\mathit{S}}_2$ , showing that a is defended by ${\mathit{S}}_2$ in ${\mathsf{AF}}^{{\mathit{S}}_1}$ and, thus, ${\mathit{S}}_2$ is admissible in ${\mathsf{AF}}^{{\mathit{S}}_1}$ .

For the other direction,1

¹

Note that this direction can also be shown by using the fact that admissible “semantics” is fully decomposable [4], but we explicitly prove it for matters of simplicity.

if $\mathit{S}=\varnothing$ then S is also admissible. Assume $\mathit{S}={\mathit{S}}_1\cup {\mathit{S}}_2$ , ${\mathit{S}}_1\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ and ${\mathit{S}}_2$ is an admissible set of ${\mathsf{AF}}^{{\mathit{S}}_1}$ . We have to show that S is admissible. Let $\mathit{a}\in \mathit{S}$ and let ${\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}$ be the attackers of a in $\mathsf{AF}$ . If $\mathit{a}\in {\mathit{S}}_1$ then there are ${\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\in {\mathit{S}}_1\subseteq \mathit{S}$ such that ${\mathit{c}}_{\mathit{i}}$ attacks ${\mathit{b}}_{\mathit{i}}$ since ${\mathit{S}}_1$ is admissible. If $\mathit{a}\in {\mathit{S}}_2$ , assume for the sake of contradiction that there is an attacker b of a such that there is no $\mathit{b}\in \mathit{S}$ that attacks c in $\mathsf{AF}$ . It follows that b is also in ${\mathsf{AF}}^{{\mathit{S}}_1}$ and a is undefended by ${\mathit{S}}_2$ in ${\mathsf{AF}}^{{\mathit{S}}_1}$ . This contradicts the assumption that ${\mathit{S}}_2$ is admissible in ${\mathsf{AF}}^{{\mathit{S}}_1}$ . □

By recursively applying the above theorem, we obtain the following corollary.

Corollary 1.

Every non-empty admissible set S can be written as $\mathit{S}={\mathit{S}}_1\cup \cdots \cup {\mathit{S}}_{\mathit{n}}$ with pairwise disjoint ${\mathit{S}}_{\mathit{i}}$ , $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{n}$ , ${\mathit{S}}_1$ is an initial set of $\mathsf{AF}$ and every ${\mathit{S}}_{\mathit{i}}$ , $\mathit{i}=2\mathrm{,}\dots \mathrm{,}\mathit{n}$ is an initial set of ${\mathsf{AF}}^{{\mathit{S}}_1\cup \cdots \cup {\mathit{S}}_{\mathit{i}-1}}$ . Furthermore, only non-empty admissible sets S can be written in such a fashion.

Example 6.

Consider again the argumentation framework ${\mathsf{AF}}_0$ from Fig. 1 and recall that $$\begin{array}{ll}\hfill {\mathit{S}}_1& =\{\mathit{b}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{h}\mathrm{,}\mathit{i}\}\end{array}$$ is an admissible set of ${\mathsf{AF}}_0$ (and actually a preferred extension). ${\mathit{S}}_1$ can be written as $$\begin{array}{ll}\hfill {\mathit{S}}_1& =\{\mathit{h}\}\cup \{\mathit{f}\}\cup \{\mathit{e}\mathrm{,}\mathit{i}\}\cup \{\mathit{b}\}\end{array}$$ where

$\{\mathit{h}\}$ is an initial set of ${\mathsf{AF}}_0$ (Fig. 1),

$\{\mathit{f}\}$ is an initial set of ${\mathsf{AF}}_0^{\{\mathit{h}\}}$ (Fig. 3(a)),

$\{\mathit{e}\mathrm{,}\mathit{i}\}$ is an initial set of ${\mathsf{AF}}_0^{\{\mathit{h}\mathrm{,}\mathit{f}\}}$ (Fig. 3(b)), and

$\{\mathit{b}\}$ is an initial set of ${\mathsf{AF}}_0^{\{\mathit{e}\mathrm{,}\mathit{i}\mathrm{,}\mathit{h}\mathrm{,}\mathit{f}\}}$ (Fig. 3(c)).

Note that a decomposition $\mathit{S}={\mathit{S}}_1\cup \cdots \cup {\mathit{S}}_{\mathit{n}}$ of an admissible set S from Corollary 1 is not necessarily uniquely determined. In the previous example, ${\mathit{S}}_1$ could also have been constructed by selecting, e. g., $\{\mathit{f}\}$ first.

Fig. 3.

Reducts obtained from ${\mathsf{AF}}_0$ for the construction of ${\mathit{S}}_1=\{\mathit{b}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{h}\mathrm{,}\mathit{i}\}$ .

Let us now discuss the wider significance of Theorem 1 and Corollary 1. For that, recall the standard approach to compute and justify the (uniquely determined) grounded extension of an argumentation framework $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ [19], cf. also the discussion in [38]. Basically, the grounded extension E of $\mathsf{AF}$ can be computed by selecting any non-attacked argument $\mathit{a}\in \mathsf{A}$ , add it to E, remove a and all arguments attacked by a from $\mathsf{AF}$ (so move from $\mathsf{AF}$ to ${\mathsf{AF}}^{\{\mathit{a}\}}$ ), and continue the process until no further unattacked argument can be found. Observe the similarity of this procedure to the procedure indicated by Theorem 1: in order to construct any admissible set S of $\mathsf{AF}$ , first select any initial set ${\mathit{S}}^{\prime }$ of $\mathsf{AF}$ , add it to S (which is initially empty), remove ${\mathit{S}}^{\prime }$ and all arguments attacked by ${\mathit{S}}^{\prime }$ from $\mathsf{AF}$ , and continue the process. Therefore, initial sets allow us to serialise the construction of any admissible set into smaller steps, each of these steps solving a single conflict in the framework under consideration. Depending on how initial sets are selected at each step and how we end the process, we can also recover different semantics. Let us now formalise these ideas. For that, we first need two functions that define the selection mechanism of initial sets and the termination criterion.

Definition 4.

A state T is a tuple $\mathit{T}=\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}$ with $\mathsf{AF}\in \mathfrak{AF}$ and $\mathit{S}\subseteq \mathfrak{A}$ .

Definition 5.

A selection function α is any function $\mathit{\alpha }:2^{\mathfrak{A}}\times 2^{\mathfrak{A}}\times 2^{\mathfrak{A}}\to 2^{\mathfrak{A}}$ with $\mathit{\alpha }\mathrm{(}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{,}\mathit{Z}\mathrm{)}\subseteq \mathit{X}\cup \mathit{Y}\cup \mathit{Z}$ for all $\mathit{X}\mathrm{,}\mathit{Y}\mathrm{,}\mathit{Z}\subseteq \mathfrak{A}$ .

We will apply a selection function α in the form $\mathit{\alpha }\mathrm{(}{\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\mathrm{,}{\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\mathrm{,}{\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\mathrm{)}$ (for some $\mathsf{AF}$ ), so α selects a subset of the initial sets as eligible to be selected in the construction process. We explicitly differentiate the different types of initial sets as parameters here as a technical convenience.

Definition 6.

A termination function β is any function $\mathit{\beta }:\mathfrak{AF}\times 2^{\mathfrak{A}}\to \{0\mathrm{,}1\}$ .

A termination function β is used to indicate when a construction of an admissible set is finished (this will be the case if $\mathit{\beta }\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}=1$ ).

We will now define a transition system on states that makes use of a selection and a termination function to constrain the construction of admissible sets. For some selection function α, consider the following transition rule: $$\begin{array}{}\text{(1)}& \hfill \mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}\stackrel{{\mathit{S}}^{\prime }\in \mathit{\alpha }\mathrm{(}{\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\mathrm{,}{\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\mathrm{,}{\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\mathrm{)}}{\to }\mathrm{(}{\mathsf{AF}}^{{\mathit{S}}^{\prime }}\mathrm{,}\mathit{S}\cup {\mathit{S}}^{\prime }\mathrm{)}& \end{array}$$ If $\mathrm{(}{\mathsf{AF}}^{\prime }\mathrm{,}{\mathit{S}}^{\prime }\mathrm{)}$ can be reached from $\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}$ via a finite number of steps (this includes no steps at all) with the above rule we write $\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}{⇝}^{\mathit{\alpha }}\mathrm{(}{\mathsf{AF}}^{\prime }\mathrm{,}{\mathit{S}}^{\prime }\mathrm{)}$ . If, in addition, the state $\mathrm{(}{\mathsf{AF}}^{\prime }\mathrm{,}{\mathit{S}}^{\prime }\mathrm{)}$ also satisfies the termination criterion of β, i. e., $\mathit{\beta }\mathrm{(}{\mathsf{AF}}^{\prime }\mathrm{,}\mathit{S}\mathrm{)}=1$ , then we write $\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}{⇝}^{\mathit{\alpha }\mathrm{,}\mathit{\beta }}\mathrm{(}{\mathsf{AF}}^{\prime }\mathrm{,}{\mathit{S}}^{\prime }\mathrm{)}$ .

Given concrete instances of α and β, let ${\mathcal{E}}^{\mathit{\alpha }\mathrm{,}\mathit{\beta }}\mathrm{(}\mathsf{AF}\mathrm{)}$ be the set of all S with $\mathrm{(}\mathsf{AF}\mathrm{,}\varnothing \mathrm{)}{⇝}^{\mathit{\alpha }\mathrm{,}\mathit{\beta }}\mathrm{(}{\mathsf{AF}}^{\prime }\mathrm{,}\mathit{S}\mathrm{)}$ (for some ${\mathsf{AF}}^{\prime }$ ).

Definition 7.

A semantics σ is serialisable with a selection function α and a termination function β if $\mathit{\sigma }\mathrm{(}\mathsf{AF}\mathrm{)}={\mathcal{E}}^{\mathit{\alpha }\mathrm{,}\mathit{\beta }}\mathrm{(}\mathsf{AF}\mathrm{)}$ for all $\mathsf{AF}$ .

A direct consequence of Corollary 1 is the following.

Theorem 2.

Admissible semantics 2

²

Although admissible sets are usually not regarded as a semantics, we can treat the function $\mathsf{\text{adm}}\mathrm{(}·\mathrm{)}$ as such.

is serialisable with $$\begin{array}{ll}\hfill {\mathit{\alpha }}_{\mathsf{\text{adm}}}\mathrm{(}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{,}\mathit{Z}\mathrm{)}& =\mathit{X}\cup \mathit{Y}\cup \mathit{Z}{\mathit{\beta }}_{\mathsf{\text{adm}}}\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}=1\end{array}$$

In other words, any admissible set can be constructed by not constraining the selection of initial sets at all ( ${\mathit{\alpha }}_{\mathsf{\text{adm}}}$ ) and accepting every reachable state ( ${\mathit{\beta }}_{\mathsf{\text{adm}}}$ ). We can also characterise most of the admissibility-based semantics from Section 2 through serialisation using specific selection and termination functions, as the following results show.

The following observation has been hinted at in [40], but not formally proven. Using the notions of selection and termination functions, we can make the construction principle of complete extensions explicit.

Theorem 3.

Complete semantics is serialisable with ${\mathit{\alpha }}_{\mathsf{\text{adm}}}$ and $$\begin{array}{ll}\hfill {\mathit{\beta }}_{\mathsf{\text{co}}}\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}& =\left\{\begin{array}{cc}1\hfill & \mathit{\text{if }}{\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}=\varnothing \hfill \\ 0\hfill & \mathit{\text{otherwise}}\hfill \end{array}\right.\end{array}$$

Note that ${\mathit{\beta }}_{\mathsf{\text{co}}}$ only accepts those states, which cannot be extended by already defended arguments (which are those appearing in ${\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ ). The above theorem also allows us to characterise complete extensions in a similar manner as admissible sets in Theorem 1.

Corollary 2.

Let $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ be an abstract argumentation framework and $\mathit{S}\subseteq \mathsf{A}$ . S is complete if and only if either

$\mathit{S}=\varnothing$ and ${\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}=\varnothing$ or

$\mathit{S}={\mathit{S}}_1\cup {\mathit{S}}_2$ , ${\mathit{S}}_1\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ and ${\mathit{S}}_2$ is complete in ${\mathsf{AF}}^{{\mathit{S}}_1}$ .

Grounded semantics has the same termination criterion as complete semantics, but constrains the selection of initial sets to those in ${\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ .

Theorem 4.

Grounded semantics is serialisable with $$\begin{array}{ll}\hfill {\mathit{\alpha }}_{\mathsf{\text{gr}}}\mathrm{(}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{,}\mathit{Z}\mathrm{)}& =\mathit{X}\end{array}$$ and ${\mathit{\beta }}_{\mathsf{\text{co}}}$ .

Note that ${\mathit{\alpha }}_{\mathsf{\text{gr}}}$ and ${\mathit{\beta }}_{\mathsf{\text{co}}}$ formalise the algorithm to compute the grounded extension sketched before. Therefore, the non-deterministic algorithm realised by the transition rule (1) is a generalisation of this algorithm. Similarly as Corollary 2 we obtain the following characterisation of grounded semantics in terms of the reduct.

Corollary 3.

Let $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ be an abstract argumentation framework and $\mathit{S}\subseteq \mathsf{A}$ . S is grounded if and only if either

$\mathit{S}=\varnothing$ and ${\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}=\varnothing$ or

$\mathit{S}={\mathit{S}}_1\cup {\mathit{S}}_2$ , ${\mathit{S}}_1\in {\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ and ${\mathit{S}}_2$ is grounded in ${\mathsf{AF}}^{{\mathit{S}}_1}$ .

For stable semantics, we do not need to constrain the selection of initial sets but only ensure that all arguments are either included in or attacked by the constructed extension.

Theorem 5.

Stable semantics is serialisable with ${\mathit{\alpha }}_{\mathsf{\text{adm}}}$ and $$\begin{array}{ll}\hfill {\mathit{\beta }}_{\mathsf{\text{st}}}\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}& =\left\{\begin{array}{cc}1\hfill & \mathit{\text{if }}\mathsf{AF}=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{)}\hfill \\ 0\hfill & \mathit{\text{otherwise}}\hfill \end{array}\right.\end{array}$$

As before, we obtain the following characterisation of stable semantics in terms of the reduct.

Corollary 4.

Let $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ be an abstract argumentation framework and $\mathit{S}\subseteq \mathsf{A}$ . S is stable if and only if either

$\mathit{S}=\varnothing$ and $\mathsf{A}=\varnothing$ or

$\mathit{S}={\mathit{S}}_1\cup {\mathit{S}}_2$ , ${\mathit{S}}_1\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ and ${\mathit{S}}_2$ is stable in ${\mathsf{AF}}^{{\mathit{S}}_1}$ .

For preferred semantics, we simply have to apply transitions exhaustively. Note that this result strengthens Proposition 3 from [40].

Theorem 6.

Preferred semantics is serialisable with ${\mathit{\alpha }}_{\mathsf{\text{adm}}}$ and $$\begin{array}{ll}\hfill {\mathit{\beta }}_{\mathsf{\text{pr}}}\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}& =\left\{\begin{array}{cc}1\hfill & \mathit{\text{if }}\mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}=\varnothing \hfill \\ 0\hfill & \mathit{\text{otherwise}}\hfill \end{array}\right.\end{array}$$

Corollary 5.

Let $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ be an abstract argumentation framework and $\mathit{S}\subseteq \mathsf{A}$ . S is preferred if and only if either

$\mathit{S}=\varnothing$ and $\mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}=\varnothing$ or

$\mathit{S}={\mathit{S}}_1\cup {\mathit{S}}_2$ , ${\mathit{S}}_1\in \mathsf{\text{IS}}\mathrm{(}\mathsf{AF}\mathrm{)}$ and ${\mathit{S}}_2$ is preferred in ${\mathsf{AF}}^{{\mathit{S}}_1}$ .

Our final positive result is about strong admissibility, which follows quite easily from the construction of the grounded extension.

Theorem 7.

Strong admissibility semantics is serialisable with ${\mathit{\alpha }}_{\mathsf{\text{gr}}}$ and ${\mathit{\beta }}_{\mathsf{\text{adm}}}$ .

Corollary 6.

Let $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ be an abstract argumentation framework and $\mathit{S}\subseteq \mathsf{A}$ . S is strongly admissible if and only if either

$\mathit{S}=\varnothing$ or

$\mathit{S}={\mathit{S}}_1\cup {\mathit{S}}_2$ , ${\mathit{S}}_1\in {\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}$ and ${\mathit{S}}_2$ is strongly admissible in ${\mathsf{AF}}^{{\mathit{S}}_1}$ .

A related result to the above observation is given by Baumann et. al in [9] (Definition 7 and Proposition 2). There, a strongly admissible extension E is characterised through the existence of pairwise disjoint sets ${\mathit{A}}_1\mathrm{,}\dots \mathrm{,}{\mathit{A}}_{\mathit{n}}$ such that $\mathit{E}={\mathit{A}}_1\cup \dots {\mathit{A}}_{\mathit{n}}$ , ${\mathit{A}}_1$ is a set of unattacked arguments in $\mathsf{AF}$ and ${\mathit{A}}_1\cup \cdots \cup {\mathit{A}}_{\mathit{j}}$ defends ${\mathit{A}}_{\mathit{j}+1}$ for all $1⩽\mathit{j}⩽\mathit{n}-1$ . Our construction above also implies the existence of these sets ${\mathit{A}}_1\mathrm{,}\dots \mathrm{,}{\mathit{A}}_{\mathit{n}}$ with the same properties, but with the additional feature that all ${\mathit{A}}_{\mathit{i}}$ , $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{n}$ are singleton sets (since unattacked initial sets are always singleton sets).

Missing from our results so far are the ideal and semi-stable semantics. Both of them cannot be serialised.

Theorem 8.

Ideal semantics is not serialisable.

The proof of the above theorem is given by the following counterexample.

Fig. 4.

The argumentation frameworks ${\mathsf{AF}}_2$ (top) and ${\mathsf{AF}}_3$ (bottom) from Example 7.

Example 7.

Consider the two argumentation frameworks ${\mathsf{AF}}_2$ and ${\mathsf{AF}}_3$ in Fig. 4. We have $$\begin{array}{ll}\hfill \mathsf{\text{id}}\mathrm{(}{\mathsf{AF}}_2\mathrm{)}& =\{\mathit{b}\}\mathsf{\text{id}}\mathrm{(}{\mathsf{AF}}_3\mathrm{)}=\{\mathit{b}\mathrm{,}\mathit{e}\}\end{array}$$ and $$\begin{array}{ll}\hfill {\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}{\mathsf{AF}}_2\mathrm{)}& ={\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}{\mathsf{AF}}_3\mathrm{)}=\varnothing \\ \hfill {\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}{\mathsf{AF}}_2\mathrm{)}& ={\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}{\mathsf{AF}}_3\mathrm{)}=\{\{\mathit{b}\}\mathrm{,}\{\mathit{e}\}\}\\ \hfill {\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}{\mathsf{AF}}_2\mathrm{)}& ={\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}{\mathsf{AF}}_3\mathrm{)}=\varnothing \end{array}$$ So no selection function α can distinguish these frameworks and should return either

$\mathit{\alpha }\mathrm{(}\varnothing \mathrm{,}\{\{\mathit{b}\}\mathrm{,}\{\mathit{e}\}\}\mathrm{,}\varnothing \mathrm{)}=\varnothing$ or

$\mathit{\alpha }\mathrm{(}\varnothing \mathrm{,}\{\{\mathit{b}\}\mathrm{,}\{\mathit{e}\}\}\mathrm{,}\varnothing \mathrm{)}=\{\{\mathit{b}\}\mathrm{,}\{\mathit{e}\}\}$ .

Note also that α cannot return just one of the two initial sets as they cannot be distinguished. In case 1, the ideal extensions of both ${\mathsf{AF}}_2$ and ${\mathsf{AF}}_3$ cannot be constructed. So assume case 2 and select $\{\mathit{e}\}$ in the first transition. Observe that ${\mathit{AF}}_2^{\{\mathit{e}\}}={\mathit{AF}}_3^{\{\mathit{e}\}}$ , so further constructions will be identical. Since the ideal extensions of ${\mathsf{AF}}_2$ and ${\mathsf{AF}}_3$ differ and no β can distinguish these cases, ideal semantics is not serialisable.

The above behaviour of ideal semantics is insofar surprising since the concept of unchallenged initial sets is closely related to the general idea of the ideal extension. Recall that the initial extension is the maximal admissible set contained in each preferred extension. This basically means that the arguments in the ideal extension are compatible with each admissible set and no admissible set attacks any argument in the ideal extension. On the other hand, an unchallenged initial set is likewise an undisputed admissible set, as there is no other initial set that attacks it. However, as the above example shows, unchallenged initial sets are not sufficient to characterise the ideal extension. We will discuss the relationship between unchallenged initial sets and the ideal extension a bit more below and in Section 5.

Likewise negative, but for somewhat different reasons, is the following result about semi-stable semantics.

Theorem 9.

Semi-stable semantics is not serialisable.

The reason that semi-stable semantics is not serialisable is that it needs some form of “global” view on candidate extensions to judge whether a set of arguments is indeed a semi-stable extension. We illustrate this in the next example (which also serves as the proof of Theorem 9).

Fig. 5.

The argumentation frameworks ${\mathsf{AF}}_4$ (top), ${\mathsf{AF}}_5$ (middle), and ${\mathsf{AF}}_6$ (bottom) from Example 8.

Example 8.

Consider the three argumentation frameworks ${\mathsf{AF}}_4$ , ${\mathsf{AF}}_5$ , ${\mathsf{AF}}_6$ in Fig. 5. Observe that $$\begin{array}{l}\mathsf{\text{sst}}\mathrm{(}{\mathsf{AF}}_4\mathrm{)}=\{\{\mathit{a}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathit{b}\}\}\\ \mathsf{\text{sst}}\mathrm{(}{\mathsf{AF}}_5\mathrm{)}=\{\{\mathit{b}\}\}\\ \mathsf{\text{sst}}\mathrm{(}{\mathsf{AF}}_6\mathrm{)}=\{\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\}\end{array}$$ However, $$\begin{array}{l}{\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}{\mathsf{AF}}_4\mathrm{)}={\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}{\mathsf{AF}}_5\mathrm{)}={\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}{\mathsf{AF}}_6\mathrm{)}=\varnothing \\ {\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}{\mathsf{AF}}_4\mathrm{)}={\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}{\mathsf{AF}}_5\mathrm{)}={\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}{\mathsf{AF}}_6\mathrm{)}=\varnothing \\ {\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}{\mathsf{AF}}_4\mathrm{)}={\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}{\mathsf{AF}}_5\mathrm{)}={\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}{\mathsf{AF}}_6\mathrm{)}=\{\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\}\end{array}$$ First, no selection function α can distinguish these frameworks (as it only operates on the sets ${\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}·\mathrm{)}$ , ${\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}·\mathrm{)}$ , and ${\mathsf{\text{IS}}}^{\leftrightarrow }\mathrm{(}·\mathrm{)}$ ) and would either return

$\mathit{\alpha }\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\}\mathrm{)}=\varnothing$ ,

$\mathit{\alpha }\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\}\mathrm{)}=\{\{\mathit{a}\}\}$ ,

$\mathit{\alpha }\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\}\mathrm{)}=\{\{\mathit{b}\}\}$ , or

$\mathit{\alpha }\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\}\mathrm{)}=\{\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\}$ .

In cases 1–3, not all semi-stable extensions can be constructed for, e. g., ${\mathsf{AF}}_4$ . For case 4 and ${\mathsf{AF}}_5$ , a valid transition would then produce the state ${\mathit{T}}_1=\mathrm{(}\mathrm{(}\{\mathit{c}\}\mathrm{,}\{\mathrm{(}\mathit{c}\mathrm{,}\mathit{c}\mathrm{)}\}\mathrm{)}\mathrm{,}\{\mathit{a}\}\mathrm{)}$ from which no further transition is possible. A β function for semi-stable semantics should now determine that ${\mathit{T}}_1$ is not a terminating state (since $\{\mathit{a}\}$ is not a semi-stable extension of ${\mathsf{AF}}_5$ ). However, the same state ${\mathit{T}}_1$ can also be reached for ${\mathsf{AF}}_6$ , but here $\{\mathit{a}\}$ is a semi-stable extension. Since β cannot distinguish these two scenarios at ${\mathit{T}}_1$ , there is no such β.

The same argument from above can also be used to show that eager semantics is not serialisable. The eager extension is the maximal (wrt. set inclusion) admissible set contained in every semi-stable extension, see e. g. [5]. In Example 8, the eager extension of ${\mathsf{AF}}_5$ is $\{\mathit{b}\}$ while it is ∅ for ${\mathsf{AF}}_4$ and ${\mathsf{AF}}_6$ . No pair $\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{\beta }\mathrm{)}$ can be defined to distinguish these cases as well.

The results of this section show that many admissibility-based semantics can be characterised through the notion of initial sets and a simple non-deterministic algorithm based on selecting initial sets at each step. This brings a new perspective on the rationality of admissibility-based semantics, as their basic construction principles are made explicit via an operational mechanism. This is similar in spirit to the purpose of discussion games [12] which model acceptability problems of individual arguments as an operational mechanism as well (here a dialogue between a proponent and an opponent). However, here we focused on the construction of whole extensions and not on acceptability problems of individual arguments.

The notion of serialisability also allows to define completely new semantics by defining only a selection and a termination function. For example, a straightforward idea for that would be the selection function ${\mathit{\alpha }}_0$ defined via $$\begin{array}{ll}\hfill {\mathit{\alpha }}_0\mathrm{(}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{,}\mathit{Z}\mathrm{)}& =\mathit{X}\cup \mathit{Y}\end{array}$$ and the termination function ${\mathit{\beta }}_0$ defined via $$\begin{array}{ll}\hfill {\mathit{\beta }}_0\mathrm{(}\mathsf{AF}\mathrm{,}\mathit{S}\mathrm{)}& =\left\{\begin{array}{cc}1\hfill & \text{if }{\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{(}\mathsf{AF}\mathrm{)}\cup {\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{(}\mathsf{AF}\mathrm{)}=\varnothing \hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}\right.\end{array}$$ which amounts to exhaustively adding unattacked and unchallenged initial sets. This yields a semantics that is more skeptical than the preferred semantics but less skeptical than the ideal semantics as the following result shows.

Theorem 10.

For every E with $\mathrm{(}\mathsf{AF}\mathrm{,}\varnothing \mathrm{)}{⇝}^{{\mathit{\alpha }}_0\mathrm{,}{\mathit{\beta }}_0}\mathrm{(}{\mathsf{AF}}^{\prime }\mathrm{,}\mathit{E}\mathrm{)}$

$\mathit{E}\subseteq {\mathit{E}}^{\prime }$ for some preferred extension ${\mathit{E}}^{\prime }$ and

${\mathit{E}}_{\mathsf{\text{id}}}\subseteq \mathit{E}$ for the ideal extension ${\mathit{E}}_{\mathsf{\text{id}}}$ .

Consider the following examples showing the difference between the above semantics and ideal semantics.

Example 9.

Consider again ${\mathsf{AF}}_2$ from Example 7 and depicted in Fig. 4. There are two extensions ${\mathit{E}}_1$ and ${\mathit{E}}_2$ wrt. to the serialisable semantics defined by ${\mathit{\alpha }}_0$ and ${\mathit{\beta }}_0$ : $$\begin{array}{ll}\hfill {\mathit{E}}_1& =\{\mathit{b}\}{\mathit{E}}_2=\{\mathit{b}\mathrm{,}\mathit{e}\}\end{array}$$ where the extension ${\mathit{E}}_2$ can be constructed by first selecting the initial set $\{\mathit{e}\}$ (which is unchallenged in ${\mathsf{AF}}_2$ ) and then $\{\mathit{b}\}$ .

Example 10.

Consider ${\mathsf{AF}}_7$ depicted in Fig. 6. There are four preferred extensions ${\mathit{E}}_1$ , ${\mathit{E}}_2$ , ${\mathit{E}}_3$ , and ${\mathit{E}}_4$ in ${\mathsf{AF}}_7$ defined via $$\begin{array}{ll}\hfill {\mathit{E}}_1& =\{\mathit{a}\mathrm{,}\mathit{e}\}{\mathit{E}}_2=\{\mathit{a}\mathrm{,}\mathit{d}\mathrm{,}\mathit{f}\}{\mathit{E}}_3=\{\mathit{b}\mathrm{,}\mathit{e}\}{\mathit{E}}_4=\{\mathit{b}\mathrm{,}\mathit{d}\mathrm{,}\mathit{f}\}\end{array}$$ and the ideal extension ${\mathit{E}}_{\mathit{id}}$ is empty: $$\begin{array}{ll}\hfill {\mathit{E}}_{\mathit{id}}& =\varnothing \end{array}$$ However, there is one extension ${\mathit{E}}_5$ wrt. to the serialisable semantics defined by ${\mathit{\alpha }}_0$ and ${\mathit{\beta }}_0$ : $$\begin{array}{ll}\hfill {\mathit{E}}_5& =\{\mathit{d}\mathrm{,}\mathit{f}\}\end{array}$$ The reason for that is that both $\{\mathit{d}\}$ and $\{\mathit{f}\}$ are unchallenged initial sets in ${\mathsf{AF}}_7$ (and once one is selected the other becomes an unattacked initial set and can be selected as well).

Fig. 6.

The argumentation framework ${\mathsf{AF}}_7$ from Example 10.

For future work, we intend to investigate the above and further possibilities for serialisable semantics in more detail.

5. Computational complexity

In order to round up our investigation of initial sets, we now analyse them wrt. computational complexity. We assume familiarity with basic concepts of computational complexity and basic complexity classes such as $\mathsf{\text{P}}$ , $\mathsf{\text{NP}}$ , $\mathsf{\text{coNP}}$ , see [30] for an introduction. We also require knowledge of the “non-standard” classes DP (and its complement coDP), ${\mathsf{\text{P}}}^{\mathsf{\text{NP}}}$ , and ${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ . The class DP is the class of decision problems that are a conjunction of a problem in NP and a problem in coNP, i. e., in language notation $\mathsf{\text{DP}}=\{{\mathit{L}}_1\cap {\mathit{L}}_2\mid {\mathit{L}}_1\in \mathsf{\text{NP}}\mathrm{,}{\mathit{L}}_2\in \mathsf{\text{coNP}}\}$ . The class ${\mathsf{\text{P}}}^{\mathsf{\text{NP}}}$ is the class of decision problems that can be solved by a deterministic polynomial-time algorithm that can make polynomially many adaptive queries3

³

A query is adaptive if it may depend on a previous query; queries are non-adaptive if they can be posed in any order or in parallel.

to an NP-oracle. The class ${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ [24] is the class of decision problems that can be solved by a deterministic polynomial-time algorithm that can make polynomially many non-adaptive queries to an NP-oracle. Note that ${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ is sometimes denoted by ${\mathrm{\Theta }}_2^{\mathit{P}}$ and is equal to ${\mathsf{\text{P}}}^{\mathsf{\text{NP}}[log]}$ , i. e., the class of decision problems solvable by deterministic polynomial-time algorithm that can make logarithmically many adaptive NP-oracle calls [30]. Observe also that $\mathsf{\text{DP}}\subseteq {\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ and $\mathsf{\text{coDP}}\subseteq {\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ as well as ${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}\subseteq {\mathsf{\text{P}}}^{\mathsf{\text{NP}}}$ .

We consider the following computational tasks for $\mathit{\sigma }\in \{\mathsf{\text{IS}}\mathrm{,}{\mathsf{\text{IS}}}^{\nleftarrow }\mathrm{,}{\mathsf{\text{IS}}}^{\nleftrightarrow }\mathrm{,}{\mathsf{\text{IS}}}^{\leftrightarrow }\}$ , cf. [22]:

Given $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ and $\mathit{S}\subseteq \mathsf{A}$ ,

decide whether $\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathsf{AF}\mathrm{)}$ .

Given $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ ,

decide whether $\mathit{\sigma }\mathrm{(}\mathsf{AF}\mathrm{)}\ne \varnothing$ .

Given $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ ,

decide whether $|\mathit{\sigma }\mathrm{(}\mathsf{AF}\mathrm{)}|=1$ .

Given $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ and $\mathit{a}\in \mathsf{A}$ ,

decide whether there is $\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathsf{AF}\mathrm{)}$ with $\mathit{a}\in \mathit{S}$ .

Given $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ and $\mathit{a}\in \mathsf{A}$ ,

decide whether for all $\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathsf{AF}\mathrm{)}$ , $\mathit{a}\in \mathit{S}$ .

Note that we do not consider the problems ${\mathit{\text{Exists}}}_{\mathit{\sigma }}^{\neg \varnothing }$ [22] (which asks whether there is a non-empty (initial) set) as these are equivalent to ${\mathit{\text{Exists}}}_{\mathit{\sigma }}$ due to the non-emptiness of all types of initial sets.

Table 1 summarises our results on the complexity of the above tasks, all proofs can be found in the appendix.

Table 1

Complexity of computational tasks related to initial sets. An attached “-h” refers to hardness for the class and an attached “-c” refers to completeness for the class. All hardness results are wrt. polynomial reductions

σ	$\mathsf{\text{IS}}$	${\mathsf{\text{IS}}}^{\nleftarrow }$	${\mathsf{\text{IS}}}^{\nleftrightarrow }$	${\mathsf{\text{IS}}}^{\leftrightarrow }$
${\mathit{\text{Ver}}}_{\mathit{\sigma }}$	in P	in P	coNP-c	NP-c
${\mathit{\text{Exists}}}_{\mathit{\sigma }}$	NP-c	in P	${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ -c	NP-c
${\mathit{\text{Unique}}}_{\mathit{\sigma }}$	DP-c	in P	in ${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ , DP-h	trivial
${\mathit{\text{Cred}}}_{\mathit{\sigma }}$	NP-c	in P	${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ -c	NP-c
${\mathit{\text{Skept}}}_{\mathit{\sigma }}$	coNP-c	in P	${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ -c	coNP-c

The results for $\mathsf{\text{IS}}$ mirror the results on admissible sets [22], with a few exceptions. While the problem of deciding whether a set S is admissible can be solved in logarithmic space with polynomial time [22], we only showed that the problem of deciding whether a set S is an initial set can be solved in polynomial time. It is unlikely (though a formal proof is missing at the moment) that we can strengthen these results in the same way as for admissible sets, since the minimality condition of an initial set suggest that subsets (of linear size) have to be constructed in an algorithm. Moreover, while the problems $\mathit{\text{Exists}}$ and $\mathit{\text{Skept}}$ are trivial for admissible sets [22] (since the empty set is always admissible), they are intractable for initial sets. The problem ${\mathit{\text{Unique}}}_{\mathsf{\text{IS}}}$ is DP-complete (it is coNP-complete for admissible sets) since existence of initial sets is not guaranteed.

We get some different complexity characterisations for the different types of initial sets. All tasks for unattacked initial sets are tractable, as only unattacked arguments have to be considered. All tasks become harder (under standard complexity-theoretic assumptions) when only unchallenged initial sets are considered. In particular, ${\mathit{\text{Ver}}}_{\mathit{\sigma }}$ is coNP-complete as it has to be verified that there is no other initial set attacking the set that is to be verified. Moreover, Theorem 10 already showed that there is some conceptual relation between unchallenged initial sets and the ideal extension. This is strengthened by our observation of the computational complexity of the other tasks pertaining to unchallenged initial sets, as all non-trivial tasks on ideal semantics are ${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ -complete (under randomised reductions) [21]. We showed ${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ -completeness (under polynomial reductions) for most of those tasks as well, with the exception being the problem ${\mathit{\text{Unique}}}_{{\mathsf{\text{IS}}}^{\nleftrightarrow }}$ , where we only showed $\mathsf{\text{DP}}$ -hardness and a ${\mathsf{\text{P}}}_{\parallel }^{\mathsf{\text{NP}}}$ -hardness proof remains an open problem.

The complexity of the tasks for challenged initial sets are similar as in the general case, with two exceptions. Verification of challenged initial sets is intractable as another initial set has to found that attacks the set under consideration. Moreover, ${\mathit{\text{Unique}}}_{{\mathsf{\text{IS}}}^{\leftrightarrow }}$ has the trivial answer NO for all instances as the existence of one challenged initial set ${\mathit{S}}_1$ implies the existence of another challenged initial set ${\mathit{S}}_2$ that attacks (and is attacked by) ${\mathit{S}}_1$ .

6. Discussion

In this paper, we revisited the notion of initial sets, i. e., non-empty minimal admissible sets. We investigated their general properties and used them as basic building blocks to construct any admissible set. We have characterised many admissibility-based semantics via this approach and concluded our analysis with some notes on computational complexity.

Initial sets allow us to concisely explain why a certain argument can be accepted (e. g., whether it is contained in a preferred extension). We can deconstruct an extension via the characterisation of Corollary 1, justify the inclusion of initial sets along this characterisation – e. g., by pointing to the conflicts that had to be solved –, and arrive step by step at the argument in question.

A recent paper that addresses a similar topic as we do is [10]. There, Baumann and Ulbricht introduce explanation schemes as a way to explain the construction of extensions wrt. complete, admissible, and strongly admissible semantics. Let us consider the case of complete semantics. Given $\mathsf{AF}=\mathrm{(}\mathsf{A}\mathrm{,}\mathsf{R}\mathrm{)}$ , the construction follows basically three steps:4

⁴

Although an abbreviated two-step procedure is also discussed.

(1) Determine the grounded extension ${\mathit{E}}_0$ of $\mathsf{AF}$ , (2) select a conflict-free set ${\mathit{E}}_1$ from the set of arguments appearing in some even-length cycle in the reduct ${\mathsf{AF}}^{{\mathit{E}}_0}$ , and (3) determine the grounded extension ${\mathit{E}}_2$ of the reduct ${\mathsf{AF}}^{{\mathit{E}}_0\cup {\mathit{E}}_1}$ . If $\mathit{E}={\mathit{E}}_0\cup {\mathit{E}}_1\cup {\mathit{E}}_2$ defends ${\mathit{E}}_1$ then E is a complete extension (and every complete extension can be decomposed in such a way). The overall construction is similar to our approach, in particular, it consists of a series of steps where we select a set of arguments and move to the reduct of the framework wrt. the arguments accumulated so far. However, our approach provides a more fine-grained way to construct extensions. In each step, we solve a single issue by selecting a single initial set. Step 2 of Baumann and Ulbricht’s approach possibly solves a series of different conflicts all at once. This may actually diffuse the goal to provide an explanation why a certain extension is constructed as it is, as a selection of a conflict-free set of arguments from all even cycles may not clearly show, which conflicts are actually resolved. Furthermore, we do not need to explicitly use the notion of grounded semantics (and the general possibility to include defended arguments) in our construction, as it arises naturally through selecting (unattacked) initial sets and moving to the reduct immediately.

As a by-product of our work, we introduced a new principle [37] for abstract argumentation semantics: serialisability. For future work, we aim at investigated relationships of this new principle to other existing principles listed in [37]. Another avenue for future work to investigate whether our characterisations of admissibility-based semantics can be exploited for algorithmic purposes [14]. It is clear, that there is no obvious advantage in terms of computational complexity by computing (for example) a preferred extension via our transition system as it involves the computation of initial sets at each step (which is an intractable problem as ${\mathit{\text{Exists}}}_{\mathsf{\text{IS}}}$ is already NP-complete). However, our characterisation of initial sets through strongly connected components (see Section 3) could be exploited to devise a parallel algorithm – see also [15] –, as initial sets can be calculated independently of each other in each strongly connected component.