Attack semantics and collective attacks revisited

Abstract

In the current paper we re-examine the concepts of attack semantics and collective attacks in abstract argumentation, and examine how these concepts interact with each other. For this, we systematically map the space of possibilities. Starting with standard argumentation frameworks (which consist of a directed graph with nodes and arrows) we briefly state both node semantics and arrow semantics (the latter a.k.a. attack semantics) in both their extensions-based form and labellings-based form. We then proceed with SETAFs (which consist of a directed hypergraph of nodes and arrows, to take into account the notion of collective attacks) and state both node semantics and arrow semantics, in both their extensions-based and labellings-based form. We then show equivalence between the extensions-based and labellings-based form, for node semantics and arrow semantics of AFs, as well as for node semantics and arrow semantics of SETAFs. Moreover, we show equivalence between node semantics and arrow semantics for AFs, and equivalence between node semantics and arrow semantics for SETAFs (with the notable exception of semi-stable). We also provide a novel way of converting a SETAF to an AF such that semantics are preserved, without the use of any “meta arguments”.

Although the main part of our work is on the level of abstract argumentation, we do provide an application of our theory on the instantiated level. More specifically, we show that the classical characterisation of Assumption-Based Argumentation (ABA) can be seen as an instantiation based on a SETAF, whereas the contemporary characterisation of ABA can be seen as an instantiation based on a standard AF. Our theory of how to convert a SETAF to an AF can then be used to account for both the similarities and the differences between the classical and contemporary characterisations of ABA. Most prominently, our theory is able to explain the semantic mismatch for semi-stable semantics that arises in the ABA instantiation process.

Keywords

Abstract argumentation assumption-based argumentation attack semantics collective attacks

1. .Introduction

The 1990s saw some of the foundational work in argumentation theory. This includes the work of Simari and Loui [48] that later evolved into Defeasible Logic Programming (DeLP) [37] as well as the ground-breaking work of Vreeswijk [53] whose way of constructing arguments has subsequently been applied in the various versions of the ASPIC formalism [13,40,41,44]. Two approaches, however, stand out for their ability to model a wide range of existing formalisms for non-monotonic inference. First of all, there is the abstract argumentation approach of Dung [20], which is shown to be able to model formalisms such as Default Logic, logic programming under stable and well-founded model semantics [20], as well as Nute’s Defeasible Logic [38] and logic programming under 3-valued stable model semantics [54] and regular semantics [16]. Secondly, there is the assumption-based argumentation (ABA) approach of Bondarenko, Dung, Kowalski and Toni [10], which is shown to model formalisms like Default Logic, logic programming under stable model semantics, auto epistemic logic and circumscription [10].

One of the essential differences between these two approaches is that abstract argumentation is argument-based. The idea is to use the information in the knowledge base to construct arguments and to examine how these arguments attack each other. Semantics are then defined on the resulting argumentation framework (AF), i.e., the directed graph in which the nodes represent arguments and the arrows represent the attack relation. In assumption-based argumentation, on the other hand, semantics are defined on sets of assumptions that attack each other based on their possible inferences.

To some extent, assumption-based argumentation can be regarded as applying a directed hypergraph of which the nodes contain assumptions and the arrows coincide with ABA-arguments that each attack an assumption. This is different from the ABA-AA instantiation [21], which applies a normal (binary) graph of which the nodes (not the arrows) contain ABA-arguments. In the current work, we investigate this hypergraph on the abstract level and refer to it as a SETAF. The hyperedges of such a SETAF can be interpreted as collective attacks, which have first been investigated by Nielsen and Parsons [42].

Even though SETAFs extend the limits of AFs by allowing for collective attacks, it has been shown that many semantics properties and principles still apply in this more general setting [8,27,32,35]. This holds even though SETAFs are more expressive than AFs [24]. Recent work examines the computational complexity of reasoning and the underlying hypergraph structure of SETAFs [26,28–30]. We will use the theory developed in this paper to show the semantic correspondence between ABA and its SETAF instantiation.

One particular claim in the literature is that assumption-based argumentation and abstract argumentation are equivalent to some extent [21,49]. That is, the outcome (in terms of conclusions) of assumption-based argumentation would be the same as the outcome of its abstract argumentation interpretation (the ABA-AA instantiation of [21]). In the current paper, we re-examine this claim, by carefully analysing what happens on the abstract level. After all, if a SETAF is an abstraction of ABA, and an AF is an abstraction of the ABA-AA instantiation, then examining equivalence between ABA and the ABA-AA instantiation boils down to examining equivalence between SETAFs and AFs.

To carry out our inquiry, we need to borrow a number of concepts from the argumentation literature. The first concept is that of SETAF labellings [35]. Through our theory it becomes clear that these essentially coincide with the assumption labellings of [47]. The second concept is that of attack-semantics [52], which turns out to play an important role in the conversion process from SETAFs to AFs.

We want to highlight that our approach differs from existing conversions from SETAFs to AFs [35,43]. These approaches can be seen as an instance of flattening [9], i.e., the additional meaning of collective attacks is modelled by the introduction of additional arguments to the “flat” AF. The semantics then coincide under projection. However, in our approach the original SETAF is turned “inside-out”, i.e., we construct an AF where the arguments correspond to the attacks of the SETAFs. We then show the semantic correspondence via attack semantics.

In our current work, we systematically fill the gaps in the space of collective attacks and attack semantics via extensions and labellings. This orthogonal approach is summarised in Fig. 1. Using the thus developed theory, connecting SETAFs and AFs, we then re-examine the often claimed equivalence between assumption-based argumentation and abstract argumentation. We find that some of the already observed equivalences (under complete [17], preferred [17], stable [49] and grounded semantics [22]) are special cases of our theory. In addition, for a particular non-equivalence (under semi-stable semantics [17]) our theory is able to explain why assumption-based argumentation is not equivalent to the ABA-AA instantiation. As we will see, this is due to the fact that on the abstract level the translation process from SETAFs to AFs does not preserve equivalence under semi-stable semantics.

The remaining part of this paper is structured as follows. First, in Section 2 (Argumentation Frameworks and their Semantics) we briefly summarise some key concepts from the formal argumentation literature, including that of an AF, extension-based semantics, labelling-based semantics, and the notion of attack-semantics. Then, in Section 3 (SETAFs and their Semantics) we recall the concept of SETAFs and how the semantics generalise to this setting. We then broaden the notion of attack-semantics to operate on SETAFs. The results of Section 2 and 3 form the theoretical underpinning of our theory; the obtained relationships between the semantics are summarised in Fig. 1. In Section 4 (Relating SETAFs to AFs) we provide a translation procedure to convert SETAFs into AFs, based on the concept of attack-semantics. In Section 5 (Instantiating AFs and SETAFs using ABA) we examine the consequences of the thus obtained theory on AFs and SETAFs in the specific context of ABA, and what this means for the perceived equivalence between ABA and AA.¹ We round off with a discussion in Section 6.

Fig. 1.

Illustration of the contents of Section 2 and Section 3. The contributions of this paper are highlighted in red colour.

In order to improve readability, we have moved the proofs to the appendices of the paper. A reader who is only interested in our main findings could decide only to read Section 1 to Section 6.

2. .Argumentation frameworks and their semantics

In the current section, we provide a summary of some of the existing theory in formal argumentation that we will build on. We start with the concept of an argumentation framework, which is essentially a graph consisting of nodes (N) and arrows ( $a r r$ ). For current purposes, we restrict ourselves to finite argumentation frameworks.

Definition 1.
An argumentation framework is a pair $(N, a r r)$ where N is a finite set of nodes (called arguments) whose internal structure can be left implicit, and $a r r \subseteq N \times N$ .

We will commonly refer to the elements of $a r r$ as the arrows of the argumentation framework. We say that $A \in N$ attacks $B \in N$ iff $(A, B) \in a r r$ . Semantics of argumentation frameworks can be defined in terms of the nodes [20] and in terms of the arrows [52]. We will now discuss each of these approaches.
2.1. .Node semantics for AFs

Semantics for argumentation frameworks were originally defined in terms of its nodes [20].

Definition 2.
Let $(N, a r r)$ be an argumentation framework, $M \subseteq N$ and $B \in N$ . We say that M attacks B iff $\exists A \in M : (A, B) \in a r r$ . We say that $M_{1} \subseteq N$ attacks $M_{2} \subseteq N$ iff $M_{1}$ attacks some $B \in M_{2}$ . We define $M^{+}$ as ${A \in N | M$ attacks $A}$ . We say that M is conflict-free iff $M \cap M^{+} = \emptyset$ . We say that M defends A iff each $B \subseteq N$ that attacks A is attacked by M. We define the function $F : 2^{N} \to 2^{N}$ as follows: $F (M) = {A \in N | A$ is defended by $M}$ .
Definition 3.
Let $(N, a r r)$ be an argumentation framework. A set of nodes $M \subseteq N$ is called: (1)
an admissible set iff M is conflict-free and $M \subseteq F (M)$
(2)
a complete extension iff M is conflict-free and $M = F (M)$
(3)
a grounded extension iff M is minimal (w.r.t. ⊆) among all complete extensions
(4)
a preferred extension iff M is a maximal (w.r.t. ⊆) complete extension
(5)
a semi-stable extension iff M is a complete extension where $M \cup M^{+}$ is maximal (w.r.t. ⊆) among all complete extensions
(6)
a stable extension iff M is a complete extension with $M \cup M^{+} = N$

Although Definition 3 defines the common node semantics in a slightly different way than for instance in [20], equivalence can be observed [11].

An alternative way of defining node semantics is by applying labellings, as is done in the following definition based on [11,14].
Definition 4.
Let $(N, a r r)$ be an argumentation framework. A node labelling is a function $N L a b : N \to {i n, o u t, u n d e c}$ . A node labelling $N L a b$ is called admissible iff for each $A \in N$ :
if $N L a b (A) = i n$ then for each $B \in N$ such that $(B, A) \in a r r$ it holds that $N L a b (B) = o u t$

if $N L a b (A) = o u t$ then there exists a $B \in N$ such that $(B, A) \in a r r$ and $N L a b (B) = i n$
A node labelling $N L a b$ is called complete iff it is admissible and also satisfies for each $A \in N$ :
if $N L a b (A) = u n d e c$ then not for each $B \in N$ such that $(B, A) \in a r r$ it holds that $N L a b (B) = o u t$ , and there does not exists a $B \in N$ such that $(B, A) \in a r r$ and $N L a b (B) = i n$
As a convention, we write $i n (N L a b)$ for ${A \in N | N L a b (A) = i n}$ , $o u t (N L a b)$ for ${A \in N | N L a b (A) = o u t}$ and $u n d e c (N L a b)$ for ${A \in N | N L a b (A) = u n d e c}$ . A complete node labelling $N L a b$ is called: (1)
grounded iff $i n (N L a b)$ is minimal (w.r.t. ⊆) among all complete node labellings
(2)
preferred iff $i n (N L a b)$ is maximal (w.r.t. ⊆) among all complete node labellings
(3)
semi-stable iff $u n d e c (N L a b)$ is minimal (w.r.t. ⊆) among all complete node labellings
(4)
stable iff $u n d e c (N L a b) = \emptyset$

As a node labelling essentially defines a partition, we sometimes write it as a triple $(i n (N L a b)$ , $o u t (N L a b)$ , $u n d e c (N L a b))$ .

It has been shown that the complete node labellings with maximal $i n$ are equal to the complete node labellings with maximal $o u t$ [14], and that the complete node labelling where $i n$ is minimal is unique and equal to both the complete node labelling where $o u t$ is minimal and the complete node labelling where $u n d e c$ is maximal [14]. This means that the grounded, preferred and semi-stable node labellings cover all possibilities regarding the minimisation and maximisation of a particular label (among the complete node labellings). This is summarised in Table 1.

Table 1
Implementing different conditions on complete node labellings of argumentation frameworks.

Condition on node labelling Resulting semantics

maximal $i n$ preferred

maximal $o u t$ preferred

maximal $u n d e c$ grounded

minimal $i n$ grounded

minimal $o u t$ grounded

minimal $u n d e c$ semi-stable

no $u n d e c$ stable

As was pointed out in [14], for the semantics we consider labellings and extensions are one-to-one related through the functions $N L a b 2 A r g s$ and $A r g s 2 N L a b$ , where
$\begin{aligned} N l a b 2 A r g s (N L a b) = i n (N L a b), and \\ A r g s 2 n L a b (M) = (M, M^{+}, N ∖ (M \cup M^{+}))^{2} . \end{aligned}$

That is, if $N L a b$ is a complete (resp. grounded, preferred, semi-stable or stable) node labelling, then $N L a b 2 A r g s (N L a b)$ is a complete (resp. grounded, preferred, semi-stable or stable) extension, and if M is a complete (resp. grounded, preferred, semi-stable or stable) extension, then $A r g s 2 N L a b (M)$ is a complete (resp. grounded, preferred, semi-stable or stable) node labelling [14]. Moreover, under complete semantics (as well as under grounded, preferred, semi-stable and stable semantics) $N L a b 2 A r g s$ and $A r g s 2 N L a b$ are bijective functions and each other’s inverses [14]. Table 2 provides an overview of the results.

Table 2
The relation between node extensions and node labellings of argumentation frameworks, through $A r g s 2 N L a b$ and $N L a b 2 A r g s$ .

Node extension Relation Node labelling

complete extension ⇔ complete labelling

grounded extension ⇔ grounded labelling

preferred extension ⇔ preferred labelling

semi-stable extension ⇔ semi-stable labelling

stable extension ⇔ stable labelling

2.2. .Arrow semantics for AFs

Condition on node labelling	Resulting semantics
maximal $i n$	preferred
maximal $o u t$	preferred
maximal $u n d e c$	grounded
minimal $i n$	grounded
minimal $o u t$	grounded
minimal $u n d e c$	semi-stable
no $u n d e c$	stable

Node extension	Relation	Node labelling
complete extension	⇔	complete labelling
grounded extension	⇔	grounded labelling
preferred extension	⇔	preferred labelling
semi-stable extension	⇔	semi-stable labelling
stable extension	⇔	stable labelling

As an alternative to defining semantics based on the nodes of an argumentation framework, it is also possible to define semantics based on the arrows of the argumentation framework. This idea of “attack semantics” was first introduced in [52] – however, these semantics have not yet been defined in terms of extensions, as we introduce them in Definition 5.

Definition 5.
Let $(N, a r r)$ be an argumentation framework, $a \subseteq a r r$ and $(A, B) \in a r r$ . We say that a attacks $(A, B)$ iff $(C, A) \in a$ for some $C \in N$ . We say that $a_{1} \subseteq a r r$ attacks $a_{2} \subseteq a r r$ iff $a_{1}$ attacks some element of $a_{2}$ . We define $a^{+}$ as ${(C, D) \in a r r | a$ attacks $(C, D)}$ . We say that a is conflict-free iff $a \cap a^{+} = \emptyset$ . We say that a defends $(A, B)$ iff each $(C, A) \in a r r$ is attacked by a. We define the function $F : 2^{a r r} \to 2^{a r r}$ as follows: $F (a) = {(A, B) \in a r r | (A, B)$ is defended by $a}$ .
Definition 6.
Let $(N, a r r)$ be an argumentation framework. $a \subseteq a r r$ is called: (1)
an admissible set iff a is conflict-free and $a \subseteq F (a)$
(2)
a complete extension iff a is conflict-free and $a = F (a)$
(3)
a grounded extension iff a is minimal (w.r.t. ⊆) among all complete extensions
(4)
a preferred extension iff a is a maximal (w.r.t. ⊆) complete extension
(5)
a semi-stable extension iff a is a complete extension where $a \cup a^{+}$ is maximal (w.r.t. ⊆) among all complete extensions
(6)
a stable extension iff a is a complete extension with $a \cup a^{+} = a r r$

An alternative way of defining arrow semantics is by applying labellings, as is done in the following definition.3
Definition 7.
Let $(N, a r r)$ be an argumentation framework. An arrow labelling is a function $A L a b : a r r \to {i n, o u t, u n d e c}$ . An arrow labelling $A L a b$ is called admissible iff for each $(A, B) \in a r r$ :
if $A L a b ((A, B)) = i n$ then for each $(C, A) \in a r r$ it holds that $A L a b ((C, A)) = o u t$

if $A L a b ((A, B)) = o u t$ then there exists a $(C, A) \in a r r$ such that $A L a b ((C, A)) = i n$
An arrow labelling $A L a b$ is called complete iff it is admissible and also satisfies for each $(A, B) \in a r r$ :
if $A L a b ((A, B)) = u n d e c$ then not for each $(C, A) \in a r r$ it holds that $A L a b ((C, A)) = o u t$ , and there does not exist a $(C, A) \in a r r$ such that $A L a b ((C, A)) = i n$
As a convention, we write $i n (A L a b)$ for ${(A, B) \in a r r | A L a b ((A, B)) = i n}$ , $o u t (A L a b)$ for ${(A, B) \in a r r | A L a b ((A, B)) = o u t}$ and $u n d e c (A L a b)$ for ${(A, B) \in a r r | A L a b ((A, B)) = u n d e c}$ . A complete arrow labelling $A L a b$ is called: (1)
grounded iff $i n (A L a b)$ is minimal (w.r.t. ⊆) among all complete arrow labellings
(2)
preferred iff $i n (A L a b)$ is maximal (w.r.t. ⊆) among all complete arrow labellings
(3)
semi-stable iff $u n d e c (A L a b)$ is minimal (w.r.t. ⊆) among all complete arrow labellings
(4)
stable iff $u n d e c (A L a b) = \emptyset$

As an arrow labelling essentially defines a partition, we sometimes write it as a triple $(i n (A L a b)$ , $o u t (A L a b)$ , $u n d e c (A L a b))$ .

It can be shown that the complete arrow labellings with maximal $i n$ are equal to the complete arrow labellings with maximal $o u t$ (Appendix A) and that the complete arrow labelling where $i n$ is minimal is unique and equal to both the complete arrow labelling where $o u t$ is minimal and the complete arrow labelling where $u n d e c$ is maximal (Appendix A). This means that the grounded, preferred and semi-stable arrow labellings cover all possibilities regarding the minimisation and maximisation of a particular label (among the complete arrow labellings). This is summarised in Table 3.

Table 3
Implementing different conditions on complete arrow labellings of argumentation frameworks.

Condition on arrow labelling Resulting semantics

maximal $i n$ preferred

maximal $o u t$ preferred

maximal $u n d e c$ grounded

minimal $i n$ grounded

minimal $o u t$ grounded

minimal $u n d e c$ semi-stable

no $u n d e c$ stable

It can be shown that arrow extensions and arrow labellings are one-to-one related through the functions $A L a b 2 a$ and $a 2 A L a b$ , where
$\begin{aligned} A l a b 2 a (A L a b) = i n (A L a b), and \\ a 2 A L a b (a) = (a, a^{+} a a r, ∖ (a \cup a^{+}))^{4} . \end{aligned}$

If $A L a b$ is a complete (resp. grounded, preferred, semi-stable or stable) arrow labelling, then $A L a b 2 a (A L a b)$ is a complete (resp. grounded, preferred, semi-stable or stable) arrow extension, and if a is a complete (resp. grounded, preferred, semi-stable or stable) arrow extension then $a 2 A L a b (a)$ is a complete (resp. grounded, preferred, semi-stable or stable) arrow labelling. Moreover, under complete semantics (as well as under grounded, preferred, semi-stable and stable semantics) $A L a b 2 a$ and $a 2 A L a b$ are bijective functions that are each other’s inverses. Details and proofs can be found in Appendix H. Table 4 provides an overview of the results.

Table 4
The relation between arrow extensions and arrow labellings of argumentation frameworks, through $a 2 A L a b$ and $A L a b 2 a$ .

Arrow extension Relation Arrow labelling

complete extension ⇔ complete labelling

grounded extension ⇔ grounded labelling

preferred extension ⇔ preferred labelling

semi-stable extension ⇔ semi-stable labelling

stable extension ⇔ stable labelling

2.3. .On the equivalence between node semantics and arrow semantics for AFs

Condition on arrow labelling	Resulting semantics
maximal $i n$	preferred
maximal $o u t$	preferred
maximal $u n d e c$	grounded
minimal $i n$	grounded
minimal $o u t$	grounded
minimal $u n d e c$	semi-stable
no $u n d e c$	stable

Arrow extension	Relation	Arrow labelling
complete extension	⇔	complete labelling
grounded extension	⇔	grounded labelling
preferred extension	⇔	preferred labelling
semi-stable extension	⇔	semi-stable labelling
stable extension	⇔	stable labelling

It turns out that arrow labellings and node labellings are one-to-one related through the functions $A L a b 2 N L a b$ and $N L a b 2 A L a b$ , where

\begin{aligned} A L a b 2 N L a b (A L a b) & = ({A \in N | \forall (B, A) \in a r r : A L a b ((B, A)) = o u t}, \\ {A \in N | \exists (B, A) \in a r r : A L a b ((B, A)) = i n}, \\ {A \in N | \neg \forall (B, A) \in a r r : A L a b ((B, A)) = o u t and \\ \neg \exists (B, A) \in a r r : A L a b ((B, A)) = i n}), \\ N L a b 2 A L a b (N L a b) & = ({(A, B) \in a r r | N L a b (A) = i n}, \\ {(A, B) \in a r r | N L a b (A) = o u t}, \\ {(A, B) \in a r r | N L a b (A) = undec}) . \end{aligned}

It can be shown that if $A L a b$ is a complete (resp. grounded, preferred or stable) arrow labelling, then $A L a b 2 N L a b$ is a complete (resp. grounded, preferred or stable) node labelling, and if $N L a b$ is a complete (resp. grounded, preferred, semi-stable or stable) node labelling, then $N L a b 2 A L a b (N L a b)$ is a complete (resp. grounded, preferred, semi-stable or stable) arrow labelling (see Appendix B for proofs). Moreover, under complete semantics (as well as under grounded, preferred and stable semantics) $A L a b 2 N L a b$ and $N L a b 2 A L a b$ are bijective functions and each other’s inverses (see Appendix B for proofs). Table 5 and Theorem 8, respectively, provide an overview of these results.

Table 5
The relation between node labellings and arrow labellings of argumentation frameworks, through $N L a b 2 A L a b$ and $A L a b 2 N L a b$ .

Node labelling Relation Arrow labelling

complete node labelling ⇔ complete arrow labelling

grounded node labelling ⇔ grounded arrow labelling

preferred node labelling ⇔ preferred arrow labelling

semi-stable node labelling ⇔ semi-stable arrow labelling

stable node labelling ⇔ stable arrow labelling

Node labelling	Relation	Arrow labelling
complete node labelling	⇔	complete arrow labelling
grounded node labelling	⇔	grounded arrow labelling
preferred node labelling	⇔	preferred arrow labelling
semi-stable node labelling	⇔	semi-stable arrow labelling
stable node labelling	⇔	stable arrow labelling

Theorem 8.

Let $A F = (N, a r r)$ be an argumentation framework and let $N L a b$ and $A L a b$ be a node labelling and an arrow labelling of $A F$ , respectively. It holds that: (1)

If $N L a b$ is a complete node labelling, then $N L a b 2 A L a b (N L a b)$ is a complete arrow labelling.

If $A L a b$ is a complete arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a complete node labelling.

(2)

When restricted to complete node labellings and complete arrow labellings, the functions $A L a b 2 N L a b$ and $N L a b 2 A L a b$ become bijections and each other’s inverses.

(3)

If $N L a b$ is a grounded node labelling, then $N L a b 2 A L a b (N L a b)$ is a grounded arrow labelling.

If $A L a b$ is a grounded arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a grounded node labelling.

(4)

If $N L a b$ is a preferred node labelling, then $N L a b 2 A L a b (N L a b)$ is a preferred arrow labelling.

If $A L a b$ is a preferred arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a preferred node labelling.

(5)

If $N L a b$ is a stable node labelling, then $N L a b 2 A L a b (N L a b)$ is a stable arrow labelling.

If $A L a b$ is a stable arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a stable node labelling.

Note that this implication does not hold for semi-stable semantics (in neither direction), as the following counter-examples illustrate. Intuitively, the problem are nodes that have no outgoing arrows, which means in arrow semantics we cannot distinguish the cases $o u t$ and $u n d e c$ .

Example 9.

Let $A F = (N, a r r)$ be an argumentation framework with $N = {A, B, C, D}$ and $a r r = {(A, A), (A, C), (B, D), (D, B), (D, C)}$ .

$A F$ has three complete node labellings:

\begin{aligned} N L a b_{1} = (\emptyset, \emptyset {A, B, C, D}) \\ N L a b_{2} = ({B}, {D}, {A, C}) \\ N L a b_{3} = ({D}, {B, C}, {A}) \end{aligned}

and three complete arrow labellings:

\begin{aligned} {A L a b}_{1} = (\emptyset, \emptyset, {(A, A), (A, C), (B, D), (D, B), (D, C)}) \\ {A L a b}_{2} = ({(B, D)}, {(D, B), (D, C)}, {(A, A), (A, C)}) \\ {A L a b}_{3} = ({(D, B), (D, C)}, {(B, D)}, {(A, A), (A, C)}) \end{aligned}

These node labellings and arrow labellings correspond to each other through the functions

N L a b 2 A L a b

and

A L a b 2 N L a b

. While

{A L a b}_{2}

is a semi-stable arrow labelling,

{N L a b}_{2} = A L a b 2 N L a b ({A L a b}_{2})

is not a semi-stable node labelling (the only semi-stable node labelling is

{N L a b}_{3}

Example 10.

Let $A F = (N, a r r)$ be an argumentation framework with $N = {A, B, C, D, E, F}$ and $a r r = {(A, B), (C, B), (C, C), (A, D), (D, A), (D, E), (E, E), (E, F)}$ .

$A F$ has three complete node labellings:

\begin{aligned} N L a b_{1} = (\emptyset, \emptyset {A, B, C, D, E, F}) \\ N L a b_{2} = ({A}, {B, D}, {C, E, F}) \\ N L a b_{3} = ({D, F}, {A, E}, {B, C}) \end{aligned}

and three complete arrow labellings:

\begin{aligned} N L a b_{1} = (\emptyset, \emptyset {(A, B), (C, B), (C, C), (A, D), (D, A), (D, E), (E, E), (E, F),}) \\ N L a b_{2} = ({(A, B), (A, D)}, {(D, A), (D, E)}, {(C, B), (C, C), (E, E), (E, F)}) \\ N L a b_{3} = ({(D, A), (D, E)}, {(A, B), (A, D), (E, E), (E, F)}, {(C, B), (C, C)}) \end{aligned}

These node labellings and arrow labellings correspond to each other through the functions $N L a b 2 A L a b$ and $A L a b 2 N L a b$ . While ${N L a b}_{2}$ is a semi-stable node labelling, ${A L a b}_{2} = N L a b 2 A L a b ({N L a b}_{2})$ is not a semi-stable arrow labelling (the only semi-stable arrow labelling is ${A L a b}_{3}$ ).

Node extensions and arrow extensions are one-to-one related via the functions

\begin{aligned} A r g s 2 a = A L a b 2 a \circ N L a b 2 A L a b \circ A r g s 2 N L a b, and \\ a 2 A r g s = A r g s 2 N L a b \circ A L a b 2 N L a b \circ A L a b 2 a . \end{aligned}

Table 6 provides an overview (see Appendix I for proofs).

Table 6

The relation between node extensions and arrow extensions of argumentation frameworks.

Node extension	Relation	Arrow extension
complete node extension	⇔	complete arrow extension
grounded node extension	⇔	grounded arrow extension
preferred node extension	⇔	preferred arrow extension
semi-stable node extension		semi-stable arrow extension
stable node extension	⇔	stable arrow extension

3. .SETAFs and their semantics

Apart from defining argumentation semantics based on a normal (binary) directed graph, one can also define argumentation semantics that take collective attacks into account. The idea is that instead of one node attacking another node, there is a set of nodes attacking another node. We note that these frameworks are a special case of directed hypergraphs where the target element is a singleton. For current purposes, we restrict ourselves to hypergraphs that are finite.

Definition 11.
An argumentation framework with set attacks (SETAF) is a tuple $S F = (N, a r r)$ where $N$ is a finite set of nodes, whose structure can be left implicit, and $a r r \subseteq 2^{N} \times N$ .

As for AFs, we refer to the elements of $N$ as the nodes and to the elements of $a r r$ as the arrows of the SETAF. Moreover, we say $M$ attacks A iff $(M, A) \in a r r$ . Consider the following example for an illustration.
Example 12.
Consider the following SETAF $S F = (N, a r r)$ with
$\begin{aligned} N = {A, B, C, D, E, F}, \\ a r r = {(\emptyset, A), ({A}, B), ({B, C}, E), ({C, F}, E), ({C}, F), ({D}, B), ({E}, D), ({F}, C)} . \end{aligned}$

Remark 13.
Originally, set attacks have been introduced without allowing for the empty set attacking an argument [42]: an argumentation framework with collective attacks is a pair $(N, a r r)$ where $N$ is a finite set of nodes and $a r r \subseteq (2^{N} ∖ \emptyset) \times N$ . Hence each AF with collective attacks is a SETAF but not vice versa. However, the difference can be neglected, as we show in Appendix G: given a SETAF $S F = (N, a r r)$ , if we simply delete all nodes $A \in N$ with $(\emptyset, A) \in a r r$ and all arrows $(M, B)$ where either $A \in M$ or $B = A$ , we obtain an AF with collective attacks that is equivalent (w.r.t. all semantics under consideration) to our original SETAF $S F$ .
Remark 14.
Note that (with a slight abuse of notation) every AF can be seen as a SETAF (cf. [42]): let $A F = (N, a r r)$ be an AF, the corresponding SETAF ${S F}_{A F}$ is defined as ${S F}_{A F} = (N, {({A}, B) | (A, B) \in a r r})$ . Both the node semantics and arrow semantics (see next sections) coincide in this case.

Just as is the case for AFs, semantics of SETAFs can be defined in terms of nodes [35,42] and in terms of arrows (which is a novel contribution of this paper). We will now discuss each of these approaches.
3.1. .Node semantics for SETAFs

Semantics for SETAFs were originally defined in terms of its nodes [42].

Definition 15.
Let $S F = (N, a r r)$ be a SETAF, $M \subseteq N$ and $A \in N$ . We say that $M$ attacks A iff $\exists M^{'} \subseteq M : (M^{'}, A) \in a r r$ . We say that $M_{1} \subseteq N$ attacks $M_{2} \subseteq N$ iff $M_{1}$ attacks some $B \in M_{2}$ . We define $M_{S F}^{+}$ as ${A \in N | M$ attacks $A}$ . We say that $M$ is conflict-free iff $M \cap M_{S F}^{+} = \emptyset$ . We write $c f (S F) = {M h \subseteq N | M \cap M_{S F}^{+} = \emptyset}$ to denote the set of conflict-free sets. We say that $M$ defends A iff for each $M^{'} \subseteq N$ that attacks A, $M$ attacks $M^{'}$ . We define the characteristic function $F_{S F} : 2^{N} \to 2^{N}$ with $F_{S F} (M) = {A \in N | A$ is defended by $M}$ . We omit subscript $S F$ if it is clear from the context.
Definition 16 [35,42]

Let $(N, a r r)$ be a SETAF. $M \subseteq N$ is called:

(1)
an admissible set iff $M$ is conflict-free and $M \subseteq F (M)$
(2)
a complete extension iff $M$ is conflict-free and $M = F (M)$
(3)
a grounded extension iff $M$ is minimal (w.r.t. ⊆) among all complete extensions
(4)
a preferred extension iff $M$ is a maximal (w.r.t. ⊆) complete extension
(5)
a semi-stable extension iff $M$ is a complete extension where $M \cup M^{+}$ is maximal (w.r.t. ⊆) among all complete extensions
(6)
a stable extension iff $M$ is a complete extension where $M \cup M^{+} = N$

If one interprets an arrow $(M, A)$ as a collective attack [42] from $M$ to A, then the semantics of Definition 16 coincide with those defined in [42] (minus semi-stable, which is missing in [42] but has been considered in later work, e.g., in [35]). In contrast to the original definitions, we have decided to follow the approach from [35] and use complete semantics as the basis for defining preferred, semi-stable, grounded, and stable semantics. It holds that the grounded extension is unique, and that there always exists at least one preferred and at least one semi-stable extension.

An alternative way of defining SETAF semantics is by applying node labellings as done in [35].
Definition 17 [35]

Let $(N, a r r)$ be a SETAF. A SETAF node labelling is a function $N L a b : N \to {i n, o u t, u n d e c}$ . A SETAF node labelling $N L a b$ is called admissible iff for each $A \in N$ :

if $N L a b (A) = i n$ then for each $M \subseteq N$ such that $(M, A) \in a r r$ it holds that $\exists B \in M : N L a b (B) = o u t$

if $N L a b (A) = o u t$ then there exists an $M \subseteq N$ such that $(M, A) \in a r r$ and $\forall B \in M : N L a b (B) = i n$

A SETAF node labelling

N L a b

is called complete iff it is admissible and also satisfies for each

A \in N

if $N L a b (A) = u n d e c$ then not for each $M \subseteq N$ such that $(M, A) \in a r r$ it holds that $\exists B \in M : N L a b (B) = o u t$ and there does not exist an $M \subseteq N$ such that $(M, A) \in a r r$ and $\forall B \in M : N L a b (B) = i n$

As a convention, we write

i n (N L a b)

for

{A \in N | N L a b (A) = i n}

o u t (N L a b)

for

{A \in N | N L a b (A) = o u t}

and

u n d e c (N L a b)

for

{A \in N | N L a b (A) = u n d e c}

. A complete SETAF node labelling

N L a b

is called:

(1)
grounded iff $i n (N L a b)$ is minimal (w.r.t. ⊆) among all complete SETAF node labellings
(2)
preferred iff $i n (N L a b)$ is maximal (w.r.t. ⊆) among all complete SETAF node labellings
(3)
semi-stable iff $u n d e c (N L a b)$ is minimal (w.r.t. ⊆) among all complete SETAF node labellings
(4)
stable iff $u n d e c (N L a b) = \emptyset$

As a SETAF node labelling essentially defines a partition, we sometimes write it as a triple $(i n (N L a b)$ , $o u t (N L a b)$ , $u n d e c (N L a b))$ .

It can been shown that the complete SETAF node labellings with maximal $i n$ are equal to the complete SETAF node labellings with maximal $o u t$ (see Appendix D) and that the complete SETAF node labelling where $i n$ is minimal is unique and equal to both the complete SETAF node labelling where $o u t$ is minimal and the complete SETAF node labelling where $u n d e c$ is maximal (See Appendix D). This means that the grounded, preferred and semi-stable SETAF node labellings cover all possibilities regarding the minimisation and maximisation of a particular label (among the complete SETAF node labellings). This is summarised in Table 7.

Table 7
Implementing different conditions on complete node labellings of SETAFs.

Condition on node labelling Resulting semantics

maximal $i n$ preferred

maximal $o u t$ preferred

maximal $u n d e c$ grounded

minimal $i n$ grounded

minimal $o u t$ grounded

minimal $u n d e c$ semi-stable

no $u n d e c$ stable

As shown in [35, Theorem 5.10, Theorem 5.11], it holds that SETAF node labellings and SETAF extensions are one-to-one related through the functions $N L a b 2 A r g s$ and $A r g s 2 N L a b$ , where
$\begin{aligned} N L a b 2 A r g s (N l a b) = i n (N l a b), and \\ A r g s 2 N L a b (m) = {(M, M^{+}, N ∖ (M \cup M^{+}))}^{5} . \end{aligned}$

If $N L a b$ is a complete (resp. grounded, preferred, semi-stable or stable) SETAF node labelling, then $N L a b 2 A r g s (N L a b)$ is a complete (resp. grounded, preferred, semi-stable or stable) SETAF extension, and if $M$ is a complete (resp. grounded, preferred, semi-stable or stable) SETAF extension, then $A r g s 2 N L a b (M)$ is a complete (resp. grounded, preferred, semi-stable or stable) SETAF node labelling (see Appendix D for proofs). Moreover, under complete semantics (as well as under grounded, preferred, semi-stable and stable semantics) $N L a b 2 A r g s$ and $A r g s 2 N L a b$ are bijective functions and each other’s inverses (see Appendix D for proofs). Table 8 provides an overview of these results.

Table 8
The relation between node extensions and node labellings of SETAFs, through $A r g s 2 N L a b$ and $N L a b 2 A r g s$ .

Node extension Relation Node labelling

complete extension ⇔ complete labelling

grounded extension ⇔ grounded labelling

preferred extension ⇔ preferred labelling

semi-stable extension ⇔ semi-stable labelling

stable extension ⇔ stable labelling

3.2. .Arrow semantics for SETAFs

Condition on node labelling	Resulting semantics
maximal $i n$	preferred
maximal $o u t$	preferred
maximal $u n d e c$	grounded
minimal $i n$	grounded
minimal $o u t$	grounded
minimal $u n d e c$	semi-stable
no $u n d e c$	stable

Node extension	Relation	Node labelling
complete extension	⇔	complete labelling
grounded extension	⇔	grounded labelling
preferred extension	⇔	preferred labelling
semi-stable extension	⇔	semi-stable labelling
stable extension	⇔	stable labelling

As an alternative to defining semantics based on the nodes of a SETAF, it is also possible to define semantics based on the arrows of the SETAF. This can be done using either arrow extensions or arrow labellings. We start with arrow extensions.

Definition 18.
Let $(N, a r r)$ be a SETAF, $a \subseteq a r r$ and $(M, A) \in a r r$ . We say that $a$ attacks $(M, A)$ iff $(M^{'}, B) \in a$ with $B \in M$ for some $M^{'} \subseteq N$ . We say that $a_{1} \subseteq a r r$ attacks $a_{2} \subseteq a r r$ iff $a_{1}$ attacks some element of $a_{2}$ . We define $a^{+}$ as ${(M, A) \in a r r | a$ attacks $(M, A)}$ . We say that $a$ is conflict-free iff $a \cap a^{+} = \emptyset$ . We say that $a$ defends $(M, A)$ iff each $(M^{'}, B) \in a r r$ with $B \in M$ is attacked by $a$ . We define the function $F : 2^{a r r} \to 2^{a r r}$ as follows: $F (a) = {(M, A) \in a r r | (M, A)$ is defended by $a}$ .
Definition 19.
Let $(N, a r r)$ be a SETAF. $a \subseteq a r r$ is called: (1)
an admissible set iff $a$ is conflict-free and $a \subseteq F (a)$
(2)
a complete extension iff $a$ is conflict-free and $a = F (a)$
(3)
a grounded extension iff $a$ is minimal (w.r.t. ⊆) among all complete extensions
(4)
a preferred extension iff $a$ is a maximal (w.r.t. ⊆) complete extension
(5)
a semi-stable extension iff $a$ is a complete extension where $a \cup a^{+}$ is maximal (w.r.t. ⊆) among all complete extensions
(6)
a stable extension iff $a$ is a complete extension with $a \cup a^{+} = a r r$

An alternative way of defining arrow semantics for SETAF is by applying labellings, as is done in the following definition.
Definition 20.
Let $(N, a r r)$ be a SETAF. A SETAF arrow labelling is a function $A L a b : a r r \to {i n, o u t, u n d e c}$ . A SETAF arrow labelling $A L a b$ is called admissible iff for each $(M, A) \in a r r$ :
if $A L a b ((M, A)) = i n$ then for each $(M^{'}, B) \in a r r$ such that $B \in M$ it holds that $A L a b ((M^{'}, B)) = o u t$

if $A L a b ((M, A)) = o u t$ then there exists an $(M^{'}, B) \in a r r$ such that $B \in M$ and $A L a b ((M^{'}, B)) = i n$
A SETAF arrow labelling $A L a b$ is called complete iff it is admissible and satisfies for each $(M, A) \in a r r$ :
if $A L a b ((M, A)) = u n d e c$ then not for each $(M^{'}, B) \in a r r$ such that $B \in M$ it holds that $A L a b ((M^{'}, B)) = o u t$ and there does not exist an $(M^{'}, B) \in a r r$ such that $B \in M$ and $A L a b ((M^{'}, B)) = i n$
As a convention, we write $i n (A L a b)$ for ${(M, A) \in a r r | A L a b ((M, A)) = i n}$ , $o u t (A L a b)$ for ${(M, A) \in a r r | A L a b ((M, A)) = o u t}$ and $u n d e c (A L a b)$ for ${(M, A) \in a r r | A L a b ((M, A)) = u n d e c}$ . A complete SETAF arrow labelling $A L a b$ is called: (1)
grounded iff $i n (A L a b)$ is minimal (w.r.t. ⊆) among all complete SETAF arrow labellings
(2)
preferred iff $i n (A L a b)$ is maximal (w.r.t. ⊆) among all complete SETAF arrow labellings
(3)
semi-stable iff $u n d e c (A L a b)$ is minimal (w.r.t. ⊆) among all complete SETAF arrow labellings
(4)
stable iff $u n d e c (A L a b) = \emptyset$

As a SETAF arrow labelling essentially defines a partition, we sometimes write it as a triple $(i n (A L a b)$ , $o u t (A L a b)$ , $u n d e c (A L a b))$ .

It can be shown that the complete arrow labellings with maximal $i n$ are equal to the complete arrow labellings with maximal $o u t$ (Appendix E) and that the complete arrow labelling where $i n$ is minimal is unique and equal to both the complete arrow labelling where $o u t$ is minimal and the complete arrow labelling where $u n d e c$ is maximal (Appendix E). This means that the grounded, preferred and semi-stable arrow labellings cover all possibilities regarding the minimisation and maximisation of a particular label (among the complete arrow labellings). This is summarised in Table 9.

It can be shown that arrow extensions and arrow labellings are one-to-one related through the functions $A L a b 2 a$ and $a 2 A L a b$ , where
$\begin{aligned} A L a b 2 a (A L a b) = i n (A L a b), \\ a 2 A L a b (a) = (a, a^{+}, a r r ∖ (a \cup a^{+}))^{6} . \end{aligned}$

Table 9
Implementing different conditions on complete arrow labellings of SETAF.

Condition on arrow labelling Resulting semantics

maximal $i n$ preferred

maximal $o u t$ preferred

maximal $u n d e c$ grounded

minimal $i n$ grounded

minimal $o u t$ grounded

minimal $u n d e c$ semi-stable

no $u n d e c$ stable

If $A L a b$ is a complete (resp. grounded, preferred, semi-stable or stable) arrow labelling, then $A L a b 2 a (A L a b)$ is a complete (resp. grounded, preferred, semi-stable or stable) arrow extension, and if $a$ is a complete (resp. grounded, preferred, semi-stable or stable) arrow extension then $a 2 A L a b (a)$ is a complete (resp. grounded, preferred, semi-stable or stable) arrow labelling. Moreover, under complete semantics (as well as under grounded, preferred, semi-stable and stable semantics) $A L a b 2 a$ and $a 2 A L a b$ are bijective functions that are each other’s inverses. Details and proofs can be found in Appendix J. Table 10 provides an overview of the results.

Table 10
The relation between arrow extensions and arrow labellings of SETAF, through $a 2 A L a b$ and $A L a b 2 a$ .

Arrow extension Relation Arrow labelling

complete extension ⇔ complete labelling

grounded extension ⇔ grounded labelling

preferred extension ⇔ preferred labelling

semi-stable extension ⇔ semi-stable labelling

stable extension ⇔ stable labelling

3.3. .On the equivalence of node semantics and arrow semantics for SETAFs

Condition on arrow labelling	Resulting semantics
maximal $i n$	preferred
maximal $o u t$	preferred
maximal $u n d e c$	grounded
minimal $i n$	grounded
minimal $o u t$	grounded
minimal $u n d e c$	semi-stable
no $u n d e c$	stable

Arrow extension	Relation	Arrow labelling
complete extension	⇔	complete labelling
grounded extension	⇔	grounded labelling
preferred extension	⇔	preferred labelling
semi-stable extension	⇔	semi-stable labelling
stable extension	⇔	stable labelling

It can be shown that SETAF arrow labellings and SETAF node labellings are one-to-one related through the functions $A L a b 2 N L a b$ and $N L a b 2 A L a b$ , where

\begin{aligned} A L a b 2 N L a b (A L a b) & = ({A \in N | \forall (M, A) \in a r r : A L a b ((M, A)) = o u t}, \\ {A \in N | \exists (M, A) \in a r r : A L a b ((M, A)) = i n}, \\ {A \in N | \neg \forall (M, A) \in a r r : A L a b ((M, A)) = o u t and \\ \neg \exists (M, A) \in a r r : A L a b ((M, A)) = i n}), \\ A L a b 2 A L a b (N L a b) & = ({(M, A) \in a r r | \forall B \in M : N L a b (B) = i n}, \\ {(M, A) \in a r r | \exists B \in M : N L a b (B) = o u t}, \\ {(M, A) \in a r r | \neg \forall B \in M : N L a b (B) = i n and \\ \neg \exists B \in M : N L a b (B) = o u t}) . \end{aligned}

It can be shown that if $A L a b$ is a complete (resp. grounded, preferred, semi-stable or stable) SETAF arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a complete (resp. grounded, preferred or stable) SETAF node labelling, and if $N L a b$ is a complete (resp. grounded, preferred or stable) node labelling, then $N L a b 2 A L a b (N L a b)$ is a complete (resp. grounded, preferred or stable) arrow labelling (see Appendix F for proofs).

However, the relation between SETAF arrow labellings and SETAF node labellings does not hold under semi-stable semantics (due to Remark 14, the same counter example as in AFs applies, i.e., Example 9 and Example 10). This is despite the fact that, under complete semantics (as well as under grounded, preferred, semi-stable and stable semantics) $A L a b 2 N L a b$ and $N L a b 2 A L a b$ are bijective functions and each other’s inverses (see Appendix F for proofs). Theorem 21 and Table 11, respectively, provide an overview of these results.

Theorem 21.
Let $S F = (N, a r r)$ be a SETAF and let $N L a b$ and $A L a b$ be a node labelling and an arrow labelling of $S F$ , respectively. It holds that: (1)
If $N L a b$ is a complete node labelling, then $N L a b 2 A L a b (N L a b)$ is a complete arrow labelling.

If $A L a b$ is a complete arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a complete node labelling.
(2)
When restricted to complete node labellings and complete arrow labellings, the functions $A L a b 2 N L a b$ and $N L a b 2 A L a b$ become bijections and each other’s inverses.
(3)
If $N L a b$ is a grounded node labelling, then $N L a b 2 A L a b (N L a b)$ is a grounded arrow labelling.

If $A L a b$ is a grounded arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a grounded node labelling.
(4)
If $N L a b$ is a preferred node labelling, then $N L a b 2 A L a b (N L a b)$ is a preferred arrow labelling.

If $A L a b$ is a preferred arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a preferred node labelling.
(5)
If $N L a b$ is a stable node labelling, then $N L a b 2 A L a b (N L a b)$ is a stable arrow labelling.

If $A L a b$ is a stable arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a stable node labelling.

Table 11
The relation between node labellings and arrow labellings of SETAFs, through $N L a b 2 A L a b$ and $A L a b 2 N L a b$ .

Node labelling Relation Arrow labelling

complete node labelling ⇔ complete arrow labelling

grounded node labelling ⇔ grounded arrow labelling

preferred node labelling ⇔ preferred arrow labelling

semi-stable node labelling semi-stable arrow labelling

stable node labelling ⇔ stable arrow labelling

Conflict-free node extensions and arrow extensions are one-to-one related via the functions
$\begin{aligned} A r g s 2 a = A L a b 2 a \circ N L a b 2 A L a b \circ A r g s 2 N L a b, \\ a 2 A r g s = A r g s 2 N L a b \circ A L a b 2 N L a b \circ A L a b 2 a . \end{aligned}$

Table 12 provides an overview (see Appendix K for proofs).

Table 12
The relation between node extensions and arrow extensions of SETAFs.

Node extension Relation Arrow extension

complete node extension ⇔ complete arrow extension

grounded node extension ⇔ grounded arrow extension

preferred node extension ⇔ preferred arrow extension

semi-stable node extension semi-stable arrow extension

stable node extension ⇔ stable arrow extension

4. .Relating SETAFs to AFs

Node labelling	Relation	Arrow labelling
complete node labelling	⇔	complete arrow labelling
grounded node labelling	⇔	grounded arrow labelling
preferred node labelling	⇔	preferred arrow labelling
semi-stable node labelling		semi-stable arrow labelling
stable node labelling	⇔	stable arrow labelling

It is possible to translate a SETAF to an AF, and in the current section we will provide one particular way of doing so (other methods are presented, e.g., in [43]). The idea is that the arrows of the SETAF become the nodes of the AF.7 As the arrows of the original framework become the nodes of the associated framework we say we turn the framework “inside-out”. The proofs of this section can be found in Appendix L.

Definition 22.
Let $S F = (N, a r r)$ be a SETAF. We define the associated inside-out argumentation framework ${A F}_{S F}$ as $(N, a r r)$ with $N = a r r$ and $a r r = {((M_{1}, A_{1}), (M_{2}, A_{2})) | (M_{1}, A_{1}), (M_{2}, A_{2}) \in a r r$ and $A_{1} \in M_{2}}$

As a side effect of this translation, the arrow labellings of the SETAF become the node labellings of the associated argumentation framework.
Theorem 23.
Let $S F = (N, a r r)$ be a SETAF and ${A F}_{S F} = (N, a r r)$ be the associated argumentation framework. It holds that $A L a b$ is a complete (resp. grounded, preferred, semi-stable or stable) SETAF arrow labelling of $S F$ iff $A L a b$ is a complete (resp. grounded, preferred, semi-stable or stable) node labelling of ${A F}_{S F}$ .

The relation described in Theorem 23 is summarised in Table 13. The fact that SETAF arrow labellings are equivalent to the associated argumentation framework node labellings (Theorem 23), together with the earlier observed equivalence between SETAF node labellings and SETAF arrow labellings (Theorem 21) allows for the connection between the node labellings of a SETAF and the node labellings of the associated argumentation framework. These are one-to-one related through the functions $N L a b 2 A L a b$ and $A L a b 2 N L a b$ , when applying complete, grounded, preferred, or stable semantics (but not when applying semi-stable semantics, as we have seen earlier). We will now provide an example for the “inside-out” framework of a SETAF.

Table 13
The relation between arrow labellings of a SETAF $S F$ and node labellings of its corresponding inside-out framework ${A F}_{S F}$ .

Arrow labelling of $S F$ Relation Node labelling of ${A F}_{S F}$

complete arrow labelling ⇔ complete node labelling

grounded arrow labelling ⇔ grounded node labelling

preferred arrow labelling ⇔ preferred node labelling

semi-stable arrow labelling ⇔ semi-stable node labelling

stable arrow labelling ⇔ stable node labelling

Example 24.
Recall the SETAF $S F = (N, a r r)$ from Example 12 (see (a)). The associated inside-out argumentation framework is ${A F}_{S F} = (N, a r r)$ with
$\begin{aligned} N & = {(\emptyset, A), ({A}, B), ({B, C}, E), ({C, F}, E), ({C}, F), ({D}, B), ({E}, D), ({F}, C)} . \\ a r r & = {((\emptyset, A), ({A}, B)), (({A}, B), ({B, C}, E)), (({B, C}, E), ({E}, D)), \\ (({D}, B), ({B, C}, E)), (({F}, C), ({B, C}, E)), (({E}, D), ({D}, B)), (({F}, C), ({C}, F)) \\ (({F, C}), ({C, F}, E)), (({C}, F), ({F}, C)), (({C}, F), ({C, F}, E)), \\ (({C, F}, E), ({E}, D))} \end{aligned}$

$S F$ has three complete arrow labellings:
$\begin{aligned} {A L a b}_{1} & = ({(\emptyset, A)}, {({A}, B)}, {({B, C}, E), ({C, F}, E), ({C}, F), ({D}, B), ({E}, D), \\ ({F}, C)}) \\ {A L a b}_{2} & = ({(\emptyset, A), ({F}, C), ({E}, D)}, {({A}, B), ({C}, F), ({D}, B), ({B, C}, E), \\ ({C, F}, E)}, \emptyset) \\ {A L a b}_{3} & = ({(\emptyset, A), ({C}, F)}, {({A}, B), ({F}, C), ({C, F}, E)}, {({B, C}, E), ({D}, B), \\ ({E}, D)}) \end{aligned}$
${A F}_{S F}$ has three complete node labellings:
$\begin{aligned} {N L a b}_{1} & = {A L a b}_{1}, \\ {N L a b}_{2} & = {A L a b}_{2}, \\ {N L a b}_{3} & = {A L a b}_{3} \end{aligned}$

5. .Instantiating AFs and SETAFs using ABA

Arrow labelling of $S F$	Relation	Node labelling of ${A F}_{S F}$
complete arrow labelling	⇔	complete node labelling
grounded arrow labelling	⇔	grounded node labelling
preferred arrow labelling	⇔	preferred node labelling
semi-stable arrow labelling	⇔	semi-stable node labelling
stable arrow labelling	⇔	stable node labelling

In the current section, we show how assumption-based argumentation (ABA) can be used to instantiate both a standard AF and a SETAF. The common instantiation procedure translates a given ABA framework (ABAF) into a standard AF [19]. However, it turns out that the concepts underlying ABA are actually much closer in spirit to SETAFs. Here we discuss both instantiations and examine to what extent they can be considered equal to each other. Thereby, we will build upon our previously established results showing a close correspondence between the formalisms. We start with introducing ABAFs.

Definition 25 [21]

An ABAF is a tuple $D = (L, R, A, \bar{})$ where:

$(L, R)$ is a deductive system, with $L$ being a logical language, and $R$ being a set of inference rules on this language,

$A \subseteq L$ is a (non-empty) set of assumptions,

$\bar{}$ is the contrary function, i.e., a total mapping from $A$ into $L$ ; $\bar{α}$ is called the contrary of α.

For current purposes we only consider ABAFs that are flat in the sense of [10], which amounts to no assumption being the head of an inference rule.

Definition 26 [21]

Given an ABAF $D = (L, R, A, \bar{})$ , a derivation tree for $c \in L$ (the conclusion or claim) supported by $A s m s \subseteq A$ is a finite tree t with nodes labelled by formulas in $L$ or by the special symbol ⊤ such that:

the root is labelled c

for every node N

*
if N is a leaf then N is labelled either by an assumption or by ⊤
*
if N is not a leaf and b is the label of N, then there exists an inference rule $b \leftarrow b_{1}, \dots, b_{m}$ ( $m ⩾ 0$ ) and either $m = 0$ and the child of N is labelled by ⊤, or $m > 0$ and N has m children, labelled by $b_{1}, \dots, b_{m}$ respectively

$A s m s (t)$ is the set of all assumptions labelling the leaves
We denote by $c l (t) = c$ the conclusion of t.

Note that for each assumption $γ \in A$ , a trivial derivation tree consisting of a leaf labelled γ is induced.

Now that the notions of an ABAF and a derivation tree have been defined, we proceed with defining the ABA semantics [10,19]. Historically, they have been defined in two different ways: using extensions of assumptions or using extensions of arguments [10,19,21]. We start with the more contemporary argument-based notion.
Definition 27.
Given an ABAF $D = (L, R, A, \bar{})$ , an ABA-argument is a pair $(A s m s, c)$ where $A s m s \subseteq A$ and $c \in L$ such that there is a derivation tree t with $c l (t) = c$ and $A s m s (t) = A s m s$ . We say that an ABA-argument $({A s m s}_{1}, c_{1})$ attacks an ABA-argument $({A s m s}_{2}, c_{2})$ iff $c_{1} = \bar{γ}$ for some $γ \in {A s m s}_{2}$ .

Our notion of an ABA-argument (Definition 27) is in line with the notation in the ABA literature [22], where a derivation tree is often denoted as $A s m s ⊢ c$ . Notice, however, that as observed in [22] there can be several derivation trees (Definition 26) that yield the same assumptions-conclusion pair (Definition 27). However, for the purpose of the ABA semantics it does not matter whether one defines arguments as derivation trees or as pairs of assumptions and conclusions, since the semantics are characterised by considering this information only. Formally, ABA-arguments $(A s m s, c)$ are equivalence classes of derivation trees for the purpose of argumentation semantics.

Using the notion of ABA-arguments and their attacks, it is straightforward to define the associated AF.
Definition 28.
Given an ABAF $D = (L, R, A, \bar{})$ , the associated AF ${A F}_{D}$ is defined as $(N, a r r)$ with N being the set of ABA-arguments, and $a r r$ being the attack relation among ABA-arguments.

The semantics of the ABAF D can now be determined by the semantics of the associated AF ${A F}_{D}$ in the usual way. Due to the altered notion of ABA-arguments in Definition 27 as compared to [10,22], the associated AF of an ABAF might contain fewer nodes (ABA-arguments) and arrows than the one constructed according to [22]. Nevertheless, the semantics correspond as proven in Appendix M.
Example 29.
We consider the ABAF $D = (L, R, A, \bar{})$ where $A = {a, b, c, d, e, f}$ , $L = A \cup {a_{c} | a \in A}$ , $\bar{a} = a_{c}$ for each $a \in A$ , and
$\begin{aligned} a_{c} & \leftarrow & b_{c} \leftarrow d . & d_{c} \leftarrow e . & e_{c} \leftarrow b, c . \\ b_{c} & \leftarrow a . & e_{c} \leftarrow c, f . & f_{c} \leftarrow c . & c_{c} \leftarrow f . \end{aligned}$
In this example, each rule induces one ABA-argument, for instance $({c, f}, e_{c})$ . The attack relation is the natural one. Hence the AF $F_{D}$ is given as follows.

Note the structural similarity to the inside-out AF from Example 24 when ignoring the trivial ABA-arguments of the form $({a}, a)$ .

Now that we have provided the contemporary definition of ABA semantics which is based on extensions (resp. labellings) of arguments, we shift our attention to the more classical definition of ABA semantics which is based on extensions (resp. labellings) of assumptions. While the former can be captured by constructing an AF, the latter can be captured by a SETAF, which we are going to demonstrate subsequently. First, we define the semantics directly on the ABAF, without any kind of instantiation.
Definition 30.
Let $D = (L, R, A, \bar{})$ be an ABAF, $A s m s \subseteq A$ and $α \in A$ . We say that $A s m s$ attacks α iff there is an ABA-argument $({A s m s}^{'}, \bar{α})$ with ${A s m s}^{'} \subseteq A s m s$ . We say that ${A s m s}_{1} \subseteq A$ attacks ${A s m s}_{2} \subseteq A$ iff ${A s m s}_{1}$ attacks some $β \in {A s m s}_{2}$ . We define ${A s m s}^{+}$ as ${α \in A | A s m s$ attacks $α}$ . We say that $A s m s$ is conflict-free iff $A s m s \cap {A s m s}^{+} = \emptyset$ . We say that $A s m s$ defends α iff for each ${A s m s}^{'} \subseteq A$ that attacks α, $A s m s$ attacks ${A s m s}^{'}$ . We define the function $F : 2^{A} \to 2^{A}$ as follows: $F (A s m s) = {α \in A | α$ is defended by $A s m s}$ .
Definition 31.
Let $D = (L, R, A, \bar{})$ be an ABAF. The set $A s m s \subseteq A$ is called (1)
an admissible assumption set iff $A s m s$ is conflict-free and $A s m s \subseteq F (A s m s)$
(2)
a complete assumption extension iff $A s m s$ is conflict-free and $A s m s = F (A s m s)$
(3)
a grounded assumption extension iff $A s m s$ is the (unique) minimal (w.r.t. ⊆) complete assumption extension
(4)
a preferred assumption extension iff $A s m s$ is a maximal (w.r.t. ⊆) complete assumption extension
(5)
a semi-stable assumption extension iff $A s m s$ is a complete assumption extension where $A s m s \cup {A s m s}^{+}$ is maximal (w.r.t. ⊆) among the complete assumption extensions
(6)
a stable assumption extension iff $A s m s$ is a complete assumption extension with $A s m s \cup {A s m s}^{+} = A$

Since the notion of ABA-arguments (Definition 27) influences the attack and defense relations between arguments (Definition 30), it also affects the definition of semantics of an ABAF as compared to [10,22]. However, the semantics of an ABAF are the same no matter whether our definition of arguments or the one in [22] is used. It should also be noticed that description of preferred and stable semantics in Definition 31 is slightly different from [10,22]. We prove equivalence in Appendix M.
Theorem 32.
Let $D = (L, R, A, \bar{})$ be an ABAF. (1)
The set $A s m s \subseteq A$ is an admissible assumption set according to Definitions 26-31 iff $A s m s$ is an admissible assumption set according to the definitions in [ 10 , 22 ].
(2)
The set $A s m s \subseteq A$ is a complete (resp. grounded, preferred, semi-stable or stable) assumption extension according to Definitions 26-31 iff $A s m s$ is a complete (resp. grounded, preferred, semi-stable or stable) assumption extension according to the definitions in [ 10 , 17 , 22 ]

We next consider the SETAF instantiation of an ABAF. The SETAF is close to the original ABAF as for instance stated in [10,22]. Instead of computing all derivation trees to construct an AF, the SETAF we instantiate only contains the set $A$ of assumptions as arguments. Then, the induced attacks are defined in a very natural way: if $(Asms, \bar{γ})$ is an ABA-argument, then the set $A s m s$ attacks the assumption γ. Since SETAFs have the modeling capabilities of capturing this, we can simply use this as the definition of our attack relation. In summary, this yields the following definition of the associated SETAF.
Definition 33.
Given an ABAF $D = (L, R, A, \bar{})$ , the associated SETAF ${S F}_{D}$ is defined as $(N, a r r)$ with $N = A$ and $a r r = {(A s m s, γ) | (A s m s, \bar{γ}) is an ABA-argument with γ \in A}$ .
Example 34.
Recall the previous ABAF $D = (L, R, A, \bar{})$ where $A = {a, b, c, d, e, f}$ , $L = A \cup {a_{c} | a \in A}$ , $\bar{a} = a_{c}$ for each $a \in A$ , and rules
$\begin{aligned} a_{c} & \leftarrow & b_{c} \leftarrow d . & d_{c} \leftarrow e . & e_{c} \leftarrow b, c . \\ b_{c} & \leftarrow a . & e_{c} \leftarrow c, f . & f_{c} \leftarrow c . & c_{c} \leftarrow f . \end{aligned}$
Each assumption in $A$ induces one argument in our SETAF ${S F}_{D}$ . Moreover, the attacks can be read off of the rules: for instance, c and f collectively attack e due to the rule “ $e_{c} \leftarrow c, f$ .” Consequently, ${S F}_{D}$ is given as follows.

Again, note the structural similarity to the SETAF from Example 24.

It is not difficult to see that the extensions of the thus constructed SETAF correspond to the traditional ABA extensions of assumptions.
Theorem 35.
Let $D = (L, R, A, \bar{})$ be an ABAF, ${S F}_{D}$ be the associated SETAF, and $A s m s \subseteq A$ . It holds that (1)
$A s m s$ is a complete extension of ${S F}_{D}$ iff $A s m s$ is a complete extension of D in the sense of [ 10 , 22 ];
(2)
$A s m s$ is a grounded extension of ${S F}_{D}$ iff $A s m s$ is a grounded extension of D in the sense of [ 10 , 22 ];
(3)
$A s m s$ is a preferred extension of ${S F}_{D}$ iff $A s m s$ is a preferred extension of D in the sense of [ 10 , 22 ];
(4)
$A s m s$ is a semi-stable extension of ${S F}_{D}$ iff $A s m s$ is a semi-stable extension of D in the sense of [ 15 ];
(5)
$A s m s$ is a stable extension of ${S F}_{D}$ iff $A s m s$ is a stable extension of D in the sense of [ 10 , 22 ].

Hence, the essential difference between the classical ABA definitions (in which semantics are defined in terms of assumptions [10,22]) and the more contemporary ABA-AF instantiation (in which semantics are defined in terms of arguments [21]) is that the classical ABA definititions are based on a SETAF, in which the ABA-arguments form the arrows, whereas the ABA-AF instantiation is based on an AF, in which the ABA-arguments form the nodes.8

Now that the difference between the classical ABA definitions and the ABA-AF instantiation has been made clear, we can shed new light on the issue of whether these are actually equivalent. The idea is to apply the abstract theory on AF labellings and SETAF labellings in the particular context of ABA. This is done using the following steps: (1)
Start with the SETAF generated by the ABA SETAF instantiation. The complete (resp. grounded, preferred, semi-stable or stable) assumption extensions of the ABA-framework correspond one-to-one with the complete (resp. grounded, preferred, semi-stable and stable) node labellings of the SETAF.
(2)
Convert the SETAF node labellings to the associated SETAF arrow labellings (that is, apply the concept of arrow-semantics to the SETAF). Since each arrow of the SETAF is associated with an ABA-argument, this will essentially define a labelling of ABA-arguments.
(3)
Convert the SETAF into an AF (the associate inside-out AF, cf. Definition 22). The arrows of the SETAF become the nodes of the AF. The arrow labellings of the SETAF become the node labellings of the AF.
(4)
The thus obtained AF is almost equivalent to the ABA-AF instantiation. However, two things still need to be taken care of. First, we should restore the contrary signs in the conclusions of the ABA-arguments, which were lost when generating the SETAF at step 1. Secondly, it can be observed that the resulting graph only contains the attacking ABA-arguments (arguments whose conclusion is the contrary of an assumption) whereas the ABA-AF instantiation also contains the non-attacking ABA-arguments (arguments whose conclusion is not the contrary of an assumption). These need to be added to the graph. The thus added nodes might have in-going arrows, but do not have any out-going arrows. Consequently, the node labellings can be extended in a straightforward way. Thereby, the overall set of accepted assumptions is preserved. The result will be the ABA-AF instantiation, with associated labellings.
At step 4, the effect of adding the non-attacking ABA-arguments basically means going from an AF ${A F}_{1} = (N_{1}, {a r r}_{1})$ to an AF ${A F}_{2} = (N_{2}, {a r r}_{2})$ such that
$\begin{aligned} N_{1} \subseteq N_{2} and a r r_{2} \cap (N_{1} \times N_{1}) = a r r_{1} \end{aligned}$
(1)
(no new arrows are added among the nodes that were already there) and
$\begin{aligned} a r r_{2} \cap ((N_{2} ∖ N_{1}) \times N_{2}) = \emptyset \end{aligned}$
(2)
(the new nodes do not have out-going arrows). In this situation, the complete (resp. grounded, preferred or stable) node labellings of ${A F}_{2}$ can be computed straightforwardly if we are given the labellings of ${A F}_{1}$ . While this is intuitively clear, from a formal point of view we make use of the directionality principle here [3].
Proposition 36.
Let ${A F}_{1} = (N_{1}, {a r r}_{1})$ and ${A F}_{2} = (N_{2}, {a r r}_{2})$ be two AFs such that conditions (1) and (2) are met. (i)
If ${N L a b}_{1}$ is a complete (resp. grounded, preferred or stable) node labelling of ${A F}_{1}$ , then
$\begin{aligned} {N L a b}_{2} & = {N L a b}_{1} \cup {(A, i n) | A \in N_{2} ∖ N_{1}, \forall (B, A) \in {a r r}_{2} : {N L a b}_{1} (B) = o u t} \\ \cup {(A, o u t) | A \in N_{2} ∖ N_{1}, \exists (B, A) \in {a r r}_{2} : {N L a b}_{1} (B) = i n} \\ \cup {(A, u n d e c) | A \in N_{2} ∖ N_{1}, \neg \forall (B, A) \in {a r r}_{2} : {N L a b}_{1} (B) = o u t, \\ \neg \exists (B, A) \in {a r r}_{2} : {N L a b}_{1} (B) = i n} \end{aligned}$
is a complete (resp. grounded, preferred or stable) node labelling of ${A F}_{2}$ .
(ii)
If ${N L a b}_{2}$ is a complete (resp. grounded, preferred or stable) node labelling of ${A F}_{2}$ , then ${N L a b}_{1}$ is a complete (resp. grounded, preferred or stable) node labelling of ${A F}_{1}$ .

It can be observed that the thus defined conversion functions between node labellings of ${A F}_{1}$ and node labellings of ${A F}_{2}$ are bijective functions that are each other’s inverses. Hence, the complete (resp. grounded, preferred and stable) node labellings of ${A F}_{1}$ and the complete (resp. grounded, preferred and stable) node labellings of ${A F}_{2}$ are one-to-one related.

We now formalise that the relation between the inside-out AF associated to ${S F}_{D}$ and the AF ${A F}_{D}$ corresponding to D meets the conditions described in Proposition 36.
Proposition 37.
Let D be an ABAF. Let ${S F}_{D}$ be the associated SETAF and let ${A F}_{{S F}_{D}}$ be its inside-out AF. Let ${A F}_{D}$ be the AF associated with D. Then the relation between ${A F}_{1} := {A F}_{{S F}_{D}}$ and ${A F}_{2} := {A F}_{D}$ is as described in (1) and (2) (up to argument names).

The equivalences observed in the ABA-literature between extensions of assumptions (using the classical definition of ABA) and extensions of arguments (using the ABA-AF instantiation) follow from the above described theory on AFs and SETAFs. Let $D = (L, R, A, \bar{})$ be an ABAF and let ${A F}_{D} = (N, a r r)$ be the associated AF (the ABA-AF instantiation). We define the functions $A s m s 2 A r g s : 2^{A} \to 2^{N}$ and $A r g s 2 A s m s : 2^{N} \to 2^{A}$ as follows:
$\begin{aligned} A s m s 2 A r g s (A s m s) = {({A s m s}^{'}, c) \in N | {A s m s}^{'} \subseteq A s m s} \end{aligned}$
and
$\begin{aligned} A r g s 2 A s m s (M) = ⋃_{({A s m s}^{'}, c) \in M} {A s m s}^{'} . \end{aligned}$

We are now ready to give an alternative proof for the (known) result that an ABAF D can be evaluated by computing the semantics of the associated AF ${A F}_{D}$ . Our proof will make use of several relations we showed throughout the present paper.9
Theorem 38.
Let $D = (L, R, A, \bar{})$ be an ABA framework and ${A F}_{D} = (N, a r r)$ be the associated argumentation framework. (1)
If $A s m s$ is a complete (resp. grounded, preferred or stable) assumption extension of D, then $A s m s 2 A r g s (A s m s)$ is a complete (resp. grounded, preferred or stable) extension of ${A F}_{D}$ .
(2)
If M is a complete (resp. grounded, preferred or stable) extension of ${A F}_{D}$ then $A r g s 2 A s m s (M)$ is a complete (resp. grounded, preferred or stable) assumption extension of D.
(3)
When restricted to complete (resp. grounded, preferred and stable) assumption extensions of D and complete (resp. grounded, preferred and stable) extensions of ${A F}_{D}$ the functions $A s m s 2 A r g s$ and $A r g s 2 A s m s$ are bijective and each other’s inverses.

Proof.
We only do the case of complete semantics (the other semantics can be handled in a similar way). (1)
Let $A s m s$ be a complete assumption extension of D. We proceed in several steps, combining the results from our paper.

(i) By Theorem 35, the set $A s m s$ is a complete node extension of the associated SETAF ${S F}_{D}$ .

(ii) Now let $N L a b$ be the SETAF node labelling associated with $A s m s$ . From the correspondence between extensions and labellings (see Table 8), it follows that $N L a b$ is a complete SETAF node labelling of ${S F}_{D}$ .

(iii) In the next step, let $A L a b$ be the associated SETAF arrow labelling associated with $N L a b$ . By Theorem 21, it holds that $A L a b$ is a complete SETAF arrow labelling of ${S F}_{D}$ .

(iv) Let ${A F}_{{S F}_{D}}$ be the inside-out AF that results from converting the SETAF ${S F}_{D}$ (Definition 22). By Theorem 23, it holds that $A L a b$ is a complete node labelling of ${A F}_{{S F}_{D}}$ .

(v) Now let ${A F}_{D}$ be the AF associated to D. By Proposition 37, it holds that ${A F}_{D}$ is the result of taking ${A F}_{{S F}_{D}}$ and adding some nodes without out-going arrows. Since $A L a b$ is a complete node labelling of ${A F}_{S F}$ it follows that the labelling ${A L a b}^{'}$ resulting from applying Proposition 36 is a complete node labelling of ${A F}_{D}$ .

(vi) Let M be the associated complete extension. It holds that M consists of precisely those ABA-arguments whose assumptions are in $A s m s$ . This can be seen as follows: Each attacking ABA-argument whose assumptions are in $A s m s$ will have been represented as an arrow in the SETAF that was labelled $i n$ by the SETAF arrow labelling (this is because the assumptions $A s m s$ were labelled $i n$ as nodes of the SETAF); consequently it was still labelled $i n$ by the node labelling of ${A F}_{S F}$ , so still labelled $i n$ by the node labelling of ${A F}_{D}$ , and thus an element of M. We have left to deal with the auxiliary nodes without out-going arrows. As we already mentioned, the node labelling of ${A F}_{D}$ can be obtained by applying Proposition 36 to ${A F}_{S F}$ . So we analyse which further arguments are labelled $i n$ : By construction of ${A F}_{D}$ , the additional nodes are ABA-arguments of the form $({A s m s}^{'}, γ)$ s.t. γ is not the contrary of any assumption in D. Since in-going arrows in ABA are determined by the assumptions required to construct an argument, $({A s m s}^{'}, γ)$ is defended by our complete labelling of ${A F}_{D}$ iff ${A s m s}^{'} \subseteq A s m s$ . In this case, $({A s m s}^{'}, γ)$ is labelled $i n$ (Proposition 36); otherwise it is not. Consequently, the set $A s m s$ of accepted assumptions does not change when moving from ${A F}_{S F}$ to $A F_{D}$ and applying Proposition 36 to the novel nodes without out-going arrows.
(2)
Let M be a complete extension of ${A F}_{D}$ and let $A s m s$ be the set
$\begin{aligned} A s m s = ⋃_{({A s m s}^{'}, c) \in M} {A s m s}^{'} . \end{aligned}$
All of the aforementioned steps are applicable in both directions, so we can (i)
remove suitable nodes from ${A F}_{D}$ to yield correspondence to the inside-out AF ${A F}_{{S F}_{D}}$ associated with ${S F}_{D}$ ;
(ii)
move from the node labelling of ${A F}_{{S F}_{D}}$ to an arrow labelling of ${S F}_{D}$ ;
(iii)
move from the arrow labelling of ${S F}_{D}$ to a node labelling of ${S F}_{D}$ ;
(iv)
move from the node labelling of ${S F}_{D}$ to a node extension of ${S F}_{D}$ .
By the same chain of reasoning, the thus obtained set ${A s m s}^{'}$ is a complete assumption set of D.
(3)
In each step of the above proof, the applied mappings are bijective and each other’s inverses. Consequently, this also applies to the whole process altogether. Note in particular that, as we pointed out, the auxiliary nodes added to move from the inside-out SETAF to the associated AF do not impact the accepted assumptions.

An interesting observation is that this proof can be used to explain at which step the transformation fails for semi-stable semantics: While most of the steps would actually also work for semi-stable semantics (applying Theorem 35, Theorem 23, Table 8, and Proposition 37), the problem arises in step (iii) where we apply Theorem 21 moving from node labellings to arrow labellings in the SETAF under consideration.
6. .Discussion

In this paper we thoroughly investigated abstract argumentation semantics in several dimensions: we studied extension-based and labelling-based node and arrow semantics for standard argumentation frameworks and for argumentation frameworks with collective attacks (SETAFs), and investigated the relation between these semantics. We mapped out the entire space of possibilities, also regarding what happens when minimising or maximising a particular label. We systematically filled the gaps in the literature and introduced arrow extensions for AFs as well as arrow extensions and labellings for SETAFs (cf. red coloured elements in Fig. 2). We studied the relation to the already established semantics and compared the obtained results for SETAFs with the results for AFs. We showed that each SETAF can be “turned inside-out” and efficiently transformed into a semantically corresponding AF (cf. red coloured arc in Fig. 2). Note that arrow semantics for SETAFs can be defined in various ways (for example, preferred extensions can be defined in terms of ⊆-maximal admissible or ⊆-maximal complete extensions). We immediately obtain the same flexibility for these definitions that we are used to from AF semantics by applying Theorem 23.

Finally, we applied our findings in the realm of structured argumentation. We pointed out that for ABA frameworks our inside-out frameworks capture the instantiation process: while traditionally the semantics on the abstract level are evaluated via AFs, the original definitions are closer to the semantics of SETAFs. If this obtained SETAF is turned “inside-out”, then we obtain the traditional instantiated AF.

Fig. 2.

The separation line for semi-stable semantics (dashed) indicates transformations for which semi-stable semantics is not preserved. The arc (red coloured, inside-out labelled) between SETAF arrow labellings and AF node labellings visualises the result from Theorem 23: each SETAF arrow labelling corresponds to the node labelling of the corresponding inside-out AF. Notably, semi-stable semantics are preserved in this translation. The contributions of this paper are highlighted in red colour.

The subtle difference of semi-stable semantics. We want to highlight that the semantics correspondence holds for some of the established semantics, with the notable exception of semi-stable semantics. As indicated in Fig. 2, semi-stable semantics does not survive each transformation step. The parting line lies between node and arrow semantics for both AFs and SETAFs. Figure2 shows that our transformations preserve all considered semantics on the horizontal axis, i.e., transforming node extensions to node labellings (arrow extensions and arrow labellings, respectively) and vice versa; but they fail to preserve semi-stable semantics vertically, i.e., for switching from node extensions to arrow extensions (node labellings to arrow labellings, respectively) and vice versa. Interestingly, when moving from SETAFs to AFs via the inside-out transformation, we switch levels: as shown in Section 4, semi-stable SETAF arrow semantics correspond to semi-stable AF node semantics of the resulting AF and vice versa.

The heterogeneous behaviour of semi-stable semantics has been already observed in several different settings, e.g., when comparing logic programs and AFs [16], in the context of ABA and AFs [17], and for different variants of claim semantics [33,34,45]. In our present work, we show that these differences can be found even within the same formalism, when comparing node and arrow semantics. Utilising our novel transformation from SETAFs to AFs, we furthermore reveal that AF node semantics and SETAF arrow semantics lie in the same category (with respect to semi-stable semantics).

An alternative view on attack semantics. Arrow semantics on AFs have been initially introduced as “attack semantics” [52]. However, our intuition differs slightly from the initial definition: in [52] the arrows (i.e., attacks) are partitioned into “successful” and “unsuccessful”; these correspond to the $i n / u n d e c$ and $o u t$ labelled arrows, respectively. In contrast, our arrow extensions capture precisely the $i n$ labelled arrows. In this way, we establish a closer correspondence to the traditional three-valued node labellings for AFs which are based on the same intuition [51]. We want to emphasise however that the labelling-based arrow semantics coincide with the notions of [52].

We furthermore note that labellings for SETAFs that assign both arrows and nodes $i n$ , $o u t$ , or $u n d e c$ labels have been already considered [31]. In contrast, we consider arrow labelling semantics separately from node labellings. The generalisation of both arrow extension and labelling semantics to SETAFs is a novel contribution of this paper.

A radically new approach to flattening. Whether the simplicity of AFs is an advantage or a disadvantage has not yet been conclusively clarified; in any case, recent years have witnessed numerous generalisations of standard argumentation frameworks, e.g., generalisations that allow for preferences [1], values [7], collective attacks [42], as discussed in the present work, or a support relation [18], just to name a few. Regardless of other potential shortcomings, a unified model has its advantages; and in response to any generalisations, methods have been developed to reintegrate the generalisations into standard argumentation frameworks. The flattening technique [9] is the task to translate generalised argumentation frameworks into AFs. Usually, additional arguments are introduced to compensate the increased expressiveness of the generalised model [36,43]. Moreover, while translations from SETAFs to AFs exist (cf. [43]) these methods usually capture the semantic correspondence in the arguments (under projection).

Our approach is radically different: each arrow in the SETAF becomes a node in the AF. Instead of handling the increased expressiveness with additional arguments, we exploit the close correspondence of arrow labellings of SETAFs to node labellings of AFs. That is, starting from a given SETAF, (1)

we exploit the connection between node extensions and node labellings (for SETAFs);

(2)

we switch from node labellings to arrow labellings (for SETAFs);

(3)

we turn the framework inside-out – now, each arrow in the SETAF becomes a node in the AF;

(4)

we move from node labellings to node extensions (for AFs).

In this way, we obtain the desired AF without any additional arguments. Due to the correspondence of node labellings of AFs and arrow labellings on SETAFs we can establish a semantic correspondence between the nodes of a SETAF and its inside-out AF. This method is successful for all except semi-stable semantics when comparing the node semantics of the original SETAF instance with the node semantics of the obtained AF. As discussed above, semi-stable semantics is not preserved in point (2), i.e., when switching from node labellings to arrow labellings. We note that the proof of Theorem 38 in Section 5 makes use of the close connection of the formalisms we discussed.

Finally, we want to point out that a model that is similar to our inside-out AF has been studied in the context of dynamics in argumentation. For any given SETAF, the resulting inside-out AF resembles a cvAF [46] – an argumentation framework with explicit claims (conclusions) and vulnerabilities. For an arrow $(M, A)$ of the original SETAF $S F$ (i.e., a node of the associated inside-out argumentation framework ${A F}_{S F}$ ) the claim is A and the vulnerabilities are the elements of $M$ .

Future work. For future work, we want to investigate further semantics in all of the considered dimensions. In particular, we want to study ideal and eager semantics [12]. We anticipate that eager semantics admit a behaviour that is similar to semi-stable semantics. Ideal semantics, on the other hand, are expected to behave in line with the classical Dung semantics. Furthermore, the investigation of more involved semantics like $c f 2$ [4], $stage 2$ [25] or the more recent weak admissibility [5] would be a challenging, yet exciting task.

Abstract argumentation formalisms have been extensively investigated in terms of formal properties, principles [3,27], and the expressive power of standard argumentation frameworks and their generalisations [6,23,33,50]. However, the aforementioned results focus on node extensions in the respective formalism. It would be insightful to explore to which extent our inter-translations can help to study these properties also for e.g. arrow extensions.

Footnotes

Acknowledgements

This research has been supported by the Vienna Science and Technology Fund (WWTF) through project ICT19-065, the Austrian Science Fund (FWF) through project P32830, and by the Federal Ministry of Education and Research of Germany and by Sächsische Staatsministerium für Wissenschaft, Kultur und Tourismus in the programme Center of Excellence for AI-research “Center for Scalable Data Analytics and Artificial IntelligenceDresden/Leipzig”, project identification number: ScaDS.AI.

Properties of arrow labellings for argumentation frameworks

The labelling-based version of complete attack-semantics is defined in a slightly different way in [52]. Instead of characterising a complete arrow labelling using three if-statements, as is done in Definition 7, it is characterised using two iff-statements [52, Theorem 7]. However, it can be proved that these two characterisations are equivalent.

We now proceed to prove a number of lemmas on how arrow labellings relate to each other, and how arrow labellings relate to node labellings.

The following theorem states that minimising (resp. maximising) particular labels sometimes yields the same outcome.

From Theorem 42 it follows that the grounded, preferred and semi-stable arrow labellings cover all possibilities regarding the maximisation and minimisation of a particular label (among the complete arrow labellings).

As an aside, there exists an alternative way of proving the correctness of Theorem 39, Lemma 40, Lemma 41 and Theorem 42. The idea is that where a node labelling is based on nodes attacking each other, an arrow labelling is based on arrows attacking each other. Whereas a node A attacks a node B iff $(A, B) \in a r r$ , an arrow $(C, D)$ attacks an arrow $(E, F)$ iff $D = E$ . Hence, the notion of attack becomes a binary relation between the arrows of the argumentation framework. This binary relation can in its turn be represented in the form of a graph (a meta-graph of the original argumentation framework). The idea is to take the original argumentation framework and “turn it inside out”. That is, the arrows of the original graph become the nodes of the new meta-graph.

As arrow labellings are essentially node labellings (of the inside out argumentation framework) they satisfy the standard properties of node labellings described in the literature. Hence, Theorem 39 follows from [14, Definition 5, Definition 6 and Theorem 1], Lemma 40 follows from [14, Lemma 1], Lemma 41 follows from [16, Lemma 2] and Theorem 42 follows from [14, Theorem 6, Theorem 7].

Equivalence of node labellings and arrow labellings for argumentation frameworks

Note that the following similar statements do not hold:

Notice that the respective missing cases do not hold – analogous to Lemma 49 (the same counter examples apply in this case). In fact, the similarities between Lemma 49 and Lemma 50 are no coincidence, they are a direct consequence of the fact that the functions $N L a b 2 A L a b$ and $A L a b 2 N L a b$ are each others inverses (see Theorem 8, point 2).

To illustrate why these cases do not hold, we recall Example 9 from Section 2 (see below). It holds that $u n d e c ({A L a b}_{3}) \subseteq u n d e c ({A L a b}_{2})$ but $u n d e c (A L a b 2 N L a b ({A L a b}_{3})) ⊈ u n d e c (A L a b 2 N L a b ({A L a b}_{2}))$ . Furthermore, it also holds that $u n d e c ({A L a b}_{3}) = u n d e c ({A L a b}_{2})$ but $u n d e c (A L a b 2 N L a b ({A L a b}_{3})) \neq u n d e c (A L a b 2 N L a b ({A L a b}_{2}))$ .

We recall Example 10 from Section 2 (see below). It holds that $u n d e c ({A L a b}_{3}) ⊊ u n d e c ({A L a b}_{2})$ but $u n d e c (A L a b 2 N L a b ({A L a b}_{3})) ⊈ u n d e c (A L a b 2 N L a b ({A L a b}_{2}))$ .

We recall the following Theorem 8 from Section 2 that sums up our findings regarding the connections between arrow labellings and node labellings on AFs. Theorem 8.

Let $A F = (N, a r r)$ be an argumentation framework and let $N L a b$ and $A L a b$ be a node labelling and an arrow labelling of $A F$ , respectively. It holds that: (1)

If $N L a b$ is a complete node labelling, then $N L a b 2 A L a b (N L a b)$ is a complete arrow labelling.

If $A L a b$ is a complete arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a complete node labelling.

(2)

When restricted to complete node labellings and complete arrow labellings, the functions $A L a b 2 N L a b$ and $N L a b 2 A L a b$ become bijections and each other’s inverses.

(3)

If $N L a b$ is a grounded node labelling, then $N L a b 2 A L a b (N L a b)$ is a grounded arrow labelling.

If $A L a b$ is a grounded arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a grounded node labelling.

(4)

If $N L a b$ is a preferred node labelling, then $N L a b 2 A L a b (N L a b)$ is a preferred arrow labelling.

If $A L a b$ is a preferred arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a preferred node labelling.

(5)

If $N L a b$ is a stable node labelling, then $N L a b 2 A L a b (N L a b)$ is a stable arrow labelling.

If $A L a b$ is a stable arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a stable node labelling.

Proof.

(1)

This follows from Lemma 45 and Lemma 46.

(2)

This follows from Lemma 47 and Lemma 48.

(3)

This follows from Lemma 51.

(4)

This follows from Lemma 52.

(5)

This follows from Lemma 53.

Node extensions for SETAFs: Equivalent definitions

In this section, we show that the semantics for AFs with collective attacks defined in [42] coincide with the formulations we present in Section 3.

Recall that AFs with collective attacks and SETAFs differ in their treatment of the empty attack: in AFs with collective attacks, the attack relation is a subset of $(2^{N} ∖ \emptyset) \times N$ while SETAFs allow for attacks of the form $(\emptyset, A)$ , $A \in N$ . However, this difference can be neglected, as we discuss in Appendix G. Another difference between the work of Nielsen and Parsons and the theory on SETAFs in Section 3 is how preferred and stable semantics are defined. Throughout the current paper, we have decided to use complete semantics as the basis for defining the other semantics (including preferred and stable). This is to provide a level of uniformity, and to allow for easy conversion between extensions and labellings. However, the work of Nielsen and Parsons stays closer to [20] in the sense that preferred semantics is defined in terms of admissibility and stable semantics in terms of conflict-freeness. The resulting notions, however, are equivalent, as is stated by the following results. Lemma 55 Fundamental Lemma

Let $S F = (N, a r r)$ be a SETAF, let $M \subseteq N$ be admissible, and let $A, A^{'} \in F_{S F} (M)$ (i.e., A and $A^{'}$ are defended by $M$ ). Then (1)

$M^{'} = M \cup {A}$ is admissible, and

(2)

$A^{'} \in F_{S F} (M^{'})$ .

Proof.

The proof is analogous to the proof of the fundamental lemma for AFs [20] and AFs with collective attacks [42]. (1)

By definition of admissibility, it suffices to show that $M^{'}$ is conflict-free. Towards a contradiction, assume that there exists an argument $B \in M^{'}$ and a set $M^{″} \subseteq M^{'}$ such that $(M^{″}, B) \in a r r$ . We consider three cases: (i) $A = B$ and $A \notin M^{″}$ ; (ii) $A = B$ and $A \in M^{″}$ ; (iii) $A \neq B$ and $A \in M^{″}$ , (iv) $A \neq B$ and $A \notin M^{″}$ .

(i) First assume $A = B$ and $A \notin M^{″}$ . That is, $M^{″} \subseteq M$ attacks A. Since A is defended by $M$ , there is some $M^{‴} \subseteq M$ that attacks $M^{″}$ . Hence we have $M$ is not conflict-free, contradiction.

(ii) Now assume $A = B$ and $A \in M^{″}$ . Since A is defended by $M$ , there is some $M^{‴} \subseteq M$ that attacks some element $C \in M^{″}$ . In case $C \in M^{″} \cap M$ , it follows that $M$ is not conflict-free, contradiction. In case $C = A$ , consider case (i).

(iii) Next assume $A \neq B$ and $A \in M^{″}$ . That is, the set $M$ is attacked by $M^{″}$ containing A. Since $M$ is admissible, there is some set $M^{‴} \subseteq M$ that attacks some element in $D \in b$ . Since $M$ is conflict-free, we have $D \notin M$ . It follows that $D = A$ , i.e, there is an attack $(M^{‴}, A) \in a r r$ with $M^{‴} \subseteq M$ . Hence, we can consider case (i) again to derive a contradiction.

(iv) Finally, suppose $A \neq B$ and $A \notin M^{″}$ . Hence, $M^{″} \cup {B} ⊈ M$ , contradiction to admissibility of $M$ .

(2)

By of the characteristic function.

Theorem 56.

Let $S F = (N, a r r)$ be a SETAF and let $M \subseteq N$ . The following two statements are equivalent. (1)

$M$ is a maximal (w.r.t. ⊆) admissible set of $S F$

(2)

$M$ is a maximal (w.r.t. ⊆) complete extension if $S F$

Proof.

from 1. to 2.

Consider a maximal (w.r.t. ⊆) admissible set $M$ of $S F$ . First, we show that $M$ is complete. We show that $M$ contains all nodes it defends. Let $A \in F (M)$ . By the fundamental lemma, it holds that $M \cup {A}$ is admissible. Since $M$ is a ⊆-maximal admissible set, it follows that $A \in M$ .

Next, we show that $M$ is ⊆-maximal among all complete extensions. Towards a contradiction, assume that there is a complete extension $M^{'}$ such that $M^{'} \supset M$ . By definition of complete semantics, $M^{'}$ is admissible. Hence, we have a contradiction to ⊆-maximality of $M$ among the admissible extensions of $S F$ .

from 2. to 1.

Consider a maximal (w.r.t. ⊆) complete set $M$ of $S F$ . By definition, each complete set is admissible. It remains to show that $M$ is ⊆-maximal among admissible sets. Towards a contradiction, suppose there is an admissible set $M^{'}$ such that $M^{'} \supset M$ . By monotonicity of the characteristic function, there is a complete extension $M^{″}$ such that $M^{'} \subseteq M^{″}$ . Hence, we obtain a contradiction to the ⊆-maximality of $M$ .

Theorem 57.

Let $S F = (N, a r r)$ be a SETAF and let $M \subseteq N$ . The following two statements are equivalent. (1)

$M$ is a conflict-free set that attacks all nodes in $N ∖ M$

(2)

$M$ is a complete extension with $M \cup M^{+} = N$

Proof.

from 1. to 2.

Consider a conflict-free set $M$ of $S F$ that attacks all nodes in $N ∖ M$ . Hence, it holds that $M \cup M^{+} = N$ .

We show that $M$ is complete:

By assumption, $M$ is conflict-free.

Moreover, it defends itself: towards a contradiction, assume there is some node $A \in M$ that is not defended by $M$ . I.e., there is some attack $(M^{'}, A) \in a r r$ such that $M^{'} \cap M^{+} = \emptyset$ . By assumption $M$ attacks all nodes in $N ∖ M$ , it follows that $M^{'} \subseteq M$ , contradiction to $M$ being conflict-free. Hence we conclude that $M$ is admissible.

We show that $M$ contains all nodes it defends: let $A \in F (M)$ . By the fundamental lemma, it holds that $M \cup {A}$ is admissible. Since $M$ attacks all nodes not contained in $M$ , it follows that $A \in M$ .

from 2. to 1.

By definition, each complete set is conflict-free. Moreover, $M \cup M^{+} = N$ iff $M$ attacks all nodes in $N ∖ M$ for all conflict-free sets by definition. This concludes the proof.

Properties of node labellings for SETAFs

Note that the following Lemma 59 and Theorem 60 are a straightforward generalisation of the respective results of AFs [14]. Lemma 59.

Let ${N L a b}_{1}$ and ${N L a b}_{2}$ be complete node labellings of SETAF $S F = (N, a r r)$ . It holds that: (1)

$i n ({N L a b}_{1}) \subseteq i n ({N L a b}_{2})$ iff $o u t ({N L a b}_{1}) \subseteq o u t ({N L a b}_{2})$

(2)

$i n ({N L a b}_{1}) = i n ({N L a b}_{2})$ iff $o u t ({N L a b}_{1}) = o u t ({N L a b}_{2})$

(3)

$i n ({N L a b}_{1}) ⊊ i n ({N L a b}_{2})$ iff $o u t ({N L a b}_{1}) ⊊ o u t ({N L a b}_{2})$

Proof.

(1)

“⇒”: Suppose $i n ({N L a b}_{1}) \subseteq i n ({N L a b}_{2})$ . Let $A \in o u t ({N L a b}_{1})$ . This means that (Definition 17, second bullet point) there exists a $(M, A) \in a r r$ such that $\forall B \in M : {N L a b}_{1} (B) = i n$ . The fact that $i n ({N L a b}_{1}) \subseteq i n ({N L a b}_{2})$ then implies that $\forall B \in M : {N L a b}_{2} (B) = i n$ . Then ${N L a b}_{2} (A)$ cannot be $i n$ (otherwise there would have to be a $B \in M$ such that ${N L a b}_{2} (B) = o u t$ ) and cannot be $u n d e c$ (by Definition 17, third bullet point). Since ${N L a b}_{2} (A)$ can only be $i n$ , $o u t$ or $u n d e c$ , it then follows that ${N L a b}_{2} (A) = o u t$ .

“⇐”: Suppose $o u t ({N L a b}_{1}) \subseteq o u t ({N L a b}_{2})$ . Let $A \in i n ({N L a b}_{1})$ . This means that (Definition 17, first bullet point) for each $M \subseteq N$ such that $(M, A) \in a r r$ it holds that $\exists B \in M : {N L a b}_{1} (B) = o u t$ . The fact that $o u t ({N L a b}_{1}) \subseteq o u t ({N L a b}_{2})$ then implies that for each $M \subseteq N$ such that $(M, A) \in a r r$ it holds that $\exists B \in M : {N L a b}_{2} (B) = o u t$ . Then ${N L a b}_{2} (A)$ cannot be $o u t$ (otherwise there would have to be a $(M, A) \in a r r$ such that $\forall B \in M : {N L a b}_{2} (B) = i n$ ) and cannot be $u n d e c$ (by Definition 17, third bullet point). Since ${N L a b}_{2} (A)$ can only be $i n$ , $o u t$ or $u n d e c$ , it then follows that ${N L a b}_{2} (A) = i n$ .

(2)

This follows directly from point 1.

(3)

This follows directly from point 1 and point 2.

Theorem 60.

Let $S F = (N, a r r)$ be a SETAF, and let $N L a b$ be a SETAF node labelling of $S F$ . The following two statements are equivalent: (1)

$i n (N L a b)$ is maximal (w.r.t. set inclusion) among all complete SETAF node labellings of $S F$

(2)

$o u t (N L a b)$ is maximal (w.r.t. set inclusion) among all complete SETAF node labellings of $S F$

The following three statements are also equivalent:

$i n (N L a b)$ is minimal (w.r.t. set inclusion) among all complete SETAF node labellings of $S F$

$o u t (N L a b)$ is minimal (w.r.t. set inclusion) among all complete SETAF node labellings of $S F$

$u n d e c (N L a b)$ is maximal (w.r.t. set inclusion) among all complete SETAF node labellings of $S F$

Furthermore, it holds that the complete SETAF node labelling with minimal

i n

is unique.

Proof.

from 1 to 2

Let $N L a b$ be a complete labelling where $o u t (N L a b)$ is not maximal. Then there exists a complete labelling ${N L a b}^{'}$ with $o u t (N L a b) ⊊ o u t ({N L a b}^{'})$ . From Lemma 59 it then follows that $i n (N L a b) ⊊ i n ({N L a b}^{'})$ , so $N L a b$ is a labelling where $i n (N L a b)$ is not maximal.

from 2 to 1

Let $N L a b$ be a complete labelling where $i n (N L a b)$ is not maximal. Then there exists a complete labelling ${N L a b}^{'}$ with $i n (N L a b) ⊊ i n ({N L a b}^{'})$ . From Lemma 59 it then follows that $o u t (N L a b) ⊊ o u t ({N L a b}^{'})$ , so $N L a b$ is a labelling where $o u t (N L a b)$ is not maximal.

from 3 to 4

Note that this result is mentioned in [8] in the context of extensions. Let $N L a b$ be a complete labelling where $o u t (N L a b)$ is not minimal. Then there exists a complete labelling ${N L a b}^{'}$ with $o u t ({N L a b}^{'}) ⊊ o u t (N L a b)$ . From Lemma 59 it then follows that $i n ({N L a b}^{'}) ⊊ i n (N L a b)$ , so $N L a b$ is a labelling where $i n (N L a b)$ is not minimal.

from 4 to 3

Note that this result is mentioned in [8] in the context of extensions. Let $N L a b$ be a complete labelling where $i n (N L a b)$ is not minimal. Then there exists a complete labelling ${N L a b}^{'}$ with $i n ({N L a b}^{'}) ⊊ i n (N L a b)$ . From Lemma 59 it then follows that $o u t ({N L a b}^{'}) ⊊ o u t (N L a b)$ , so $N L a b$ is a labelling where $o u t (N L a b)$ is not minimal.

from 3 to 5

Let $N L a b$ be a complete labelling where $i n (N L a b)$ is minimal. Then by Theorem 58 $N L a b 2 A r g s (N L a b)$ is the grounded extension. Now suppose that $u n d e c (N L a b)$ is not maximal. Then there exists a complete labelling ${N L a b}^{'}$ with $u n d e c (N L a b) ⊊ u n d e c ({N L a b}^{'})$ . It holds that $N L a b 2 A r g s ({N L a b}^{'})$ is a complete extension, and from the fact that the grounded extension is a subset of each complete extension, it follows that $N L a b 2 A r g s (N L a b) \subseteq N L a b 2 A r g s ({N L a b}^{'})$ , so $i n (N L a b) \subseteq i n ({N L a b}^{'})$ . From Lemma 59 it then follows that $o u t (N L a b) \subseteq o u t ({N L a b}^{'})$ . From the fact that $i n (N L a b) \subseteq i n ({N L a b}^{'})$ and $o u t (N L a b) \subseteq o u t ({N L a b}^{'})$ it follows that $u n d e c ({N L a b}^{'}) \subseteq u n d e c (N L a b)$ . Contradiction.

from 5 to 3

Let $N L a b$ be a complete labelling where $i n (N L a b)$ is not minimal. Then there exists a complete labelling ${N L a b}^{'}$ with $i n ({N L a b}^{'}) ⊊ i n (N L a b)$ . It then follows from Lemma 59 that $o u t ({N L a b}^{'}) ⊊ o u t (N L a b)$ , so $u n d e c (N L a b) ⊊ u n d e c ({N L a b}^{'})$ .

uniqueness grounded node labelling

Shown in [35].

Properties of arrow labellings for SETAF

We show that for SETAF arrow labellings the same properties hold as for AF arrow labellings, as shown in Appendix A. In particular, we show that the complete arrow labellings with maximal $i n$ are equal to the complete arrow labellings with maximal $o u t$ , and that the complete arrow labelling where $i n$ is minimal is unique and equal to both the complete arrow labelling where $o u t$ is minimal and the complete arrow labelling where $u n d e c$ is maximal (Theorem 64).

We start with an alternative definition for the conditions of complete arrow labellings for SETAF.

We now proceed to prove a number of lemmas on how arrow labellings relate to each other, and how arrow labellings relate to node labellings.

The following theorem states that minimising (resp. maximising) particular labels sometimes yields the same outcome.

From Theorem 64 it follows that the grounded, preferred and semi-stable arrow labellings cover all possibilities regarding the maximisation and minimisation of a particular label (among the complete arrow labellings).

Equivalence of node labellings and arrow labellings for SETAFs

Note that the following similar statements do not hold. While properties 7’, 8’, 9, and 9’ already do not hold for AFs (the same counter-example applies in this case), the properties 7 and 8 do hold for AFs, but do not hold for SETAFs. 7

If $u n d e c ({N L a b}_{1}) \subseteq u n d e c ({N L a b}_{2})$ then $u n d e c ({A L a b}_{1}) \subseteq u n d e c ({A L a b}_{2})$ . A counter example is $S F$ in Example 70: We have $u n d e c ({N L a b}_{2}) \subseteq u n d e c ({N L a b}_{3})$ but $u n d e c ({A L a b}_{2}) ⊈ u n d e c ({A L a b}_{3})$ .

7’

If $u n d e c ({A L a b}_{1}) \subseteq u n d e c ({A L a b}_{2})$ then $u n d e c ({N L a b}_{1}) \subseteq u n d e c ({N L a b}_{2})$ . A counter example is $A F$ in Example 9: We have $u n d e c ({A L a b}_{2}) \subseteq u n d e c ({A L a b}_{3})$ but $u n d e c ({N L a b}_{2}) ⊈ u n d e c ({N L a b}_{3})$ .

If $u n d e c ({N L a b}_{1}) = u n d e c ({N L a b}_{2})$ then $u n d e c ({A L a b}_{1}) = u n d e c ({A L a b}_{2})$ . A counter example is $S F$ in Example 70: We have $u n d e c ({N L a b}_{2}) = u n d e c ({N L a b}_{3})$ but $u n d e c ({A L a b}_{2}) \neq u n d e c ({A L a b}_{3})$ .

8’

If $u n d e c ({A L a b}_{1}) = u n d e c ({A L a b}_{2})$ then $u n d e c ({N L a b}_{1}) = u n d e c ({N L a b}_{2})$ . A counter example is $A F$ in Example 9: We have $u n d e c ({A L a b}_{2}) = u n d e c ({A L a b}_{3})$ but $u n d e c ({N L a b}_{2}) \neq u n d e c ({N L a b}_{3})$ .

If $u n d e c ({N L a b}_{1}) ⊊ u n d e c ({N L a b}_{2})$ then $u n d e c ({A L a b}_{1}) ⊊ u n d e c ({A L a b}_{2})$ . A counter example is $A F$ in Example 9: We have $u n d e c ({N L a b}_{3}) ⊊ u n d e c ({N L a b}_{2})$ but $u n d e c ({N L a b}_{3}) ⊊ u n d e c ({N L a b}_{2})$ .

9’

If $u n d e c ({A L a b}_{1}) ⊊ u n d e c ({A L a b}_{2})$ then $u n d e c ({N L a b}_{1}) ⊊ u n d e c ({N L a b}_{2})$ . A counter example is $A F$ in Example 10: We have $u n d e c ({A L a b}_{3}) ⊊ u n d e c ({A L a b}_{2})$ but $u n d e c ({N L a b}_{3}) ⊈ u n d e c ({N L a b}_{2})$ .

Example 70.

Let $S F = (N, a r r)$ be a SETAF with $N = {A, B, C, D, E}$ and

$a r r = {(\emptyset, A), ({A}, B), ({B}, B), ({B, C}, E), ({C}, D), ({D}, C), (\emptyset, E)}$ .

$S F$ has three complete node labellings:

\begin{aligned} {N L a b}_{1} = (\emptyset, {A, E}, {B, C, D}) \\ {N L a b}_{2} = ({C}, {A, D, E}, {B}) \\ {N L a b}_{3} = ({D}, {A, C, E}, {B}) \end{aligned}

and three complete arrow labellings:

\begin{aligned} {A L a b}_{1} = ({(\emptyset, A), (\emptyset, E)}, {({A}, B)}, {({B}, B), ({B, C}, E), ({C}, D), ({D}, C)}) \\ {A L a b}_{2} = ({(\emptyset, A), ({C}, D), (\emptyset, E)}, {({A}, B), ({D}, C)}, {({B}, B), ({B, C}, E)}) \\ {A L a b}_{3} = ({(\emptyset, A), ({D}, C), (\emptyset, E)}, {({A}, B), ({B, C}, E), ({C}, D)}, {({B}, B)}) \end{aligned}

These node labellings and arrow labellings correspond to each other through the functions

N L a b 2 A L a b

and

A L a b 2 N L a b

Lemma 71.

Let ${A L a b}_{1}$ and ${A L a b}_{2}$ be complete arrow labellings of SETAF $S F = (N, a r r)$ . Let ${N L a b}_{1} = A L a b 2 N L a b ({A L a b}_{1})$ and ${N L a b}_{2} = A L a b 2 N L a b ({A L a b}_{2})$ . It holds that: (1)

$i n ({A L a b}_{1}) \subseteq i n ({A L a b}_{2})$ iff $i n ({N L a b}_{1}) \subseteq i n ({N L a b}_{2})$ .

(2)

$i n ({A L a b}_{1}) = i n ({A L a b}_{2})$ iff $i n ({N L a b}_{1}) = i n ({N L a b}_{2})$ .

(3)

$i n ({A L a b}_{1}) ⊊ i n ({A L a b}_{2})$ iff $i n ({N L a b}_{1}) ⊊ i n ({N L a b}_{2})$ .

(4)

$o u t ({A L a b}_{1}) \subseteq o u t ({A L a b}_{2})$ iff $o u t ({N L a b}_{1}) \subseteq o u t ({N L a b}_{2})$ .

(5)

$o u t ({A L a b}_{1}) = o u t ({A L a b}_{2})$ iff $o u t ({N L a b}_{1}) = o u t ({N L a b}_{2})$ .

(6)

$o u t ({A L a b}_{1}) ⊊ o u t ({A L a b}_{2})$ iff $o u t ({N L a b}_{1}) ⊊ o u t ({N L a b}_{2})$ .

Proof.

(1)

“⇒”: Suppose $i n ({A L a b}_{1}) \subseteq i n ({A L a b}_{2})$ . Let $A \in i n ({N L a b}_{1})$ . Then, from the definition of $A L a b 2 N L a b$ it follows that for every $(M, A) \in a r r$ , $(M, A) \in o u t ({A L a b}_{1})$ . From the fact that $i n ({A L a b}_{1}) \subseteq i n ({A L a b}_{2})$ it follows that (Lemma 62) $o u t ({A L a b}_{1}) \subseteq o u t ({A L a b}_{2})$ , so $(M, A) \in o u t ({A L a b}_{2})$ . From the definition of $A L a b 2 N L a b$ it then follows that ${N L a b}_{2} (A) = i n$ . That is, $A \in i n ({N L a b}_{2})$ .

“⇐”: Suppose $i n ({N L a b}_{1}) \subseteq i n ({N L a b}_{2})$ . Let $(M, A) \in i n ({A L a b}_{1})$ . Since we assume that ${A L a b}_{1}$ is complete, it follows that for every $(M^{'}, B) \in a r r$ towards some $B \in M$ it holds $(M^{'}, B) \in o u t ({A L a b}_{1})$ , which in turn means for each of these $(M^{'}, B) \in a r r$ there is some $(M^{″}, C) \in a r r$ with $C \in M^{'}$ and $(M^{″}, C) \in i n ({A L a b}_{1})$ . Then, from the definition of $A L a b 2 N L a b$ it then follows that $C \in o u t ({N L a b}_{1})$ . From $i n ({N L a b}_{1}) \subseteq i n ({N L a b}_{2})$ and Lemma 59 (point 1) we then get $o u t ({N L a b}_{1}) \subseteq o u t ({N L a b}_{2})$ . From this and $C \in o u t ({N L a b}_{1})$ we get $C \in o u t ({N L a b}_{2})$ . Then from the definition of $A L a b 2 N L a b$ it follows $(M^{″}, C) \in i n ({A L a b}_{2})$ , and then since ${A L a b}_{2}$ is complete we get $(M^{'}, B) \in o u t ({A L a b}_{2})$ and consequently $(M, A) \in i n ({A L a b}_{2})$ .

(2)

This follows directly from point 1.

(3)

This follows directly from point 1 and point 2.

(4)

“⇒”: Suppose $o u t ({A L a b}_{1}) \subseteq o u t ({A L a b}_{2})$ . Let $A \in o u t ({N L a b}_{1})$ . Then, from the definition of $A L a b 2 N L a b$ it follows that there exists a $(M, A) \in a r r$ such that $(M, A) \in i n ({A L a b}_{1})$ . From the fact that $o u t ({A L a b}_{1}) \subseteq o u t ({A L a b}_{2})$ it follows that (Lemma 62) $i n ({A L a b}_{1}) \subseteq i n ({A L a b}_{2})$ , so $(M, A) \in i n ({A L a b}_{2})$ . From the definition of $A L a b 2 N L a b$ it then follows that ${N L a b}_{2} (A) = o u t$ . That is, $A \in o u t ({N L a b}_{2})$ .

“⇐”: Suppose $o u t ({N L a b}_{1}) \subseteq o u t ({N L a b}_{2})$ . Let $(M, A) \in o u t ({A L a b}_{1})$ . Since we assume that ${A L a b}_{1}$ is complete, it follows that there exists a $(M^{'}, B)$ towards some $B \in M$ such that $(M^{'}, B) \in i n ({A L a b}_{1})$ . By completeness this means that for every $(M^{″}, C) \in a r r$ towards some $C \in M^{'}$ it holds $(M^{″}, C) \in o u t ({A L a b}_{1})$ . Then, from the definition of $A L a b 2 N L a b$ it follows that $C \in i n ({N L a b}_{1})$ , and since this is the case for every $C \in M^{'}$ we get $M^{'} \subseteq i n ({N L a b}_{1})$ . From $o u t ({N L a b}_{1}) \subseteq o u t ({N L a b}_{2})$ and Lemma 62 we then get $i n ({N L a b}_{1}) \subseteq i n ({N L a b}_{2})$ . From this and $M^{'} \subseteq i n ({N L a b}_{1})$ we get $M^{'} \subseteq i n ({N L a b}_{2})$ . Then from the definition of $A L a b 2 N L a b$ it follows that for each $B \in M$ there is a $C \in M^{'}$ such that $(M^{″}, C) \in o u t ({A L a b}_{2})$ and hence $(M^{'}, B) \in i n ({A L a b}_{2})$ , and then since ${A L a b}_{2}$ is complete we get $(M, A) \in o u t ({A L a b}_{2})$ .

(5)

This follows directly from point 4.

(6)

This follows directly from point 4 and point 5.

Notice that the respective missing cases do not hold – analogous to Lemma 69 (the same counter examples apply in this case). In fact, the similarities between Lemma 69 and Lemma 71 are no coincidence, they are a direct consequence of the fact that the functions

N L a b 2 A L a b

and

A L a b 2 N L a b

are each others inverses (see Theorem 21, point 2).

We recall the following Theorem 21 from Section 3 that sums up our findings regarding the connections between arrow labellings and node labellings on SETAFs. Theorem 21.

Let $S F = (N, a r r)$ be a SETAF and let $N L a b$ and $A L a b$ be a node labelling and an arrow labelling of $S F$ , respectively. It holds that: (1)

If $N L a b$ is a complete node labelling, then $N L a b 2 A L a b (N L a b)$ is a complete arrow labelling.

If $A L a b$ is a complete arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a complete node labelling.

(2)

When restricted to complete node labellings and complete arrow labellings, the functions $A L a b 2 N L a b$ and $N L a b 2 A L a b$ become bijections and each other’s inverses.

(3)

If $N L a b$ is a grounded node labelling, then $N L a b 2 A L a b (N L a b)$ is a grounded arrow labelling.

If $A L a b$ is a grounded arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a grounded node labelling.

(4)

If $N L a b$ is a preferred node labelling, then $N L a b 2 A L a b (N L a b)$ is a preferred arrow labelling.

If $A L a b$ is a preferred arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a preferred node labelling.

(5)

If $N L a b$ is a stable node labelling, then $N L a b 2 A L a b (N L a b)$ is a stable arrow labelling.

If $A L a b$ is a stable arrow labelling, then $A L a b 2 N L a b (A L a b)$ is a stable node labelling.

Proof.

(1)

This follows from Lemma 65 and Lemma 66.

(2)

This follows from Lemma 67 and Lemma 68.

(3)

This follows from Lemma 72.

(4)

This follows from Lemma 73.

(5)

This follows from Lemma 74.

AFs with collective attacks vs. SETAFs

The concept of a SETAF (Definition 11) is very close to that of an Argumentation System in the sense of [42], which allows for collective attacks. However, where the SETAF arrows ( $a r r$ ) are a subset of $2^{N} \times N$ in Definition 11, they are a subset of $(2^{N} ∖ \emptyset) \times N$ in [42, Definition 1]. It is not completely clear why Nielsen and Parsons decided to rule out the empty set as a basis of an attack, since the well-definedness and correctness of their work does not seem to depend on it. An argument that is attacked by the empty set is always rejected (in labelling terms: it is always $o u t$ ) and has the same effects regarding the complete, grounded, preferred, semi-stable and stable extensions as if it does not exist at all. However, it can still have advantages to be able to represent such attacks, especially when it comes to the ability to model ABA. It is perfectly possible for an ABA-derivation not to use any assumptions at all, but still attack another ABA-derivation. Hence, if we want SETAFs to be abstractions of ABA, we need to be able to take into account attacks originating from the empty set.

In the following, we show that the difference between AFs with collective attacks and SETAFs is marginal. We show that each SETAF can be represented as AF with collective attacks without affecting the semantics. First, let us recall both definitions.

By definition, each AF with collective attacks is a SETAF.

To map each SETAF to an AF with collective attacks, we simply delete all nodes that are attacked by the empty set (and all attacks they were involved in).

The translation partitions the class of all SETAF into equivalence classes where each corresponds to a single AF with collective attacks.

Each AF with collective attacks $S F$ corresponds to an equivalence class $C_{S F}$ that contains each SETAF with additional arguments that are attacked by the empty set and additional attacks that involve arguments attacked by the empty set. Note that $S F$ is contained in the equivalence class $C_{S F}$ (it is the smallest SETAF contained in the class). For instance, the empty AF with collective attacks $(\emptyset, \emptyset)$ is the minimal representative of the equivalence class

\begin{aligned} C_{(\emptyset, \emptyset)} = {(N, a r r) | \forall A \in N : (\emptyset, A) \in a r r} . \end{aligned}

Interestingly, it can be the case that the empty set is stable in a given SETAF $S F = (N, a r r)$ although it contains nodes, i.e., $N \neq \emptyset$ . For instance, the SETAF $S F = (N, a r r)$ with $N = {A, B}$ and arrows $a r r = {(\emptyset, A), (\emptyset, B), ({A, B}, A)}$ admits an empty stable extension. We observe that the considered SETAF belongs to the equivalence class $C_{(\emptyset, \emptyset)}$ which gets mapped to the empty AF with collective attacks (it is well known that the empty set is stable in the empty framework).

We show that AF with collective attacks and SETAF semantics coincide.

Below, we make use of the following notation. For a SETAF $S F = (N, a r r)$ , we write

\begin{aligned} c f (S F) = {M \subseteq N | N is conflict-free in S F} . \end{aligned}

We obtain the following.

Differently phrased, all SETAFs in the same equivalence class coincide on the semantics.

From the one-to-one correspondence between extension semantics and labellings (cf. Theorem 58) and from Theorem 80, we obtain the following result. Theorem 82.

Let $S F = (N, a r r)$ be a SETAF, let $S E T A F 2 c o l l A F (S F) = {S F}^{'} = (N^{'}, {a r r}^{'})$ be its corresponding AF with collective attacks, and let $A_{\emptyset} = N ∖ N^{'}$ denote all nodes that are attacked by the empty set in $S F$ . Then,

for each SETAF node labelling $N L a b$ for $S F$ , let ${N L a b}^{'} = N L a b |_{N h^{'}}$ denote the SETAF node labelling restricted to ${S F}^{'}$ . It holds that

$N L a b$ is complete on $S F$ iff ${N L a b}^{'}$ is complete on ${S F}^{'}$ ;

$N L a b$ is grounded on $S F$ iff ${N L a b}^{'}$ is grounded on ${S F}^{'}$ ;

$N L a b$ is preferred on $S F$ iff ${N L a b}^{'}$ is preferred on ${S F}^{'}$ ;

$N L a b$ is stable on $S F$ iff ${N L a b}^{'}$ is stable on ${S F}^{'}$ ;

$N L a b$ is semi-stable on $S F$ iff ${N L a b}^{'}$ is semi-stable on ${S F}^{'}$ .

for each SETAF node labelling ${N L a b}^{'}$ for ${S F}^{'}$ , let $N L a b = N L a b \cup {(A, o u t) | A \in A_{\emptyset}}$ denote the extension of ${N L a b}^{'}$ to the set of nodes in $A_{\emptyset}$ (observe that each such node is assigned $o u t$ ). It holds that

${N L a b}^{'}$ is complete on ${S F}^{'}$ iff $N L a b$ is complete on $S F$ ;

${N L a b}^{'}$ is grounded on ${S F}^{'}$ iff $N L a b$ is grounded on $S F$ ;

${N L a b}^{'}$ is preferred on ${S F}^{'}$ iff $N L a b$ is preferred on $S F$ ;

${N L a b}^{'}$ is stable on ${S F}^{'}$ iff $N L a b$ is stable on $S F$ ;

${N L a b}^{'}$ is semi-stable on ${S F}^{'}$ iff $N L a b$ is semi-stable on $S F$ .

Proof.

We provide a proof for complete semantics. The remaining proofs are analogous.

First, let $N L a b$ be a complete labelling for $S F$ , and let ${N L a b}^{'} = N L a b |_{N h^{'}}$ denote the SETAF node labelling restricted to ${S F}^{'}$ . We show that $N L a b$ is complete on $S F$ iff ${N L a b}^{'}$ is complete on ${S F}^{'}$ : from left to right

By Theorem 58, $i n (N L a b)$ is a complete node extension of $S F$ . Moreover, by Theorem 80, $i n (N L a b)$ is a complete node extension of $M^{'}$ . Applying Theorem 58 again, we obtain that $i n (N L a b)$ induces a complete node labelling of ${S F}^{'}$ .

from right to left

Analogous to the other direction.

Now, let ${N L a b}^{'}$ be a complete node labelling for ${S F}^{'}$ and let $N L a b = N L a b \cup {(A, o u t) | A \in A_{\emptyset}}$ denote the extension of ${N L a b}^{'}$ to the set of nodes in $A_{\emptyset}$ . We show that ${N L a b}^{'}$ is complete on ${S F}^{'}$ iff $N L a b$ is complete on $S F$ : from left to right

By Theorem 58, $i n ({N L a b}^{'})$ is a complete node extension of ${S F}^{'}$ . By Theorem 80, $i n ({N L a b}^{'})$ is a complete node extension of $M$ . Applying Theorem 58 again, we obtain that $i n ({N L a b}^{'})$ induces a complete node labelling of $S F$ . Moreover, since each node $A \in A_{\emptyset}$ is attacked (by the empty set), we obtain that A is labelled $o u t$ , as desired.

from right to left

Analogous to the first case above (the restriction of a complete node labelling of $S F$ to ${S F}^{'}$ is complete).

Equivalence of arrow extensions and arrow labellings for argumentation frameworks

Equivalence of node extensions and arrow extensions for argumentation frameworks

We define the functions

\begin{aligned} A r g s 2 a = A L a b 2 a \circ N L a b 2 A L a b \circ A r g s 2 N L a b \end{aligned}

and

\begin{aligned} a 2 A r g s = A r g s 2 N L a b \circ A L a b 2 N L a b \circ A L a b 2 a . \end{aligned}

For semi-stable semantics, we consider the following counter-example: Example 91.

Let us recall the $A F = (N, a r r)$ from Example 10 with $N = {A, B, C, D, E, F}$ and $a r r = {(A, B), (C, B), (C, C), (A, D), (D, A), (D, E), (E, E), (E, F)}$ .

The AF has three complete node extensions $M_{1} = \emptyset$ , $M_{2} = {A}$ , and $M_{3} = {D, F}$ that are one-to-one related to the complete arrow extensions $a_{1} = \emptyset$ , $a_{2} = {(A, B), (A, D)}$ , and $a_{3} = {(D, A), (D, E)}$ via the functions $A r g s 2 a$ and $a 2 A r g s$ .

Let us see the function $A r g s 2 a = A L a b 2 a \circ N L a b 2 A L a b \circ A r g s 2 N L a b$ at work. Let us compute $A r g s 2 a (M_{2})$ in three steps:

\begin{aligned} A r g s 2 N L a b (M_{2}) = ({A}, {B, D}, {C, E, F}) \\ N L a b 2 A L a b (A r g s 2 N L a b (M_{2})) = ({(A, B), (A, D)}, {(D, A), (D, E)}, {(C, B), (C, C), \\ (E, E), (E, F)}) \\ A L a b 2 a (N L a b 2 A L a b (A r g s 2 N L a b (M_{2}))) = {(A, B), (A, D)} \end{aligned}

Hence, we obtain $A r g s 2 a (M_{2}) = a_{2}$ .

The set $M_{2}$ is the only semi-stable node extension of $A F$ . However, the set $a_{2}$ is not a semi-stable arrow extension since $a_{3} \cup a_{3}^{+} \supset a_{2} \cup a_{2}^{+}$ . Indeed, $a_{3}$ is the unique semi-stable arrow extension of $A F$ . On the other hand, $M_{3} = a 2 A r g s (a_{3})$ is not a semi-stable node extension.

Equivalence of arrow extensions and arrow labellings for SETAFs

Equivalence of node extensions and arrow extensions for SETAFs

In this section, we will provide proofs regarding the equivalence of node and arrow extensions. We recall the functions

\begin{aligned} A r g s 2 a = A L a b 2 a \circ N L a b 2 A L a b \circ A r g s 2 N L a b \end{aligned}

and

\begin{aligned} a 2 A r g s = A r g s 2 N L a b \circ A L a b 2 N L a b \circ A L a b 2 a . \end{aligned}

We note that the above result does not apply to semi-stable semantics. As a counter-example, we refer to Example 91.

Connection between argumentation frameworks and SETAFs

Recall Definition 22. As with AFs (see Definition 43), we can turn SETAF “inside out” as well. We want to emphasise that the resulting framework is still an AF, even if we turn a SETAF inside out. Moreover, note that the following result subsumes Theorem 44, as every AF can be seen as a SETAF.

The following theorem is a slightly reformulated version of Theorem 23 from Section 4, i.e., the following proof establishes Theorem 23.

Because of Theorem 100 (point 3) the well-behavedness of arrow labellings carries over from argumentation frameworks to SETAF: as arrow labellings are essentially node labellings (of the inside out argumentation framework) they satisfy the standard properties of node labellings described in the literature. Hence, Theorem 61 follows from [14, Definition 5, Definition 6 and Theorem 1], Lemma 62 follows from [14, Lemma 1], Lemma 63 follows from [16, Lemma 2] and Theorem 64 follows from [14, Theorem 6, Theorem 7].

ABA semantics reformulated

The way arguments are defined in Definition 27 is slightly different from the original definition in [22]. This means that even though the definition of a set of assumptions attacking an assumption (Definition 30 is the same as the notion of attack in the ABA literature [22], our definition of attack refers to a different kind of argument and is therefore slightly different. We now show that nevertheless the two notions of attack coincide and that therefore the derived concepts of defence and semantics are equivalent no matter which notion of argument is used.

Since arguments in [22] are derivation trees as given in Definition 26, the equivalence results will be given in terms of arguments and derivations as given in Definitions 27 and 26, respectively.

We now proceed to prove that the semantics in ABA are equivalent no matter whether the notion of ABA arguments or derivation trees is used in the definition.

As mentioned in Section 5, the way preferred and stable semantics in the context of ABAFs were defined in Definition 31 is slightly different from the way these were originally defined in [10,22]. We have chosen to describe all ABA semantics in a uniform way, based on the notion of complete semantics. This has been done to allow for easy conversion between extensions and labellings, as well as to provide uniformity with the rest of the paper.

We will now proceed to show that our description of the ABA semantics in Definition 31 is equivalent to the original description in [10,22]. Since the notion of admissible sets and complete extensions are simply reformulations of the definitions in [10,22] in terms of the function F introduced here, we start with proving equivalence for the preferred semantics.

The next thing to show is that our description of stable semantics (Definition 31) is equivalent with the way stable semantics was originally defined in [10].

Using the lemmas and theorems provided in this section, we will now prove Theorem 32 from Section 5.

In the following, we investigate how the slightly altered notion of ABA-arguments (Definition 27 influences the associated AF as compared to [22]. Since arguments in [22] are equivalent to derivation trees in Definition 26, we will prove the results in terms of derivation trees. However, exactly the same results hold with respect to arguments as defined in [22].

Note that Definition 105 is equivalent to the notion of attack in [22].

Definition 106 is equivalent to the associated AF as defined in [22].

Notes

References

Amgoud

Cayrol

, On the acceptability of arguments in preference-based argumentation framework, in: Proceedings of UAI 1998, 1998, pp. 1–7.

Baroni

Caminada

M.W.A.

Giacomin

, An introduction to argumentation semantics, Knowledge Engineering Review 26(4) (2011), 365–410. doi:10.1017/S0269888911000166.

Baroni

Giacomin

, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171(10–15) (2007), 675–700.

Baroni

Giacomin

Guida

, scc-recursiveness: A general schema for argumentation semantics, Artificial Intelligence 168(1–2) (2005), 165–210.

Baumann

Brewka

Ulbricht

, Shedding new light on the foundations of abstract argumentation: Modularization and weak admissibility, Artificial Intelligence 310 (2022), 103742. doi:10.1016/j.artint.2022.103742.

Baumann

Strass

, On the maximal and average numbers of stable extensions, in: Proceedings of TAFA 2013, LNCS, Vol. 8306, Springer, 2013, pp. 111–126. doi:10.1007/978-3-642-54373-9_8.

Bench-Capon

T.J.M.

, Persuasion in practical argument using value-based argumentation frameworks, Journal of Logic and Computation 13(3) (2003), 429–448. doi:10.1093/logcom/13.3.429.

Bikakis

Cohen

Dvořák

Flouris

Parsons

, Joint attacks and accrual in argumentation frameworks, FLAP 8(6) (2021), 1437–1501, https://collegepublications.co.uk/ifcolog/?00048 .

Boella

Gabbay

D.M.

van der Torre

L.W.N.

Villata

, Meta-argumentation modelling I: Methodology and techniques, Studia Logica 93(2–3) (2009), 297–355. doi:10.1007/s11225-009-9213-2.

10.

Bondarenko

Dung

P.M.

Kowalski

R.A.

Toni

, An abstract, argumentation-theoretic approach to default reasoning, Artificial Intelligence 93 (1997), 63–101. doi:10.1016/S0004-3702(97)00015-5.

11.

Caminada

M.W.A.

, On the issue of reinstatement in argumentation, in: Proceedings of JELIA 2006, LNAI 4160, Springer, 2006, pp. 111–123.

12.

Caminada

M.W.A.

, Comparing two unique extension semantics for formal argumentation: Ideal and eager, in: Proceedings of BNAIC 2007, 2007, pp. 81–87.

13.

Caminada

M.W.A.

Amgoud

, On the evaluation of argumentation formalisms, Artificial Intelligence 171(5–6) (2007), 286–310.

14.

Caminada

M.W.A.

Gabbay

D.M.

, A logical account of formal argumentation, Studia Logica 93(2–3) (2009), 109–145. Special issue: new ideas in argumentation theory.

15.

Caminada

M.W.A.

Sá

Alcântara

, On the equivalence between logic programming semantics and argumentation semantics, in: Proceedings of ECSQARU 2013, 2013, pp. 97–108.

16.

Caminada

M.W.A.

Sá

Alcântara

Dvořák

, On the equivalence between logic programming semantics and argumentation semantics, International Journal of Approximate Reasoning 58 (2015), 87–111. doi:10.1016/j.ijar.2014.12.004.

17.

Caminada

M.W.A.

Sá

Alcântara

Dvořák

, On the difference between assumption-based argumentation and abstract argumentation, IfCoLog Journal of Logic and its Applications 2 (2015), 15–34.

18.

Cayrol

Lagasquie-Schiex

, On the acceptability of arguments in bipolar argumentation frameworks, in: Proceedings of ECSQARU 2005, LNCS, Vol. 3571, Springer, 2005, pp. 378–389.

19.

Čyras

Fan

Schulz

Toni

, Assumption-based argumentation: Disputes, explanations, preferences, in: Handbook of Formal Argumentation, Vol. 1, College Publications, 2018, pp. 365–408.

20.

Dung

P.M.

, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77(2) (1995), 321–357. doi:10.1016/0004-3702(94)00041-X.

21.

Dung

P.M.

Kowalski

R.A.

Toni

, Assumption-based argumentation, in: Argumentation in Artificial Intelligence, Simari

Rahwan

, eds, Springer US, 2009, pp. 199–218. ISBN 978-0-387-98196-3. doi:10.1007/978-0-387-98197-0_10.

22.

Dung

P.M.

Mancarella

Toni

, Computing ideal sceptical argumentation, Artificial Intelligence 171(10–15) (2007), 642–674.

23.

Dunne

P.E.

Dvořák

Linsbichler

Woltran

, Characteristics of multiple viewpoints in abstract argumentation, Artificial Intelligence 228 (2015), 153–178. doi:10.1016/j.artint.2015.07.006.

24.

Dvořák

Fandinno

Woltran

, On the expressive power of collective attacks, Argument & Computation 10(2) (2019), 191–230. doi:10.3233/AAC-190457.

25.

Dvořák

Gaggl

S.A.

, Stage semantics and the SCC-recursive schema for argumentation semantics, Journal of Logic and Computation 26(4) (2016), 1149–1202. doi:10.1093/logcom/exu006.

26.

Dvořák

Greßler

Woltran

, Evaluating SETAFs via answer-set programming, in: Proceedings of SAFA 2018, CEUR Workshop Proceedings, Vol. 2171, CEUR-WS.org2018, pp. 10–21, http://ceur-ws.org/Vol-2171/paper_2.pdf .

27.

Dvořák

König

Ulbricht

Woltran

, Principles and their computational consequences for argumentation frameworks with collective attacks, Journal of Artificial Intelligence Research 79 (2024), 69–136. doi:10.1613/jair.1.14879.

28.

Dvořák

König

Woltran

, On the complexity of preferred semantics in argumentation frameworks with bounded cycle length, in: Proceedings of KR 2021, 2021, pp. 671–675. doi:10.24963/kr.2021/67.

29.

Dvořák

König

Woltran

, Deletion-backdoors for argumentation frameworks with collective attacks, in: Proceedings of SAFA 2022, Vol. 3236, 2022, pp. 98–110, http://ceur-ws.org/Vol-3236/paper8.pdf .

30.

Dvořák

König

Woltran

, Treewidth for argumentation frameworks with collective attacks, in: Proceedings of COMMA 2022, FAIA, Vol. 353, IOS Press, 2022, pp. 140–151.

31.

Dvořák

Rapberger

Wallner

J.P.

, Labelling-based algorithms for SETAFs, in: Proceedings of SAFA 2020, CEUR Workshop Proceedings, Vol. 2672, CEUR-WS.org, 2020, pp. 34–46, https://ceur-ws.org/Vol-2672/paper_4.pdf .

32.

Dvořák

Rapberger

Woltran

, On the different types of collective attacks in abstract argumentation: Equivalence results for SETAFs, Journal of Logic and Computation 30(5) (2020), 1063–1107. doi:10.1093/logcom/exaa033.

33.

Dvořák

Rapberger

Woltran

, Argumentation semantics under a claim-centric view: Properties, expressiveness and relation to SETAFs, in: Proceedings of KR 2020, 2020, pp. 341–350. doi:10.24963/kr.2020/35.

34.

Dvořák

Rapberger

Woltran

, A claim-centric perspective on abstract argumentation semantics: Claim-defeat, principles, and expressiveness, Artificial Intelligence 324 (2023), 104011. doi:10.1016/J.ARTINT.2023.104011.

35.

Flouris

Bikakis

, A comprehensive study of argumentation frameworks with sets of attacking arguments, International Journal of Approximate Reasoning 109 (2019), 55–86. doi:10.1016/j.ijar.2019.03.006.

36.

Gabbay

D.M.

, Semantics for higher level attacks in extended argumentation frames part 1: Overview, Stud Logica 93(2–3) (2009), 357–381. doi:10.1007/s11225-009-9211-4.

37.

García

A.J.

Dix

Simari

G.R.

, Argument-based logic programming, in: Argumentation in Artificial Intelligence, Simari

Rahwan

, eds, Springer US, 2009, pp. 153–171. ISBN 978-0-387-98196-3. doi:10.1007/978-0-387-98197-0_8.

38.

Governatori

Maher

M.J.

Antoniou

Billington

, Argumentation semantics for defeasible logic, Journal of Logic and Computation 14(5) (2004), 675–702. doi:10.1093/logcom/14.5.675.

39.

König

Rapberger

Ulbricht

, Just a matter of perspective – intertranslating expressive argumentation formalisms, in: Proceedings of COMMA 2022, FAIA, Vol. 353, IOS Press, 2022, pp. 212–223.

40.

Modgil

Prakken

, A general account of argumentation with preferences, Artificial Intellligence 195 (2013), 361–397. doi:10.1016/j.artint.2012.10.008.

41.

Modgil

Prakken

, Abstract rule-based argumentation, in: Handbook of Formal Argumentation, Vol. 1, College Publications, 2018, pp. 287–364.

42.

Nielsen

S.H.

Parsons

, A generalization of Dung’s abstract framework for argumentation: Arguing with sets of attacking arguments, in: Proceedings of ArgMAS 2006, LNAI, Vol. 4766, 2006, pp. 54–73.

43.

Polberg

, Developing the abstract dialectical framework, PhD thesis, Vienna University of Technology, Institute of Information Systems, 2017.

44.

Prakken

, An abstract framework for argumentation with structured arguments, Argument & Computation 1(2) (2010), 93–124. doi:10.1080/19462160903564592.

45.

Rapberger

, Defining argumentation semantics under a claim-centric view, in: Proceedings of STAIRS 2020, CEUR Workshop Proceedings, Vols 2655, CEUR-WS.org, 2020, https://ceur-ws.org/Vol-2655/paper2.pdf .

46.

Rapberger

Ulbricht

, On dynamics in structured argumentation formalisms, Journal of Artificial Intelligence Research 77 (2023), 563–643. doi:10.1613/JAIR.1.14481.

47.

Schultz

Toni

, Complete assumption labellings, in: Proceedings of COMMA 2014, 2014, pp. 405–412.

48.

Simari

G.R.

Loui

R.P.

, A mathematical treatment of defeasible reasoning and its implementation, Artificial Intelligence 53 (1992), 125–157. doi:10.1016/0004-3702(92)90069-A.

49.

Toni

, Reasoning on the web with assumption-based argumentation, in: Reasoning Web. Semantic Technologies for Advanced Query Answering, Eiter

Krennwallner

, eds, 2012, pp. 370–386. doi:10.1007/978-3-642-33158-9_10.

50.

Ulbricht

, On the maximal number of complete extensions in abstract argumentation frameworks, in: Proceedings of KR 2021, 2021, pp. 707–711. doi:10.24963/kr.2021/74.

51.

Verheij

, Two approaches to dialectical argumentation: Admissible sets and argumentation stages, in: Proceedings of NAIC 1996, 1996, pp. 357–368.

52.

Villata

Boella

van der Torre

, Attack semantics for abstract argumentation, in: Proceedings of IJCAI 2011, 2011, pp. 164–171.

53.

Vreeswijk

G.A.W.

, Abstract argumentation systems, Artificial Intelligence 90 (1997), 225–279. doi:10.1016/S0004-3702(96)00041-0.

54.

Caminada

M.W.A.

Gabbay

D.M.

, Complete extensions in argumentation coincide with 3-valued stable models in logic programming, Studia Logica 93(1–2) (2009), 383–403. Special issue: new ideas in argumentation theory.