Attack semantics and collective attacks revisited

Caminada, Martin; König, Matthias; Rapberger, Anna; Ulbricht, Markus

doi:10.3233/AAC-230011

Attack semantics and collective attacks revisited

Article type: Research Article

Authors: Caminada, Martin^{a; *} | König, Matthias^b | Rapberger, Anna^c | Ulbricht, Markus^d

Affiliations: [a] Cardiff University, United Kingdom | [b] Institute of Logic and Computation, TU Wien, Austria | [c] Department of Computing, Imperial College London, United Kingdom | [d] ScaDS.AI, Department of Computer Science, Leipzig University, Germany

Correspondence: [*] Corresponding author. E-mail: CaminadaM@cardiff.ac.uk.

Keywords: Abstract argumentation, assumption-based argumentation, attack semantics, collective attacks

DOI: 10.3233/AAC-230011

Journal: Argument & Computation, vol. Pre-press, no. Pre-press, pp. 1-77, 2024

Published: 25 March 2024

Get PDF

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.

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.1 1 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 (arr). For current purposes, we restrict ourselves to finite argumentation frameworks.

Definition 1.

An argumentation framework is a pair (N,arr) where N is a finite set of nodes (called arguments) whose internal structure can be left implicit, and arr⊆N×N.

We will commonly refer to the elements of arr as the arrows of the argumentation framework. We say that A∈N attacks B∈N iff (A,B)∈arr. 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,arr) be an argumentation framework, M⊆N and B∈N. We say that M attacks B iff ∃A∈M:(A,B)∈arr. We say that M1⊆N attacks M2⊆N iff M1 attacks some B∈M2. We define M+ as {A∈N|M attacks A}. We say that M is conflict-free iff M∩M+=∅. We say that M defends A iff each B⊆N that attacks A is attacked by M. We define the function F:2N→2N as follows: F(M)={A∈N|A is defended by M}.

Definition 3.

Let (N,arr) be an argumentation framework. A set of nodes M⊆N is called:

(1) an admissible set iff M is conflict-free and M⊆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∪M+ is maximal (w.r.t. ⊆) among all complete extensions
(6) a stable extension iff M is a complete extension with M∪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,arr) be an argumentation framework. A node labelling is a function NLab:N→{in,out,undec}. A node labelling NLab is called admissible iff for each A∈N:

if NLab(A)=in then for each B∈N such that (B,A)∈arr it holds that NLab(B)=out
if NLab(A)=out then there exists a B∈N such that (B,A)∈arr and NLab(B)=in

A node labelling NLab is called complete iff it is admissible and also satisfies for each A∈N:

if NLab(A)=undec then not for each B∈N such that (B,A)∈arr it holds that NLab(B)=out, and there does not exists a B∈N such that (B,A)∈arr and NLab(B)=in

As a convention, we write in(NLab) for {A∈N|NLab(A)=in}, out(NLab) for {A∈N|NLab(A)=out} and undec(NLab) for {A∈N|NLab(A)=undec}. A complete node labelling NLab is called:

(1) grounded iff in(NLab) is minimal (w.r.t. ⊆) among all complete node labellings
(2) preferred iff in(NLab) is maximal (w.r.t. ⊆) among all complete node labellings
(3) semi-stable iff undec(NLab) is minimal (w.r.t. ⊆) among all complete node labellings
(4) stable iff undec(NLab)=∅

As a node labelling essentially defines a partition, we sometimes write it as a triple (in(NLab), out(NLab), undec(NLab)).

It has been shown that the complete node labellings with maximal in are equal to the complete node labellings with maximal out [14], and that the complete node labelling where in is minimal is unique and equal to both the complete node labelling where out is minimal and the complete node labelling where undec 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 in	preferred
maximal out	preferred
maximal undec	grounded
minimal in	grounded
minimal out	grounded
minimal undec	semi-stable
no undec	stable

As was pointed out in [14], for the semantics we consider labellings and extensions are one-to-one related through the functions NLab2Args and Args2NLab, where

NLab2Args(NLab)=in(NLab),andArgs2NLab(M)=(M,M+,N∖(M∪M+))2.

2 That is, if NLab is a complete (resp. grounded, preferred, semi-stable or stable) node labelling, then NLab2Args(NLab) 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 Args2NLab(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) NLab2Args and Args2NLab 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 Args2NLab and NLab2Args

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

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,arr) be an argumentation framework, a⊆arr and (A,B)∈arr. We say that a attacks (A,B) iff (C,A)∈a for some C∈N. We say that a1⊆arr attacks a2⊆arr iff a1 attacks some element of a2. We define a+ as {(C,D)∈arr|a attacks (C,D)}. We say that a is conflict-free iff a∩a+=∅. We say that a defends (A,B) iff each (C,A)∈arr is attacked by a. We define the function F:2arr→2arr as follows: F(a)={(A,B)∈arr|(A,B) is defended by a}.

Definition 6.

Let (N,arr) be an argumentation framework. a⊆arr is called:

(1) an admissible set iff a is conflict-free and a⊆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∪a+ is maximal (w.r.t. ⊆) among all complete extensions
(6) a stable extension iff a is a complete extension with a∪a+=arr

An alternative way of defining arrow semantics is by applying labellings, as is done in the following definition.3 3

Definition 7.

Let (N,arr) be an argumentation framework. An arrow labelling is a function ALab:arr→{in,out,undec}. An arrow labelling ALab is called admissible iff for each (A,B)∈arr:

if ALab((A,B))=in then for each (C,A)∈arr it holds that ALab((C,A))=out
if ALab((A,B))=out then there exists a (C,A)∈arr such that ALab((C,A))=in

An arrow labelling ALab is called complete iff it is admissible and also satisfies for each (A,B)∈arr:

if ALab((A,B))=undec then not for each (C,A)∈arr it holds that ALab((C,A))=out, and there does not exist a (C,A)∈arr such that ALab((C,A))=in

As a convention, we write in(ALab) for {(A,B)∈arr|ALab((A,B))=in}, out(ALab) for {(A,B)∈arr|ALab((A,B))=out} and undec(ALab) for {(A,B)∈arr|ALab((A,B))=undec}. A complete arrow labelling ALab is called:

(1) grounded iff in(ALab) is minimal (w.r.t. ⊆) among all complete arrow labellings
(2) preferred iff in(ALab) is maximal (w.r.t. ⊆) among all complete arrow labellings
(3) semi-stable iff undec(ALab) is minimal (w.r.t. ⊆) among all complete arrow labellings
(4) stable iff undec(ALab)=∅

As an arrow labelling essentially defines a partition, we sometimes write it as a triple (in(ALab), out(ALab), undec(ALab)).

It can be shown that the complete arrow labellings with maximal in are equal to the complete arrow labellings with maximal out (Appendix A) and that the complete arrow labelling where in is minimal is unique and equal to both the complete arrow labelling where out is minimal and the complete arrow labelling where undec 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 in	preferred
maximal out	preferred
maximal undec	grounded
minimal in	grounded
minimal out	grounded
minimal undec	semi-stable
no undec	stable

It can be shown that arrow extensions and arrow labellings are one-to-one related through the functions ALab2a and a2ALab, where

ALab2a(ALab)=in(ALab),anda2ALab(a)=(a,a+,arr∖(a∪a+))4.

4 If ALab is a complete (resp. grounded, preferred, semi-stable or stable) arrow labelling, then ALab2a(ALab) 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 a2ALab(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) ALab2a and a2ALab 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 a2ALab and ALab2a

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

It turns out that arrow labellings and node labellings are one-to-one related through the functions ALab2NLab and NLab2ALab, where

ALab2NLab(ALab)=({A∈N|∀(B,A)∈arr:ALab((B,A))=out},{A∈N|∃(B,A)∈arr:ALab((B,A))=in},{A∈N|¬∀(B,A)∈arr:ALab((B,A))=out and ¬∃(B,A)∈arr:ALab((B,A))=in}),NLab2ALab(NLab)=({(A,B)∈arr|NLab(A)=in},{(A,B)∈arr|NLab(A)=out},{(A,B)∈arr|NLab(A)=undec}).

It can be shown that if ALab is a complete (resp. grounded, preferred or stable) arrow labelling, then ALab2NLab is a complete (resp. grounded, preferred or stable) node labelling, and if NLab is a complete (resp. grounded, preferred, semi-stable or stable) node labelling, then NLab2ALab(NLab) 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) ALab2NLab and NLab2ALab 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 NLab2ALab and ALab2NLab

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 AF=(N,arr) be an argumentation framework and let NLab and ALab be a node labelling and an arrow labelling of AF, respectively. It holds that:

(1) If NLab is a complete node labelling, then NLab2ALab(NLab) is a complete arrow labelling.
If ALab is a complete arrow labelling, then ALab2NLab(ALab) is a complete node labelling.
(2) When restricted to complete node labellings and complete arrow labellings, the functions ALab2NLab and NLab2ALab become bijections and each other’s inverses.
(3) If NLab is a grounded node labelling, then NLab2ALab(NLab) is a grounded arrow labelling.
If ALab is a grounded arrow labelling, then ALab2NLab(ALab) is a grounded node labelling.
(4) If NLab is a preferred node labelling, then NLab2ALab(NLab) is a preferred arrow labelling.
If ALab is a preferred arrow labelling, then ALab2NLab(ALab) is a preferred node labelling.
(5) If NLab is a stable node labelling, then NLab2ALab(NLab) is a stable arrow labelling.
If ALab is a stable arrow labelling, then ALab2NLab(ALab) 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 out and undec.

Example 9.

Let AF=(N,arr) be an argumentation framework with N={A,B,C,D} and arr={(A,A),(A,C),(B,D),(D,B),(D,C)}.

AF has three complete node labellings:

NLab1=(∅,∅,{A,B,C,D})NLab2=({B},{D},{A,C})NLab3=({D},{B,C},{A})

and three complete arrow labellings:

ALab1=(∅,∅,{(A,A),(A,C),(B,D),(D,B),(D,C)})ALab2=({(B,D)},{(D,B),(D,C)},{(A,A),(A,C)})ALab3=({(D,B),(D,C)},{(B,D)},{(A,A),(A,C)})

These node labellings and arrow labellings correspond to each other through the functions NLab2ALab and ALab2NLab. While ALab2 is a semi-stable arrow labelling, NLab2=ALab2NLab(ALab2) is not a semi-stable node labelling (the only semi-stable node labelling is NLab3).

Example 10.

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

AF has three complete node labellings:

NLab1=(∅,∅,{A,B,C,D,E,F})NLab2=({A},{B,D},{C,E,F})NLab3=({D,F},{A,E},{B,C})

and three complete arrow labellings:

ALab1=(∅,∅,{(A,B),(C,B),(C,C),(A,D),(D,A),(D,E),(E,E),(E,F)})ALab2=({(A,B),(A,D)},{(D,A),(D,E)},{(C,B),(C,C),(E,E),(E,F)})ALab3=({(D,A),(D,E)},{(A,B),(A,D),(E,E),(E,F)},{(C,B),(C,C)})

These node labellings and arrow labellings correspond to each other through the functions NLab2ALab and ALab2NLab. While NLab2 is a semi-stable node labelling, ALab2=NLab2ALab(NLab2) is not a semi-stable arrow labelling (the only semi-stable arrow labelling is ALab3).

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

Args2a=ALab2a∘NLab2ALab∘Args2NLab,anda2Args=Args2NLab∘ALab2NLab∘ALab2a.

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 SF=(N,arr) where N is a finite set of nodes, whose structure can be left implicit, and arr⊆2N×N.

As for AFs, we refer to the elements of N as the nodes and to the elements of arr as the arrows of the SETAF. Moreover, we say M attacks A iff (M,A)∈arr. Consider the following example for an illustration.

Example 12.

Consider the following SETAF SF=(N,arr) with

N={A,B,C,D,E,F},arr={(∅,A),({A},B),({B,C},E),({C,F},E),({C},F),({D},B),({E},D),({F},C)}.

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,arr) where N is a finite set of nodes and arr⊆(2N∖∅)×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 SF=(N,arr), if we simply delete all nodes A∈N with (∅,A)∈arr and all arrows (M,B) where either A∈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 SF.

Remark 14.

Note that (with a slight abuse of notation) every AF can be seen as a SETAF (cf. [42]): let AF=(N,arr) be an AF, the corresponding SETAF SFAF is defined as SFAF=(N,{({A},B)|(A,B)∈arr}). 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 SF=(N,arr) be a SETAF, M⊆N and A∈N. We say that M attacks A iff ∃M′⊆M:(M′,A)∈arr. We say that M1⊆N attacks M2⊆N iff M1 attacks some B∈M2. We define MSF+ as {A∈N|M attacks A}. We say that M is conflict-free iff M∩MSF+=∅. We write cf(SF)={Mh⊆N|M∩MSF+=∅} to denote the set of conflict-free sets. We say that M defends A iff for each M′⊆N that attacks A, M attacks M′. We define the characteristic function FSF:2N→2N with FSF(M)={A∈N|A is defended by M}. We omit subscript SF if it is clear from the context.

Definition 16

Definition 16([35,42]).

Let (N,arr) be a SETAF. M⊆N is called:

(1) an admissible set iff M is conflict-free and M⊆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∪M+ is maximal (w.r.t. ⊆) among all complete extensions
(6) a stable extension iff M is a complete extension where M∪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

Definition 17([35]).

Let (N,arr) be a SETAF. A SETAF node labelling is a function NLab:N→{in,out,undec}. A SETAF node labelling NLab is called admissible iff for each A∈N:

if NLab(A)=in then for each M⊆N such that (M,A)∈arr it holds that ∃B∈M:NLab(B)=out
if NLab(A)=out then there exists an M⊆N such that (M,A)∈arr and ∀B∈M:NLab(B)=in

A SETAF node labelling NLab is called complete iff it is admissible and also satisfies for each A∈N:

if NLab(A)=undec then not for each M⊆N such that (M,A)∈arr it holds that ∃B∈M:NLab(B)=out and there does not exist an M⊆N such that (M,A)∈arr and ∀B∈M:NLab(B)=in

As a convention, we write in(NLab) for {A∈N|NLab(A)=in}, out(NLab) for {A∈N|NLab(A)=out} and undec(NLab) for {A∈N|NLab(A)=undec}. A complete SETAF node labelling NLab is called:

(1) grounded iff in(NLab) is minimal (w.r.t. ⊆) among all complete SETAF node labellings
(2) preferred iff in(NLab) is maximal (w.r.t. ⊆) among all complete SETAF node labellings
(3) semi-stable iff undec(NLab) is minimal (w.r.t. ⊆) among all complete SETAF node labellings
(4) stable iff undec(NLab)=∅

As a SETAF node labelling essentially defines a partition, we sometimes write it as a triple (in(NLab), out(NLab), undec(NLab)).

It can been shown that the complete SETAF node labellings with maximal in are equal to the complete SETAF node labellings with maximal out (see Appendix D) and that the complete SETAF node labelling where in is minimal is unique and equal to both the complete SETAF node labelling where out is minimal and the complete SETAF node labelling where undec 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 in	preferred
maximal out	preferred
maximal undec	grounded
minimal in	grounded
minimal out	grounded
minimal undec	semi-stable
no undec	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 NLab2Args and Args2NLab, where

NLab2Args(NLab)=in(NLab),andArgs2NLab(M)=(M,M+,N∖(M∪M+))5.

5 If NLab is a complete (resp. grounded, preferred, semi-stable or stable) SETAF node labelling, then NLab2Args(NLab) 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 Args2NLab(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) NLab2Args and Args2NLab 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 Args2NLab and NLab2Args

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

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,arr) be a SETAF, a⊆arr and (M,A)∈arr. We say that a attacks (M,A) iff (M′,B)∈a with B∈M for some M′⊆N. We say that a1⊆arr attacks a2⊆arr iff a1 attacks some element of a2. We define a+ as {(M,A)∈arr|a attacks (M,A)}. We say that a is conflict-free iff a∩a+=∅. We say that a defends (M,A) iff each (M′,B)∈arr with B∈M is attacked by a. We define the function F:2arr→2arr as follows: F(a)={(M,A)∈arr|(M,A) is defended by a}.

Definition 19.

Let (N,arr) be a SETAF. a⊆arr is called:

(1) an admissible set iff a is conflict-free and a⊆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∪a+ is maximal (w.r.t. ⊆) among all complete extensions
(6) a stable extension iff a is a complete extension with a∪a+=arr

An alternative way of defining arrow semantics for SETAF is by applying labellings, as is done in the following definition.

Definition 20.

Let (N,arr) be a SETAF. A SETAF arrow labelling is a function ALab:arr→{in,out,undec}. A SETAF arrow labelling ALab is called admissible iff for each (M,A)∈arr:

if ALab((M,A))=in then for each (M′,B)∈arr such that B∈M it holds that ALab((M′,B))=out
if ALab((M,A))=out then there exists an (M′,B)∈arr such that B∈M and ALab((M′,B))=in

A SETAF arrow labelling ALab is called complete iff it is admissible and satisfies for each (M,A)∈arr:

if ALab((M,A))=undec then not for each (M′,B)∈arr such that B∈M it holds that ALab((M′,B))=out and there does not exist an (M′,B)∈arr such that B∈M and ALab((M′,B))=in

As a convention, we write in(ALab) for {(M,A)∈arr|ALab((M,A))=in}, out(ALab) for {(M,A)∈arr|ALab((M,A))=out} and undec(ALab) for {(M,A)∈arr|ALab((M,A))=undec}. A complete SETAF arrow labelling ALab is called:

(1) grounded iff in(ALab) is minimal (w.r.t. ⊆) among all complete SETAF arrow labellings
(2) preferred iff in(ALab) is maximal (w.r.t. ⊆) among all complete SETAF arrow labellings
(3) semi-stable iff undec(ALab) is minimal (w.r.t. ⊆) among all complete SETAF arrow labellings
(4) stable iff undec(ALab)=∅

As a SETAF arrow labelling essentially defines a partition, we sometimes write it as a triple (in(ALab), out(ALab), undec(ALab)).

It can be shown that the complete arrow labellings with maximal in are equal to the complete arrow labellings with maximal out (Appendix E) and that the complete arrow labelling where in is minimal is unique and equal to both the complete arrow labelling where out is minimal and the complete arrow labelling where undec 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 ALab2a and a2ALab, where

ALab2a(ALab)=in(ALab),a2ALab(a)=(a,a+,arr∖(a∪a+))6.

Table 9

Implementing different conditions on complete arrow labellings of SETAF

Condition on arrow labelling	Resulting semantics
maximal in	preferred
maximal out	preferred
maximal undec	grounded
minimal in	grounded
minimal out	grounded
minimal undec	semi-stable
no undec	stable

If ALab is a complete (resp. grounded, preferred, semi-stable or stable) arrow labelling, then ALab2a(ALab) 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 a2ALab(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) ALab2a and a2ALab 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 a2ALab and ALab2a

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

It can be shown that SETAF arrow labellings and SETAF node labellings are one-to-one related through the functions ALab2NLab and NLab2ALab, where

ALab2NLab(ALab)=({A∈N|∀(M,A)∈arr:ALab((M,A))=out},{A∈N|∃(M,A)∈arr:ALab((M,A))=in},{A∈N|¬∀(M,A)∈arr:ALab((M,A))=out and ¬∃(M,A)∈arr:ALab((M,A))=in}),NLab2ALab(NLab)=({(M,A)∈arr|∀B∈M:NLab(B)=in},{(M,A)∈arr|∃B∈M:NLab(B)=out},{(M,A)∈arr|¬∀B∈M:NLab(B)=in and ¬∃B∈M:NLab(B)=out}).

It can be shown that if ALab is a complete (resp. grounded, preferred, semi-stable or stable) SETAF arrow labelling, then ALab2NLab(ALab) is a complete (resp. grounded, preferred or stable) SETAF node labelling, and if NLab is a complete (resp. grounded, preferred or stable) node labelling, then NLab2ALab(NLab) 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) ALab2NLab and NLab2ALab 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 SF=(N,arr) be a SETAF and let NLab and ALab be a node labelling and an arrow labelling of SF, respectively. It holds that:

(1) If NLab is a complete node labelling, then NLab2ALab(NLab) is a complete arrow labelling.
If ALab is a complete arrow labelling, then ALab2NLab(ALab) is a complete node labelling.
(2) When restricted to complete node labellings and complete arrow labellings, the functions ALab2NLab and NLab2ALab become bijections and each other’s inverses.
(3) If NLab is a grounded node labelling, then NLab2ALab(NLab) is a grounded arrow labelling.
If ALab is a grounded arrow labelling, then ALab2NLab(ALab) is a grounded node labelling.
(4) If NLab is a preferred node labelling, then NLab2ALab(NLab) is a preferred arrow labelling.
If ALab is a preferred arrow labelling, then ALab2NLab(ALab) is a preferred node labelling.
(5) If NLab is a stable node labelling, then NLab2ALab(NLab) is a stable arrow labelling.
If ALab is a stable arrow labelling, then ALab2NLab(ALab) is a stable node labelling.

Table 11

The relation between node labellings and arrow labellings of SETAFs, through NLab2ALab and ALab2NLab

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

Args2a=ALab2a∘NLab2ALab∘Args2NLab,a2Args=Args2NLab∘ALab2NLab∘ALab2a.

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

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 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 SF=(N,arr) be a SETAF. We define the associated inside-out argumentation framework AFSF as (N,arr) with N=arr and arr={((M1,A1),(M2,A2))|(M1,A1),(M2,A2)∈arr and A1∈M2}

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 SF=(N,arr) be a SETAF and AFSF=(N,arr) be the associated argumentation framework. It holds that ALab is a complete (resp. grounded, preferred, semi-stable or stable) SETAF arrow labelling of SF iff ALab is a complete (resp. grounded, preferred, semi-stable or stable) node labelling of AFSF.

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 NLab2ALab and ALab2NLab, 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 SF and node labellings of its corresponding inside-out framework AFSF

Arrow labelling of SF	Relation	Node labelling of AFSF
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 SF=(N,arr) from Example 12 (see (a)). The associated inside-out argumentation framework is AFSF=(N,arr) with

N={(∅,A),({A},B),({B,C},E),({C,F},E),({C},F),({D},B),({E},D),({F},C)}.arr={((∅,A),({A},B)),(({A},B),({B,C},E)),(({B,C},E),({E},D)),arr=(({D},B),({B,C},E)),(({F},C),({B,C},E)),(({E},D),({D},B)),(({F},C),arr=({C},F)),(({F},C),({C,F},E)),(({C},F),({F},C)),(({C},F),({C,F},E)),arr=(({C,F},E),({E},D))}

SF has three complete arrow labellings:

ALab1=({(∅,A)},{({A},B)},{({B,C},E),({C,F},E),({C},F),({D},B),({E},D),({F},C)})ALab2=({(∅,A),({F},C),({E},D)},{({A},B),({C},F),({D},B),({B,C},E),({C,F},E)},∅)ALab3=({(∅,A),({C},F)},{({A},B),({F},C),({C,F},E)},{({B,C},E),({D},B),({E},D)})

AFSF has three complete node labellings:

NLab1=ALab1,NLab2=ALab2,NLab3=ALab3

5.Instantiating AFs and SETAFs using ABA

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

Definition 25([21]).

An ABAF is a tuple D=(L,R,A,a‾) 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⊆L is a (non-empty) set of assumptions,
a‾ is the contrary function, i.e., a total mapping from A into L; α‾ 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

Definition 26([21]).

Given an ABAF D=(L,R,A,a‾), a derivation tree for c∈L (the conclusion or claim) supported by Asms⊆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←b1,…,bm (m⩾0) and either m=0 and the child of N is labelled by ⊤, or m>0 and N has m children, labelled by b1,…,bm respectively
Asms(t) is the set of all assumptions labelling the leaves

We denote by cl(t)=c the conclusion of t.

Note that for each assumption γ∈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,a‾), an ABA-argument is a pair (Asms,c) where Asms⊆A and c∈L such that there is a derivation tree t with cl(t)=c and Asms(t)=Asms. We say that an ABA-argument (Asms1,c1) attacks an ABA-argument (Asms2,c2) iff c1=γ¯ for some γ∈Asms2.

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 Asms⊢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 (Asms,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,a‾), the associated AF AFD is defined as (N,arr) with N being the set of ABA-arguments, and arr being the attack relation among ABA-arguments.

The semantics of the ABAF D can now be determined by the semantics of the associated AF AFD 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,a‾) where A={a,b,c,d,e,f}, L=A∪{ac|a∈A}, a‾=ac for each a∈A, and

ac←bc←d.dc←e.ec←b,c.bc←a.ec←c,f.fc←c.cc←f.

In this example, each rule induces one ABA-argument, for instance ({c,f},ec). The attack relation is the natural one. Hence the AF FD 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,a‾) be an ABAF, Asms⊆A and α∈A. We say that Asms attacks α iff there is an ABA-argument (Asms′,α‾) with Asms′⊆Asms. We say that Asms1⊆A attacks Asms2⊆A iff Asms1 attacks some β∈Asms2. We define Asms+ as {α∈A|Asms attacks α}. We say that Asms is conflict-free iff Asms∩Asms+=∅. We say that Asms defends α iff for each Asms′⊆A that attacks α, Asms attacks Asms′. We define the function F:2A→2A as follows: F(Asms)={α∈A|α is defended by Asms}.

Definition 31.

Let D=(L,R,A,a‾) be an ABAF. The set Asms⊆A is called

(1) an admissible assumption set iff Asms is conflict-free and Asms⊆F(Asms)
(2) a complete assumption extension iff Asms is conflict-free and Asms=F(Asms)
(3) a grounded assumption extension iff Asms is the (unique) minimal (w.r.t. ⊆) complete assumption extension
(4) a preferred assumption extension iff Asms is a maximal (w.r.t. ⊆) complete assumption extension
(5) a semi-stable assumption extension iff Asms is a complete assumption extension where Asms∪Asms+ is maximal (w.r.t. ⊆) among the complete assumption extensions
(6) a stable assumption extension iff Asms is a complete assumption extension with Asms∪Asms+=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,a‾) be an ABAF.

(1) The set Asms⊆A is an admissible assumption set according to Definitions 26-31 iff Asms is an admissible assumption set according to the definitions in [10, 22].
(2) The set Asms⊆A is a complete (resp. grounded, preferred, semi-stable or stable) assumption extension according to Definitions 26-31 iff Asms 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,γ‾) is an ABA-argument, then the set Asms 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,a‾), the associated SETAF SFD is defined as (N,arr) with N=A and arr={(Asms,γ)|(Asms,γ‾) is an ABA-argument with γ∈A}.

Example 34.

Recall the previous ABAF D=(L,R,A,a‾) where A={a,b,c,d,e,f}, L=A∪{ac|a∈A}, a‾=ac for each a∈A, and rules

ac←bc←d.dc←e.ec←b,c.bc←a.ec←c,f.fc←c.cc←f.

Each assumption in A induces one argument in our SETAF SFD. Moreover, the attacks can be read off of the rules: for instance, c and f collectively attack e due to the rule “ec←c,f.” Consequently, SFD 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,a‾) be an ABAF, SFD be the associated SETAF, and Asms⊆A. It holds that

(1) Asms is a complete extension of SFD iff Asms is a complete extension of D in the sense of [10, 22];
(2) Asms is a grounded extension of SFD iff Asms is a grounded extension of D in the sense of [10, 22];
(3) Asms is a preferred extension of SFD iff Asms is a preferred extension of D in the sense of [10, 22];
(4) Asms is a semi-stable extension of SFD iff Asms is a semi-stable extension of D in the sense of [15];
(5) Asms is a stable extension of SFD iff Asms 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 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 AF1=(N1,arr1) to an AF AF2=(N2,arr2) such that

(1)N1⊆N2andarr2∩(N1×N1)=arr1

(no new arrows are added among the nodes that were already there) and

(2)arr2∩((N2∖N1)×N2)=∅

(the new nodes do not have out-going arrows). In this situation, the complete (resp. grounded, preferred or stable) node labellings of AF2 can be computed straightforwardly if we are given the labellings of AF1. While this is intuitively clear, from a formal point of view we make use of the directionality principle here [3].

Proposition 36.

Let AF1=(N1,arr1) and AF2=(N2,arr2) be two AFs such that conditions (1) and (2) are met.

(i) If NLab1 is a complete (resp. grounded, preferred or stable) node labelling of AF1, then
NLab2=NLab1∪{(A,in)|A∈N2∖N1,∀(B,A)∈arr2:NLab1(B)=out}∪{(A,out)|A∈N2∖N1,∃(B,A)∈arr2:NLab1(B)=in}∪{(A,undec)|A∈N2∖N1,¬∀(B,A)∈arr2:NLab1(B)=out,¬∃(B,A)∈arr2:NLab1(B)=in}
is a complete (resp. grounded, preferred or stable) node labelling of AF2.
(ii) If NLab2 is a complete (resp. grounded, preferred or stable) node labelling of AF2, then NLab1 is a complete (resp. grounded, preferred or stable) node labelling of AF1.

It can be observed that the thus defined conversion functions between node labellings of AF1 and node labellings of AF2 are bijective functions that are each other’s inverses. Hence, the complete (resp. grounded, preferred and stable) node labellings of AF1 and the complete (resp. grounded, preferred and stable) node labellings of AF2 are one-to-one related.

We now formalise that the relation between the inside-out AF associated to SFD and the AF AFD corresponding to D meets the conditions described in Proposition 36.

Proposition 37.

Let D be an ABAF. Let SFD be the associated SETAF and let AFSFD be its inside-out AF. Let AFD be the AF associated with D. Then the relation between AF1:=AFSFD and AF2:=AFD 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,a‾) be an ABAF and let AFD=(N,arr) be the associated AF (the ABA-AF instantiation). We define the functions Asms2Args:2A→2N and Args2Asms:2N→2A as follows:

Asms2Args(Asms)={(Asms′,c)∈N|Asms′⊆Asms}

and

Args2Asms(M)=⋃(Asms′,c)∈MAsms′.

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 AFD. Our proof will make use of several relations we showed throughout the present paper.9 9

Theorem 38.

Let D=(L,R,A,a‾) be an ABA framework and AFD=(N,arr) be the associated argumentation framework.

(1) If Asms is a complete (resp. grounded, preferred or stable) assumption extension of D, then Asms2Args(Asms) is a complete (resp. grounded, preferred or stable) extension of AFD.
(2) If M is a complete (resp. grounded, preferred or stable) extension of AFD then Args2Asms(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 AFD the functions Asms2Args and Args2Asms 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 Asms be a complete assumption extension of D. We proceed in several steps, combining the results from our paper.
(i) By Theorem 35, the set Asms is a complete node extension of the associated SETAF SFD.
(ii) Now let NLab be the SETAF node labelling associated with Asms. From the correspondence between extensions and labellings (see Table 8), it follows that NLab is a complete SETAF node labelling of SFD.
(iii) In the next step, let ALab be the associated SETAF arrow labelling associated with NLab. By Theorem 21, it holds that ALab is a complete SETAF arrow labelling of SFD.
(iv) Let AFSFD be the inside-out AF that results from converting the SETAF SFD (Definition 22). By Theorem 23, it holds that ALab is a complete node labelling of AFSFD.
(v) Now let AFD be the AF associated to D. By Proposition 37, it holds that AFD is the result of taking AFSFD and adding some nodes without out-going arrows. Since ALab is a complete node labelling of AFSF it follows that the labelling ALab′ resulting from applying Proposition 36 is a complete node labelling of AFD.
(vi) Let M be the associated complete extension. It holds that M consists of precisely those ABA-arguments whose assumptions are in Asms. This can be seen as follows: Each attacking ABA-argument whose assumptions are in Asms will have been represented as an arrow in the SETAF that was labelled in by the SETAF arrow labelling (this is because the assumptions Asms were labelled in as nodes of the SETAF); consequently it was still labelled in by the node labelling of AFSF, so still labelled in by the node labelling of AFD, 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 AFD can be obtained by applying Proposition 36 to AFSF. So we analyse which further arguments are labelled in: By construction of AFD, the additional nodes are ABA-arguments of the form (Asms′,γ) 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, (Asms′,γ) is defended by our complete labelling of AFD iff Asms′⊆Asms. In this case, (Asms′,γ) is labelled in (Proposition 36); otherwise it is not. Consequently, the set Asms of accepted assumptions does not change when moving from AFSF to AFD and applying Proposition 36 to the novel nodes without out-going arrows.
(2) Let M be a complete extension of AFD and let Asms be the set
Asms=⋃(Asms′,c)∈MAsms′.
All of the aforementioned steps are applicable in both directions, so we can
- (i) remove suitable nodes from AFD to yield correspondence to the inside-out AF AFSFD associated with SFD;
- (ii) move from the node labelling of AFSFD to an arrow labelling of SFD;
- (iii) move from the arrow labelling of SFD to a node labelling of SFD;
- (iv) move from the node labelling of SFD to a node extension of SFD.
By the same chain of reasoning, the thus obtained set Asms′ 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. Figure 2 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 in/undec and out labelled arrows, respectively. In contrast, our arrow extensions capture precisely the in 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 in, out, or undec 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 SF (i.e., a node of the associated inside-out argumentation framework AFSF) 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 cf2 [4], stage2 [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.

Notes

1 These results are based on preliminary considerations presented at COMMA 2022 [39].

2 We note that Args2NLab is defined for conflict-free sets M⊆N.

3 The labelling-based version of complete attack semantics is defined in a slightly different way in [52] than in Definition 7, but equivalence is proved in Appendix A.

4 We note that a2ALab is defined for conflict-free sets a⊆arr.

5 We note that Args2NLab is defined for conflict-free sets M⊆N.

6 We note that ALab2a is defined for conflict-free sets a⊆arr.

7 This is similar to what was sketched at the end of Appendix A.

8 It should be observed, however, that in the SETAF not all ABA-arguments are represented, as only ABA-arguments that attack an assumption (that is, ABA-arguments whose conclusion is the contrary of an assumption) can be used as arrows of the SETAF.

9 Our main contribution here is not the (known) correspondence between ABA and AFs, but the way we can proof this result by means of our theory. We thereby shed new light on this correspondence. Consequently, we include the proof here instead of moving it to the appendix.

10 Note that the proof of Lemma 51 does not depend on this result or its consequences.

11 Note that the proof of Lemma 48 does not depend on this result or its consequences.

12 Note that the proof of Theorem 21 does not depend on this result or its consequences.

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.

Appendices

Appendix A.

Appendix A.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.

Theorem 39.

Let AF=(N,arr) be an argumentation framework and let ALab be an arrow labelling of AF. ALab is a complete arrow labelling of AF iff for every (A,B)∈arr it holds that:

(1) ALab((A,B))=in iff for each (C,A)∈arr it holds that ALab((C,A))=out
(2) ALab((A,B))=out iff there exists a (C,A)∈arr such that ALab((C,A))=in

Proof.

“⇒”: Let ALab be a complete arrow labelling of AF. Point 1 LTR follows directly from the first bullet of Definition 7. As for point 1 RTL, suppose that for each (C,A)∈arr it holds that ALab((C,A))=out. Then ALab((A,B)) cannot be out (otherwise there would have to be a (C,A)∈arr such that ALab((C,A))=in) and cannot be undec (otherwise not for each (C,A)∈arr it holds that ALab((C,A))=out). Since ALab((A,B)) can only be in, out or undec, it then follows that ALab((A,B))=in.

Point 2 LTR follows directly from the second bullet of Definition 7. As for point 2 RTL, suppose that there exists a (C,A)∈arr such that ALab((C,A))=in. Then ALab((A,B)) cannot be in (otherwise for each (C,A)∈arr it holds that ALab((C,A))=out) and cannot be undec (otherwise there does not exist a (C,A)∈arr such that ALab((C,A))=in). Since ALab((A,B)) can only be in, out or undec, it follows that ALab((A,B))=out.

“⇐”: Let ALab be an arrow labelling satisfying points 1 and 2. We now need to show that ALab also satisfies the first three bullets of Definition 7. The first bullet follows directly from point 1. The second bullet follows directly from point 2. As for the third bullet, take an arbitrary (A,B)∈arr such that ALab((A,B))=undec. The fact that ALab((A,B))≠in, together with point 1, then implies that not for each (C,A)∈arr it holds that ALab((C,A))=out. The fact that ALab((A,B))≠out, together with point 2, then implies that there does not exist a (C,A)∈arr such that ALab((C,A))=in. □

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.

Lemma 40.

Let ALab1 and ALab2 be complete arrow labellings of argumentation framework AF=(N,arr). It holds that:

(1) in(ALab1)⊆in(ALab2) iff out(ALab1)⊆out(ALab2)
(2) in(ALab1)=in(ALab2) iff out(ALab1)=out(ALab2)
(3) in(ALab1)⊊in(ALab2) iff out(ALab1)⊊out(ALab2)

Proof.

(1) “⇒”: Suppose in(ALab1)⊆in(ALab2). Let (A,B)∈out(ALab1). This means that (Definition 7, second bullet point) there exists a (C,A)∈arr such that ALab1((C,A))=in. That is, (C,A)∈in(ALab1). The fact that in(ALab1)⊆in(ALab2) then implies that (C,A)∈in(ALab2). This, together with the fact that ALab2 is a complete arrow labelling implies (by point 2 of Theorem 39) that (A,B)∈out(ALab2).
“⇐”: Suppose out(ALab1)⊆out(ALab2). Let (A,B)∈in(ALab1). This means that (Definition 7, first bullet point) that for each (C,A)∈arr it holds that (C,A)∈out(ALab1). The fact that out(ALab1)⊆out(ALab2) then implies that (C,A)∈out(ALab2). This, together with the fact that ALab2 is a complete arrow labelling implies (by point 1 of Theorem 39) that (A,B)∈in(ALab2).
(2) This follows directly from point 1.
(3) This follows directly from point 1 and point 2.

□

Lemma 41.

Let ALab1 and ALab2 be complete arrow labellings of argumentation framework AF=(N,arr). It holds that:

(1) if in(ALab1)⊆in(ALab2) then undec(ALab1)⊇undec(ALab2)
(2) if in(ALab1)=in(ALab2) then undec(ALab1)=undec(ALab2)
(3) if in(ALab1)⊊in(ALab2) then undec(ALab1)⊋undec(ALab2)
(4) if out(ALab1)⊆out(ALab2) then undec(ALab1)⊇undec(ALab2)
(5) if out(ALab1)=out(ALab2) then undec(ALab1)=undec(ALab2)
(6) if out(ALab1)⊊out(ALab2) then undec(ALab1)⊋undec(ALab2)

Proof.

(1) Suppose in(ALab1)⊆in(ALab2). Then (Lemma 40, point 1) it follows that out(ALab1)⊆out(ALab2). Let (A,B)∈undec(ALab2). Then (A,B)∉in(ALab2) so (A,B)∉in(ALab1). Also, (A,B)∉out(ALab2) so (A,B)∉out(ALab1). From the fact that (A,B) is labelled either in, out or undec by ALab1, it follows that (A,B)∈undec(ALab1).
(2) This follows directly from point 1.
(3) This follows directly from point 1 of this lemma, and Lemma 40 (point 3) and the fact that every arrow is labelled either in, out, or undec.
(4) This follows directly from Lemma 40 (point 1) and point 1 of this lemma.
(5) This follows directly from point 4.
(6) This follows directly from point 4 of this lemma, and Lemma 40 (point 3) and the fact that every arrow is labelled either in, out, or undec.

□

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

Theorem 42.

Let AF=(N,arr) be an argumentation framework, and let ALab be a complete arrow labelling of AF. The following two statements are equivalent:

1.	in(ALab) is maximal (w.r.t. set inclusion) among all complete arrow labellings of AF
2.	out(ALab) is maximal (w.r.t. set inclusion) among all complete arrow labellings of AF

The following three statements are also equivalent:

3.	in(ALab) is minimal (w.r.t. set inclusion) among all complete arrow labellings of AF
4.	out(ALab) is minimal (w.r.t. set inclusion) among all complete arrow labellings of AF
5.	undec(ALab) is maximal (w.r.t. set inclusion) among all complete arrow labellings of AF

Furthermore, it holds that the complete arrow labelling with minimal in is unique.

Proof.

from 1 to 2	Suppose in(ALab) is maximal among all complete arrow labellings of AF. That is, there is no complete arrow labelling ALab′ of AF such that in(ALab)⊊in(ALab′). Suppose, towards a contradiction, that out(ALab) is not maximal among all complete arrow labellings of AF. Then there exists a complete arrow labelling ALab′ such that out(ALab)⊊out(ALab′). It then follows from Lemma 40 (point 3) that in(ALab)⊊in(ALab′). Contradiction.
from 2 to 1	Similar to the previous point.
from 3 to 4	Suppose in(ALab) is minimal among all complete arrow labellings of AF. That is, there is no complete arrow labelling ALab′ of AF such that in(ALab′)⊊in(ALab). Suppose, towards a contradiction, that out(ALab) is not minimal among all complete arrow labellings of AF. Then there exists a complete arrow labelling ALab′ such that out(ALab′)⊊out(ALab). It then follows from Lemma 40 (point 3) that in(ALab′)⊊in(ALab). Contradiction.
from 4 to 3	Similar to the previous point.
from 5 to 3	Suppose undec(ALab) is maximal among all complete arrow labellings of AF. That is, there is no complete arrow labelling ALab′ of AF such that undec(ALab)⊊undec(ALab′). Suppose, towards a contradiction, that in(ALab) is not maximal among all complete arrow labellings of AF. Then there exists a complete arrow labelling ALab′ such that in(ALab)⊊in(ALab′). It then follows from Lemma 41 (point 3) that undec(ALab′)⊊undec(ALab). Contradiction.

As for the last point to be proved (from 3 to 5), a particular difficulty is that we cannot just use the same proof strategy as the previous point (from 5 to 3). This is because point 3 of Lemma 41 only goes one-way (it’s an “if” instead of an “iff”). To overcome this, we will need to make use of the uniqueness of the grounded arrow labelling.

uniqueness grounded arrow labelling

Suppose ALab1 and ALab2 are complete arrow labellings of AF with minimal in. That is, they are grounded arrow labellings of AF. From Lemma 51 it follows10 10 that NLab1=ALab2NLab(ALab1) and NLab2=ALab2NLab(ALab2) are grounded node labellings of AF. However, since the grounded node labelling is unique [14] it follows that NLab1=NLab2, so also NLab2ALab(NLab1)=NLab2ALab(NLab2). However, since NLab2ALab(NLab1)=ALab1 and NLab2ALab(NLab2)=ALab2 (by Lemma 48)11 11 it follows that ALab1=ALab2.

Using the uniqueness of the grounded arrow labelling, we can then proceed to show that point 3 implies point 5.

from 3 to 5

Suppose ALab1 is a complete arrow labelling of AF with minimal in. That is, ALab1 is a minimal element of the set of complete arrow labellings of AF (when applying an ordering based on set-inclusion on the in-labelled part of the labellings). As this minimal element is unique, it is also the smallest element, meaning that it is less or equal to each element of the set. That is, for each complete arrow labelling ALab′ of AF, it holds that in(ALab)⊆in(ALab′). From Lemma 41 (point 1) it then follows that undec(ALab′)⊆undec(ALab). It then follows that there is there is no complete arrow labelling ALab′ of AF such that undec(ALab)⊊undec(ALab′). That is, ALab is a complete arrow labelling with maximal undec.

□

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)∈arr, 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.

Definition 43.

Let AF=(N,arr) be an argumentation framework. The inside out argumentation framework of AF is defined as AF′=(N′,arr′) with N′=arr and arr′={((A,B),(B,C))|(A,B),(B,C)∈arr}.

Theorem 44.

Let AF=(N,arr) be an argumentation framework and AF′=(N′,arr′) be its inside out argumentation framework.

(1) If ALab is a complete arrow labelling of AF, then ALab is a complete node labelling of AF′.
If NLab is a complete node labelling of AF′, then NLab is a complete arrow labelling of AF.
(2) If ALab is a preferred (resp. grounded or stable) arrow labelling of AF, then ALab is a preferred (resp. grounded or stable) node labelling of AF′.
If NLab is a preferred (resp. grounded, stable or semi-stable) node labelling of AF′, then NLab is a preferred (resp. grounded, stable or semi-stable) arrow labelling of AF.

Proof.

(1) This follows directly from the definition of a complete node labelling (Definition 4, first three bullet points), the definition of a complete arrow labelling (Definition 7, first three bullet points) and the definition of an inside out argumentation framework (Definition 43).
(2) This follows directly from point 1, together with the definition of a preferred (resp. grounded, stable or semi-stable) node labelling (Definition 4) and the definition of a preferred (resp. grounded, stable or semi-stable) arrow labelling (Definition 7).

□

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].

Appendix B.

Appendix B.Equivalence of node labellings and arrow labellings for argumentation frameworks

Lemma 45.

Let AF=(N,arr) be an argumentation framework. If NLab is a complete node labelling of AF then ALab=NLab2ALab(NLab) is a complete arrow labelling of AF.

Proof.

We need to prove that the three bullet points of Definition 7 are satisfied. Let (A,B)∈arr. We distinguish three cases:

(1) ALab((A,B))=in. From the definition of NLab2ALab it then follows that NLab(A)=in. From the fact that NLab is a complete node labelling, it then follows that NLab(C)=out for each C∈N that attacks A. From the definition of NLab2ALab it then follows that ALab((C,A))=out.
(2) ALab((A,B))=out. From the definition of NLab2ALab it then follows that NLab(A)=out. From the fact that NLab is a complete node labelling, it then follows that NLab(C)=in for some C∈N that attacks A. From the definition of NLab2ALab it then follows that ALab((C,A))=in.
(3) ALab((A,B))=undec. From the definition of NLab2ALab it then follows that NLab(A)=undec. From the fact that NLab is a complete node labelling, it then follows that not for each C∈N that attacks A it holds that NLab(C)=out and there is no C∈N that attacks A such that NLab(C)=in. From the definition of NLab2ALab it then follows that not for each (C,A)∈arr it holds that ALab((C,A))=out, and there is no (C,A)∈arr such that ALab((C,A))=in.

□

Lemma 46.

Let AF=(N,arr) be an argumentation framework. If ALab is a complete arrow labelling of AF then NLab=ALab2NLab(ALab) is a complete node labelling of AF.

Proof.

We need to prove that the three bullet points of Definition 4 are satisfied. Let A∈N. We distinguish three cases:

(1) NLab(A)=in. We need to show that for every B∈N that attacks A, it holds that NLab(B)=out. Let B∈N be a node that attacks A. This means that (B,A)∈arr. From the definition of ALab2NLab and the fact that NLab(A)=in it follows that ALab((B,A))=out. From the fact that ALab is a complete arrow labelling it then follows that there exists a (C,B)∈arr such that ALab((C,B))=in. From the definition of ALab2NLab it then follows that NLab(B)=out.
(2) NLab(A)=out. We need to show that there exists a B∈N that attacks A such that NLab(B)=in. From the definition of ALab2NLab and the fact that NLab(A)=out it follows that there is a (B,A)∈arr such that ALab((B,A))=in. From the fact that ALab is a complete arrow labelling, it then follows that for each C∈N that attacks B, it holds that ALab((C,B))=out. From the definition of ALab2NLab, it then follows that NLab(B)=in.
(3) NLab(A)=undec. We need to show that not for all B∈N that attack A it holds that NLab(B)=out, and that there is no B∈N that attacks A such that NLab(B)=in. From the definition of ALab2NLab and the fact that NLab(A)=undec it follows that (i) not for all (B,A)∈arr it holds that ALab((B,A))=out, and (ii) there is no (B,A)∈arr such that ALab((B,A))=in. From (i) it follows that there is a (B,A)∈arr such that ALab((B,A))≠out. From the fact that ALab is a complete arrow labelling, it then follows that there is no C∈N that attacks B such that ALab((C,B))=in, which from the definition of ALab2NLab implies that NLab(B)≠out. From (ii) it follows that for each (B,A)∈arr it holds that ALab((B,A))≠in. Let B be an arbitrary attacker of A. It directly follows that ALab((B,A))≠in. From the fact that ALab is a complete arrow labelling, it follows that there is a (C,B)∈arr such that ALab((C,B))≠out. From the definition of ALab2NLab, it then follows that NLab(B)≠in.

□

Lemma 47.

Let NLab be a complete node labelling of argumentation framework AF=(N,arr). It holds that ALab2NLab(NLab2ALab(NLab))=NLab.

Proof.

Let ALab=NLab2ALab(NLab). It suffices to prove the following three properties, for an arbitrary A∈N.

(1) If NLab(A)=in then ALab2NLab(ALab)(A)=in.
Suppose NLab(A)=in. Then from NLab being a complete node labelling, it follows that for each B that attacks A it holds that NLab(B)=out, which from the definition of NLab2ALab implies that ALab((B,A))=out. From the definition of ALab2NLab it then follows that ALab2NLab(ALab)(A)=in
(2) If NLab(A)=out then ALab2NLab(ALab)(A)=out.
Suppose NLab(A)=out. Then from NLab being a complete node labelling, it follows that there is a B∈N that attacks A such that NLab(B)=in, which from the definition of NLab2ALab implies that ALab((B,A))=in. From the definition of ALab2NLab it then follows that ALab2NLab(ALab)(A)=out
(3) If NLab(A)=undec then ALab2NLab(ALab)(A)=undec.
Suppose NLab(A)=undec. Then from NLab being a complete node labelling, it follows that (i) not for each B∈N that attacks A it holds that NLab(B)=out, and (ii) there is no B∈N that attacks A such that NLab(B)=in. From (i) it directly follows that there exists a B∈N that attacks A such that NLab(B)≠out, thus ALab((B,A))≠out. Then, from the definition of ALab2NLab it follows that ALab2NLab(ALab)(A)≠in. From (ii) it directly follows that for each B∈N that attacks A it holds that NLab(B)≠in. Then, from the definition of NLab2ALab it follows that ALab((B,A))≠in. Then, from the definition of ALab2NLab it follows that ALab2NLab(ALab)(A)≠out. This, together with the earlier obtained fact that ALab2NLab(ALab)(A)≠in implies that ALab2NLab(NLab)(A)=undec.

□

Lemma 48.

Let ALab be a complete arrow labelling of argumentation framework AF=(N,arr). It holds that NLab2ALab(ALab2NLab(ALab))=ALab.

Proof.

Let NLab=ALab2NLab(ALab). It suffices to prove the following three properties, for an arbitrary (A,B)∈arr.

(1) If ALab((A,B))=in then NLab2ALab(NLab)((A,B))=in.
Suppose ALab((A,B))=in. Then from the fact that ALab is a complete arrow labelling, it follows that for each C that attacks A, ALab((C,A))=out. From the definition of ALab2NLab it then follows that NLab(A)=in. From the definition of NLab2ALab it then follows that NLab2ALab(NLab)((A,B))=in.
(2) If ALab((A,B))=out then NLab2ALab(NLab)((A,B))=out.
Suppose ALab((A,B))=out. Then, from the fact that ALab is a complete arrow labelling, it follows that there exists a C that attacks A such that ALab((C,A))=in. From the definition of ALab2NLab it then follows that NLab(A)=out. From the definition of NLab2ALab it then follows that NLab2ALab(NLab)((A,B))=out.
(3) If ALab((A,B))=undec then NLab2ALab(NLab)((A,B))=undec.
Suppose ALab((A,B))=undec. Then from the fact that ALab is a complete arrow labelling, it follows that (i) not for each C that attacks A it holds that ALab((C,A))=out, and (ii) there is no C that attacks A such that ALab((C,A))=in. From (i) it directly follows that there is a C that attacks A such that ALab((C,A))≠out. From the definition of ALab2NLab it then follows that NLab(A)≠in. From the definition of NLab2ALab it then follows that NLab2ALab(NLab)((A,B))≠in. From (ii) it directly follows that for each C that attacks A it holds that ALab((C,A))≠in. From the definition of ALab2NLab it then follows that NLab(A)≠out. From the definition of NLab2ALab it then follows that NLab2ALab(NLab)((A,B))≠out. From this, together with the earlier observed fact that NLab2ALab(NLab)((A,B))≠in, it follows that NLab2ALab(NLab)((A,B))=undec.

□

Lemma 49.

Let NLab1 and NLab2 be complete node labellings of an argumentation framework AF=(N,arr). Let ALab1=NLab2ALab(NLab1) and ALab2=NLab2ALab(NLab2). It holds that:

(1) in(NLab1)⊆in(NLab2) iff in(ALab1)⊆in(ALab2).
(2) in(NLab1)=in(NLab2) iff in(ALab1)=in(ALab2).
(3) in(NLab1)⊊in(NLab2) iff in(ALab1)⊊in(ALab2).
(4) out(NLab1)⊆out(NLab2) iff out(ALab1)⊆out(ALab2).
(5) out(NLab1)=out(NLab2) iff out(ALab1)=out(ALab2).
(6) out(NLab1)⊊out(NLab2) iff out(ALab1)⊊out(ALab2).
(7) If undec(NLab1)⊆undec(NLab2) then undec(ALab1)⊆undec(ALab2).
(8) If undec(NLab1)=undec(NLab2) then undec(ALab1)=undec(ALab2).

Proof.

(1) “⇒”: Suppose in(NLab1)⊆in(NLab2). Let (A,B)∈in(ALab1). Then, from the definition of NLab2ALab it follows that A∈in(NLab1). The fact that in(NLab1)⊆in(NLab2) then implies that A∈in(NLab2). From the definition of NLab2ALab it then follows that (A,B)∈in(ALab2).
“⇐”: Suppose in(ALab1)⊆in(ALab2). Let A∈in(NLab1). First assume that there is a node B∈N such that (A,B)∈arr, i.e., A has an outgoing arrow. Then, from the definition of NLab2ALab it follows that for each B∈N such that (A,B)∈arr it holds (A,B)∈in(ALab1). The fact that in(ALab1)⊆in(ALab2) then implies that (A,B)∈in(ALab2). From the definition of NLab2ALab it then follows that A∈in(NLab2) and we are done. Now on the other hand assume that there is no node B∈N such that (A,B)∈arr, i.e., A has no outgoing arrows. Towards contradiction assume that A∉in(NLab2). This means either A is not defended by in(NLab2) or there is some B∈in(NLab2) such that (B,A)∈arr. Since we assume A∈in(NLab1) and NLab1 is complete we know that for each arrow (C,A)∈arr towards A there is a counter-attack (D,C)∈arr with D∈in(NLab1). From the definition of NLab2ALab it then follows that (D,C)∈in(ALab1). From in(ALab1)⊆in(ALab2) we then get (D,C)∈in(ALab2) and, hence, from the definition of NLab2ALab we get D∈in(NLab2). Since we chose an arbitrary attacker C of A, we know that A is defended by in(NLab2). It remains to handle the case where there is some B∈in(NLab2) such that (B,A)∈arr, i.e., A is not in in(NLab2) due to a conflict. However, since NLab1 is complete this means that B∈out(NLab1), and therefore (B,A)∈out(ALab1). From this and the fact that in(ALab1)⊆in(ALab2) and from Lemma 40 (point 1) we get (B,A)∈out(ALab2), which gives us from the definition of NLab2ALab that B∈out(NLab2), a contradiction to our assumption B∈in(NLab2).
(2) This follows directly from point 1.
(3) This follows directly from point 1 and point 2.
(4) “⇒”: Suppose out(NLab1)⊆out(NLab2). Let (A,B)∈out(ALab1). Then, from the definition of NLab2ALab it follows that A∈out(NLab1). The fact that out(NLab1)⊆out(NLab2) then implies that A∈out(NLab2). From the definition of NLab2ALab it then follows that (A,B)∈out(ALab2).
“⇐”: Suppose out(ALab1)⊆out(ALab2). Let A∈out(NLab1). Then, since NLab1 is complete, there is a B∈in(NLab1) such that (B,A)∈arr. From the definition of NLab2ALab it follows that (B,A)∈in(ALab1). From our assumption out(ALab1)⊆out(ALab2) and Lemma 40 (point 1) we get in(ALab1)⊆in(ALab2), and therefore (B,A)∈in(ALab2). From the definition of NLab2ALab it follows that B∈in(NLab2), and since NLab2 is complete we get A∈out(NLab2).
(5) This follows directly from point 4.
(6) This follows directly from point 4 and point 5.
(7) Suppose undec(NLab1)⊆undec(NLab2). Let (A,B)∈undec(ALab1). Then, from the definition of NLab2ALab it follows that A∈undec(NLab1). The fact that undec(NLab1)⊆undec(NLab2) then implies that A∈undec(NLab2). From the definition of NLab2ALab it then follows that (A,B)∈undec(ALab2).
(8) This follows directly from point 7.

□

Note that the following similar statements do not hold:

7’ If undec(ALab1)⊆undec(ALab2) then undec(NLab1)⊆undec(NLab2). A counter example is AF in Example 9: We have undec(ALab2)⊆undec(ALab3) but undec(NLab2)⊈undec(NLab3).
8’ If undec(ALab1)=undec(ALab2) then undec(NLab1)=undec(NLab2). A counter example is AF in Example 9: We have undec(ALab2)=undec(ALab3) but undec(NLab2)≠undec(NLab3).
9 If undec(NLab1)⊊undec(NLab2) then undec(ALab1)⊊undec(ALab2). A counter example is AF in Example 9: We have undec(NLab3)⊊undec(NLab2) but undec(NLab3)⊊̸undec(NLab2).
9’ If undec(ALab1)⊊undec(ALab2) then undec(NLab1)⊊undec(NLab2). A counter example is AF in Example 10: We have undec(ALab3)⊊undec(ALab2) but undec(NLab3)⊊̸undec(NLab2).

Lemma 50.

Let ALab1 and ALab2 be complete arrow labellings of argumentation framework AF=(N,arr). Let NLab1=ALab2NLab(ALab1) and NLab2=ALab2NLab(ALab2). It holds that:

(1) in(ALab1)⊆in(ALab2) iff in(NLab1)⊆in(NLab2).
(2) in(ALab1)=in(ALab2) iff in(NLab1)=in(NLab2).
(3) in(ALab1)⊊in(ALab2) iff in(NLab1)⊊in(NLab2).
(4) out(ALab1)⊆out(ALab2) iff out(NLab1)⊆out(NLab2).
(5) out(ALab1)=out(ALab2) iff out(NLab1)=out(NLab2).
(6) out(ALab1)⊊out(ALab2) iff out(NLab1)⊊out(NLab2).
(7) If undec(NLab1)⊆undec(NLab2) then undec(ALab1)⊆undec(ALab2).
(8) If undec(NLab1)=undec(NLab2) then undec(ALab1)=undec(ALab2).

Proof.

(1) “⇒”: Suppose in(ALab1)⊆in(ALab2). Let A∈in(NLab1). Then, from the definition of ALab2NLab it follows that for every C that attacks A, (C,A)∈out(ALab1). From the fact that in(ALab1)⊆in(ALab2) it follows that (Lemma 40) out(ALab1)⊆out(ALab2), so (C,A)∈out(ALab2). From the definition of ALab2NLab it then follows that NLab2(A)=in. That is, A∈in(NLab2).
“⇐”: Suppose in(NLab1)⊆in(NLab2). Let (A,B)∈in(ALab1). Since we assume that ALab1 is complete, it follows that for every (C,A) towards A, (C,A)∈out(ALab1). This means for some (D,C)∈arr we have (D,C)∈in(ALab1). Then, from the definition of ALab2NLab it follows that C∈out(NLab1). From in(NLab1)⊆in(NLab2) and [2, Lemma 1] we then get out(NLab1)⊆out(NLab2). From this and C∈out(NLab1) we get C∈out(NLab2). Then from the definition of ALab2NLab it follows that there is some (D,C)∈in(ALab2) which means (C,A)∈out(ALab2), and then since ALab2 is complete we get (A,B)∈in(ALab2).
(2) This follows directly from point 1.
(3) This follows directly from point 1 and point 2.
(4) “⇒”: Suppose out(ALab1)⊆out(ALab2). Let A∈out(NLab1). Then, from the definition of ALab2NLab it follows that there exists a C that attacks A such that (C,A)∈in(ALab1). From the fact that out(ALab1)⊆out(ALab2) it follows that (Lemma 40) in(ALab1)⊆in(ALab2), so (C,A)∈in(ALab2). From the definition of ALab2NLab it then follows that NLab2(A)=out. That is, A∈out(NLab2).
“⇐”: Suppose out(NLab1)⊆out(NLab2). Let (A,B)∈out(ALab1). Since we assume that ALab1 is complete, it follows that there exists a (C,A) towards A such that (C,A)∈in(ALab1). By completeness this means for every (D,C)∈arr towards C we have (D,C)∈out(ALab1). Then, from the definition of ALab2NLab it then follows that C∈in(NLab1). From out(NLab1)⊆out(NLab2) and [2, Lemma 1] we then get in(NLab1)⊆in(NLab2). From this and C∈in(NLab1) we get C∈in(NLab2). Then from the definition of ALab2NLab it follows that for every (D,C)∈arr towards C we have (D,C)∈out(ALab2), which means (C,A)∈in(ALab2), and then since ALab2 is complete we get (A,B)∈out(ALab2).
(5) This follows directly from point 4.
(6) This follows directly from point 4 and point 5.
(7) Suppose undec(NLab1)⊆undec(NLab2). Let (A,B)∈undec(ALab1). Then, by completeness of ALab1 it follows that for no (C,A)∈arr it holds (C,A)∈in(ALab1) and there is some (C,A)∈arr such that (C,A)∉out(ALab1), i.e., (C,A)∈undec(ALab1). From the definition of ALab2NLab it follows that A∈undec(NLab1). The fact that undec(NLab1)⊆undec(NLab2) then implies that A∈undec(NLab2). From the definition of ALab2NLab it follows then that for no (C,A)∈arr towards A it holds (C,A)∈in(ALab2) and not for all (C,A)∈arr we have (C,A)∈out(ALab2). From this we get (A,B)∈undec(ALab2).
(8) This follows directly from point 7.

□

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 NLab2ALab and ALab2NLab 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 undec(ALab3)⊆undec(ALab2) but undec(ALab2NLab(ALab3))⊈undec(ALab2NLab(ALab2)). Furthermore, it also holds that undec(ALab3)=undec(ALab2) but undec(ALab2NLab(ALab3))≠undec(ALab2NLab(ALab2)).

Example 9.

Let AF=(N,arr) be an argumentation framework with N={A,B,C,D} and arr={(A,A),(A,C),(B,D),(D,B),(D,C)}.

AF has three complete node labellings:

NLab1=(∅,∅,{A,B,C,D})NLab2=({B},{D},{A,C})NLab3=({D},{B,C},{A})

and three complete arrow labellings:

ALab1=(∅,∅,{(A,A),(A,C),(B,D),(D,B),(D,C)})ALab2=({(B,D)},{(D,B),(D,C)},{(A,A),(A,C)})ALab3=({(D,B),(D,C)},{(B,D)},{(A,A),(A,C)})

Lemma 51.

Let AF=(N,arr) be an argumentation framework.

(1) If NLab is a grounded node labelling of AF then NLab2ALab(NLab) is a grounded arrow labelling of AF.
(2) If ALab is a grounded arrow labelling of AF then ALab2NLab(ALab) is a grounded node labelling of AF.

Proof.

(1) Let NLab be a grounded node labelling of AF. Since a grounded node labelling is also a complete node labelling, it follows (Lemma 45) that ALab=NLab2ALab(NLab) is a complete arrow labelling. Suppose, towards a contradiction, that ALab does not have minimal in. That is, there exists a complete arrow labelling ALab′ such that in(ALab′)⊊in(ALab). From point 3 of Lemma 50 it then follows that in(ALab2NLab(ALab′))⊊in(ALab2NLab(ALab)). Let NLab′=ALab2NLab(ALab′). It follows (Lemma 46) that NLab′ is a complete node labelling. Furthermore, it follows from Lemma 47 that ALab2NLab(ALab)=NLab. Hence, we obtain in(NLab′)⊊in(NLab). But this is impossible since NLab is a grounded node labelling and therefore has minimal in among all complete node labellings.
(2) Let ALab be a grounded arrow labelling of AF. Since a grounded arrow labelling is also a complete arrow labelling, it follows (Lemma 46) that NLab=ALab2NLab(ALab) is a complete node labelling. Suppose, towards a contradiction, that NLab does not have minimal in. That is, there exists a complete node labelling NLab′ such that in(NLab′)⊊in(NLab). From point 3 of Lemma 49 it then follows that in(NLab2ALab(NLab′))⊊in(NLab2ALab(NLab)). Let ALab′=NLab2ALab(NLab′). It follows (Lemma 45) that ALab′ is a complete arrow labelling. Furthermore, it follows from lemma 48 that NLab2ALab(NLab)=ALab. Hence, we obtain in(ALab′)⊊in(ALab). But this is impossible since ALab is a grounded arrow labelling and therefore has minimal in among all complete arrow labellings.

□

Lemma 52.

Let AF=(N,arr) be an argumentation framework.

(1) If NLab is a preferred node labelling of AF then NLab2ALab(NLab) is a preferred arrow labelling of AF.
(2) If ALab is a preferred arrow labelling of AF then ALab2NLab(ALab) is a preferred node labelling of AF.

Proof.

Similar to the proof of Lemma 51 □

Lemma 53.

Let AF=(N,arr) be an argumentation framework.

(1) If NLab is a stable node labelling of AF then NLab2ALab(NLab) is a stable arrow labelling of AF.
(2) If ALab is a stable arrow labelling of AF then ALab2NLab(ALab) is a stable node labelling of AF.

Proof.

(1) Let NLab be a stable node labelling of AF. Since a stable node labelling is also a complete node labelling, it follows (Lemma 45) that ALab=NLab2ALab(NLab) is a complete arrow labelling. In order to prove that ALab is also a stable arrow labelling, we need to show that no arrow is labelled undec. Let (A,B)∈arr. The fact that NLab is a stable node labelling implies that A is labelled either in or out. In case NLab(A)=in, it follows from the definition of NLab2ALab that ALab((A,B))=in. In case NLab(A)=out, it follows from the definition of NLab2ALab that ALab((A,B))=out. In both cases, ALab((A,B))≠undec.
(2) Let ALab be a stable arrow labelling of AF. Since a stable arrow labelling is also a complete arrow labelling, it follows (Lemma 46) that NLab=ALab2NLab(ALab) is a complete node labelling. In order to prove that NLab is also a stable node labelling, we need to show that no node is labelled undec. Let A∈N and let B be the set of attackers of A. The fact that ALab is a stable arrow labelling means that for every attacker B∈B it holds that ALab((B,A)) is either in or out. This implies that either there exists a B∈B such that ALab((B,A))=in, or for each B∈B it holds that ALab((B,A))=out. In the former case, it follows from the definition of ALab2NLab that NLab(A)=out. In the latter case, it follows from the definition of ALab2NLab that NLab(A)=in. In either case, it holds that NLab(A)≠undec.

□

Remark 54.

Notice that it does not hold that if NLab is a semi-stable node labelling of AF then NLab2ALab(NLab) is a semi-stable arrow labelling of AF. Example 10 provides a counter example: while NLab2 is a semi-stable node labelling, ALab2 is not a semi-stable arrow labelling. Neither does the other direction hold (i.e., if ALab is a semi-stable arrow labelling of AF then ALab2NLab(ALab) is a semi-stable node labelling of AF), Example 9 provides a counter example: while ALab2 is a semi-stable arrow labelling, NLab2 is not a semi-stable node labelling.

We recall Example 10 from Section 2 (see below). It holds that undec(ALab3)⊊undec(ALab2) but undec(ALab2NLab(ALab3))⊊̸undec(ALab2NLab(ALab2)).

Example 10.

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

AF has three complete node labellings:

NLab1=(∅,∅,{A,B,C,D,E,F})NLab2=({A},{B,D},{C,E,F})NLab3=({D,F},{A,E},{B,C})

and three complete arrow labellings:

ALab1=(∅,∅,{(A,B),(C,B),(C,C),(A,D),(D,A),(D,E),(E,E),(E,F)})ALab2=({(A,B),(A,D)},{(D,A),(D,E)},{(C,B),(C,C),(E,E),(E,F)})ALab3=({(D,A),(D,E)},{(A,B),(A,D),(E,E),(E,F)},{(C,B),(C,C)})

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 AF=(N,arr) be an argumentation framework and let NLab and ALab be a node labelling and an arrow labelling of AF, respectively. It holds that:

(1) If NLab is a complete node labelling, then NLab2ALab(NLab) is a complete arrow labelling.
If ALab is a complete arrow labelling, then ALab2NLab(ALab) is a complete node labelling.
(2) When restricted to complete node labellings and complete arrow labellings, the functions ALab2NLab and NLab2ALab become bijections and each other’s inverses.
(3) If NLab is a grounded node labelling, then NLab2ALab(NLab) is a grounded arrow labelling.
If ALab is a grounded arrow labelling, then ALab2NLab(ALab) is a grounded node labelling.
(4) If NLab is a preferred node labelling, then NLab2ALab(NLab) is a preferred arrow labelling.
If ALab is a preferred arrow labelling, then ALab2NLab(ALab) is a preferred node labelling.
(5) If NLab is a stable node labelling, then NLab2ALab(NLab) is a stable arrow labelling.
If ALab is a stable arrow labelling, then ALab2NLab(ALab) 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.

□

Appendix C.

Appendix C.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 (2N∖∅)×N while SETAFs allow for attacks of the form (∅,A), A∈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

Lemma 55(Fundamental Lemma).

Let SF=(N,arr) be a SETAF, let M⊆N be admissible, and let A,A′∈FSF(M) (i.e., A and A′ are defended by M). Then

(1) M′=M∪{A} is admissible, and
(2) A′∈FSF(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∈M′ and a set M″⊆M′ such that (M″,B)∈arr. We consider three cases: (i) A=B and A∉M″; (ii) A=B and A∈M″; (iii) A≠B and A∈M″, (iv) A≠B and A∉M″.
(i) First assume A=B and A∉M″. That is, M″⊆M attacks A. Since A is defended by M, there is some M‴⊆M that attacks M″. Hence we have M is not conflict-free, contradiction.
(ii) Now assume A=B and A∈M″. Since A is defended by M, there is some M‴⊆M that attacks some element C∈M″. In case C∈M″∩M, it follows that M is not conflict-free, contradiction. In case C=A, consider case (i).
(iii) Next assume A≠B and A∈M″. That is, the set M is attacked by M″ containing A. Since M is admissible, there is some set M‴⊆M that attacks some element in D∈b. Since M is conflict-free, we have D∉M. It follows that D=A, i.e, there is an attack (M‴,A)∈arr with M‴⊆M. Hence, we can consider case (i) again to derive a contradiction.
(iv) Finally, suppose A≠B and A∉M″. Hence, M″∪{B}⊈M, contradiction to admissibility of M.
(2) By of the characteristic function.

□

Theorem 56.

Let SF=(N,arr) be a SETAF and let M⊆N. The following two statements are equivalent.

(1) M is a maximal (w.r.t. ⊆) admissible set of SF
(2) M is a maximal (w.r.t. ⊆) complete extension if SF

Proof.

from 1. to 2.

Consider a maximal (w.r.t. ⊆) admissible set M of SF. First, we show that M is complete. We show that M contains all nodes it defends. Let A∈F(M). By the fundamental lemma, it holds that M∪{A} is admissible. Since M is a ⊆-maximal admissible set, it follows that A∈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′⊃M. By definition of complete semantics, M′ is admissible. Hence, we have a contradiction to ⊆-maximality of M among the admissible extensions of SF.

from 2. to 1.

Consider a maximal (w.r.t. ⊆) complete set M of SF. 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′⊃M. By monotonicity of the characteristic function, there is a complete extension M″ such that M′⊆M″. Hence, we obtain a contradiction to the ⊆-maximality of M.

□

Theorem 57.

Let SF=(N,arr) be a SETAF and let M⊆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∪M+=N

Proof.

from 1. to 2.

Consider a conflict-free set M of SF that attacks all nodes in N∖M. Hence, it holds that M∪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∈M that is not defended by M. I.e., there is some attack (M′,A)∈arr such that M′∩M+=∅. By assumption M attacks all nodes in N∖M, it follows that M′⊆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∈F(M). By the fundamental lemma, it holds that M∪{A} is admissible. Since M attacks all nodes not contained in M, it follows that A∈M.

from 2. to 1.

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

□

Appendix D.

Appendix D.Properties of node labellings for SETAFs

Theorem 58.

Let SF=(N,arr) be a SETAF, let M⊆N and let NLab be a SETAF node labelling of SF. It holds that:

(1) if M is a complete extension of SF then
- Args2NLab(M) is a complete SETAF node labelling of SF, and
- NLab2Args(Args2NLab(M))=M
(2) if NLab is a complete SETAF node labelling of SF then
- NLab2Args(NLab) is a complete extension of SF, and
- Args2NLab(NLab2Args(NLab))=NLab
(3) if M is a grounded extension of SF then Args2NLab(M) is a grounded SETAF node labelling of SF
(4) if NLab is a grounded SETAF node labelling of SF then NLab2Args(NLab) is a grounded extension of SF
(5) if M is a preferred extension of SF then Args2NLab(M) is a preferred SETAF node labelling of SF
(6) if NLab is a preferred SETAF node labelling of SF then NLab2Args(NLab) is a preferred extension of SF
(7) if M is a semi-stable extension of SF then Args2NLab(M) is a semi-stable SETAF node labelling of SF
(8) if NLab is a semi-stable SETAF node labelling of SF then NLab2Args(NLab) is a semi-stable extension of SF
(9) if M is a stable extension of SF then Args2NLab(M) is a stable SETAF node labelling of SF
(10) if NLab is a stable SETAF node labelling of SF then NLab2Args(NLab) is a stable extension of SF

Proof.

Shown in [35]. □

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

Lemma 59.

Let NLab1 and NLab2 be complete node labellings of SETAF SF=(N,arr). It holds that:

(1) in(NLab1)⊆in(NLab2) iff out(NLab1)⊆out(NLab2)
(2) in(NLab1)=in(NLab2) iff out(NLab1)=out(NLab2)
(3) in(NLab1)⊊in(NLab2) iff out(NLab1)⊊out(NLab2)

Proof.

(1) “⇒”: Suppose in(NLab1)⊆in(NLab2). Let A∈out(NLab1). This means that (Definition 17, second bullet point) there exists a (M,A)∈arr such that ∀B∈M:NLab1(B)=in. The fact that in(NLab1)⊆in(NLab2) then implies that ∀B∈M:NLab2(B)=in. Then NLab2(A) cannot be in (otherwise there would have to be a B∈M such that NLab2(B)=out) and cannot be undec (by Definition 17, third bullet point). Since NLab2(A) can only be in, out or undec, it then follows that NLab2(A)=out.
“⇐”: Suppose out(NLab1)⊆out(NLab2). Let A∈in(NLab1). This means that (Definition 17, first bullet point) for each M⊆N such that (M,A)∈arr it holds that ∃B∈M:NLab1(B)=out. The fact that out(NLab1)⊆out(NLab2) then implies that for each M⊆N such that (M,A)∈arr it holds that ∃B∈M:NLab2(B)=out. Then NLab2(A) cannot be out (otherwise there would have to be a (M,A)∈arr such that ∀B∈M:NLab2(B)=in) and cannot be undec (by Definition 17, third bullet point). Since NLab2(A) can only be in, out or undec, it then follows that NLab2(A)=in.
(2) This follows directly from point 1.
(3) This follows directly from point 1 and point 2.

□

Theorem 60.

Let SF=(N,arr) be a SETAF, and let NLab be a SETAF node labelling of SF. The following two statements are equivalent:

(1) in(NLab) is maximal (w.r.t. set inclusion) among all complete SETAF node labellings of SF
(2) out(NLab) is maximal (w.r.t. set inclusion) among all complete SETAF node labellings of SF

The following three statements are also equivalent:

3. in(NLab) is minimal (w.r.t. set inclusion) among all complete SETAF node labellings of SF
4. out(NLab) is minimal (w.r.t. set inclusion) among all complete SETAF node labellings of SF
5. undec(NLab) is maximal (w.r.t. set inclusion) among all complete SETAF node labellings of SF

Furthermore, it holds that the complete SETAF node labelling with minimal in is unique.

Proof.

from 1 to 2	Let NLab be a complete labelling where out(NLab) is not maximal. Then there exists a complete labelling NLab′ with out(NLab)⊊out(NLab′). From Lemma 59 it then follows that in(NLab)⊊in(NLab′), so NLab is a labelling where in(NLab) is not maximal.
from 2 to 1	Let NLab be a complete labelling where in(NLab) is not maximal. Then there exists a complete labelling NLab′ with in(NLab)⊊in(NLab′). From Lemma 59 it then follows that out(NLab)⊊out(NLab′), so NLab is a labelling where out(NLab) is not maximal.
from 3 to 4	Note that this result is mentioned in [8] in the context of extensions. Let NLab be a complete labelling where out(NLab) is not minimal. Then there exists a complete labelling NLab′ with out(NLab′)⊊out(NLab). From Lemma 59 it then follows that in(NLab′)⊊in(NLab), so NLab is a labelling where in(NLab) is not minimal.
from 4 to 3	Note that this result is mentioned in [8] in the context of extensions. Let NLab be a complete labelling where in(NLab) is not minimal. Then there exists a complete labelling NLab′ with in(NLab′)⊊in(NLab). From Lemma 59 it then follows that out(NLab′)⊊out(NLab), so NLab is a labelling where out(NLab) is not minimal.
from 3 to 5	Let NLab be a complete labelling where in(NLab) is minimal. Then by Theorem 58 NLab2Args(NLab) is the grounded extension. Now suppose that undec(NLab) is not maximal. Then there exists a complete labelling NLab′ with undec(NLab)⊊undec(NLab′). It holds that NLab2Args(NLab′) is a complete extension, and from the fact that the grounded extension is a subset of each complete extension, it follows that NLab2Args(NLab)⊆NLab2Args(NLab′), so in(NLab)⊆in(NLab′). From Lemma 59 it then follows that out(NLab)⊆out(NLab′). From the fact that in(NLab)⊆in(NLab′) and out(NLab)⊆out(NLab′) it follows that undec(NLab′)⊆undec(NLab). Contradiction.
from 5 to 3	Let NLab be a complete labelling where in(NLab) is not minimal. Then there exists a complete labelling NLab′ with in(NLab′)⊊in(NLab). It then follows from Lemma 59 that out(NLab′)⊊out(NLab), so undec(NLab)⊊undec(NLab′).
uniqueness grounded node labelling	Shown in [35].

□

Appendix E.

Appendix E.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 in are equal to the complete arrow labellings with maximal out, and that the complete arrow labelling where in is minimal is unique and equal to both the complete arrow labelling where out is minimal and the complete arrow labelling where undec is maximal (Theorem 64).

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

Theorem 61.

Let SF=(N,arr) be a SETAF and let ALab be an arrow labelling of SF. ALab is a complete arrow labelling of SF iff for every (M,A)∈arr it holds that:

(1) ALab((M,A))=in iff for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out
(2) ALab((M,A))=out iff there exists a (M′,B)∈arr with B∈M such that ALab((M′,B))=in

Proof.

“⇒”: Let ALab be a complete arrow labelling of SF. Point 1 LTR follows directly from the first bullet of Definition 20. As for point 1 RTL, suppose that for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out. Then ALab((M,A)) cannot be out (otherwise there would have to be a (M′,B)∈arr with B∈M such that ALab((M′,B))=in) and cannot be undec (otherwise not for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out). Since ALab((M,A)) can only be in, out or undec, it then follows that ALab((M,A))=in.

Point 2 LTR follows directly from the second bullet of Definition 20. As for point 2 RTL, suppose that there exists a (M′,B)∈arr with B∈M such that ALab((M′,B))=in. Then ALab((M,A)) cannot be in (otherwise for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out) and cannot be undec (otherwise there does not exist a (M′,B)∈arr with B∈M such that ALab((M′,B))=in). Since ALab((M′,B)) can only be in, out or undec, it follows that ALab((M,A))=out.

“⇐”: Let ALab be an arrow labelling satisfying points 1 and 2. We now need to show that ALab also satisfies the first three bullets of Definition 20. The first bullet follows directly from point 1. The second bullet follows directly from point 2. As for the third bullet, take an arbitrary (M,A)∈arr such that ALab((M,A))=undec. The fact that ALab((M,A))≠in, together with point 1, then implies that not for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out. The fact that ALab((M,A))≠out, together with point 2, then implies that there does not exist a (M′,B)∈arr with B∈M such that ALab((M′,B))=in. □

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.

Lemma 62.

Let ALab1 and ALab2 be complete arrow labellings of SETAF SF=(N,arr). It holds that:

(1) in(ALab1)⊆in(ALab2) iff out(ALab1)⊆out(ALab2)
(2) in(ALab1)=in(ALab2) iff out(ALab1)=out(ALab2)
(3) in(ALab1)⊊in(ALab2) iff out(ALab1)⊊out(ALab2)

Proof.

(1) “⇒”: Suppose in(ALab1)⊆in(ALab2). Let (M,A)∈out(ALab1). This means that (Definition 20, second bullet point) there exists a (M′,B)∈arr such that B∈M and ALab1((M′,B))=in. That is, (M′,B)∈in(ALab1). The fact that in(ALab1)⊆in(ALab2) then implies that (M′,B)∈in(ALab2). This, together with the fact that ALab2 is a complete arrow labelling implies (by point 2 of Theorem 61) that (M,A)∈out(ALab2).
“⇐”: Suppose out(ALab1)⊆out(ALab2). Let (M,A)∈in(ALab1). This means that (Definition 20, first bullet point) that for each (M′,B)∈arr with B∈M it holds that (M′,B)∈out(ALab1). The fact that out(ALab1)⊆out(ALab2) then implies that (M′,B)∈out(ALab2). This, together with the fact that ALab2 is a complete arrow labelling implies (by point 1 of Theorem 61) that (M,A)∈in(ALab2).
(2) This follows directly from point 1.
(3) This follows directly from point 1 and point 2.

□

Lemma 63.

Let ALab1 and ALab2 be complete arrow labellings of SETAF SF=(N,arr). It holds that:

(1) if in(ALab1)⊆in(ALab2) then undec(ALab1)⊇undec(ALab2)
(2) if in(ALab1)=in(ALab2) then undec(ALab1)=undec(ALab2)
(3) if in(ALab1)⊊in(ALab2) then undec(ALab1)⊋undec(ALab2)
(4) if out(ALab1)⊆out(ALab2) then undec(ALab1)⊇undec(ALab2)
(5) if out(ALab1)=out(ALab2) then undec(ALab1)=undec(ALab2)
(6) if out(ALab1)⊊out(ALab2) then undec(ALab1)⊋undec(ALab2)

Proof.

(1) Suppose in(ALab1)⊆in(ALab2). Then (Lemma 62, point 1) it follows that out(ALab1)⊆out(ALab2). Let (M,A)∈undec(ALab2). Then (M,A)∉in(ALab2) so (M,A)∉in(ALab1). Also, (M,A)∉out(ALab2) so (M,A)∉out(ALab1). From the fact that (M,A) is labelled either in, out or undec by ALab1, it follows that (M,A)∈undec(ALab1).
(2) This follows directly from point 1.
(3) Assume in(ALab1)⊊in(ALab2). From point 1 of this lemma it follows undec(ALab1)⊇undec(ALab2). From Lemma 62 (point 3) it follows out(ALab1)⊊out(ALab2). But since every arrow is labelled either in, out, or undec, this means that in(ALab2)∖in(ALab1)⊆undec(ALab1) and out(ALab2)∖out(ALab1)⊆undec(ALab1), which gives us undec(ALab1)⊋undec(ALab2).
(4) This follows directly from Lemma 62 (point 1) and point 1 of this lemma.
(5) This follows directly from point 4.
(6) Assume out(ALab1)⊊out(ALab2). From Lemma 62 (point 3) it follows in(ALab1)⊊in(ALab2). Then undec(ALab1)⊋undec(ALab2) follows from point 3 of this lemma.

□

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

Theorem 64.

Let SF=(N,arr) be a SETAF, and let ALab be a complete arrow labelling of SF. The following two statements are equivalent:

1.	in(ALab) is maximal (w.r.t. set inclusion) among all complete arrow labellings of SF
2.	out(ALab) is maximal (w.r.t. set inclusion) among all complete arrow labellings of SF

The following three statements are also equivalent:

3.	in(ALab) is minimal (w.r.t. set inclusion) among all complete arrow labellings of SF
4.	out(ALab) is minimal (w.r.t. set inclusion) among all complete arrow labellings of SF
5.	undec(ALab) is maximal (w.r.t. set inclusion) among all complete arrow labellings of SF

Furthermore, it holds that the complete arrow labelling with minimal in is unique.

Proof.

from 1 to 2	Suppose in(ALab) is maximal among all complete arrow labellings of SF. That is, there is no complete arrow labelling ALab′ of SF such that in(ALab)⊊in(ALab′). Suppose, towards a contradiction, that out(ALab) is not maximal among all complete arrow labellings of SF. Then there exists a complete arrow labelling ALab′ such that out(ALab)⊊out(ALab′). It then follows from Lemma 62 (point 3) that in(ALab)⊊in(ALab′). Contradiction.
from 2 to 1	Similar to the previous point.
from 3 to 4	Suppose in(ALab) is minimal among all complete arrow labellings of SF. That is, there is no complete arrow labelling ALab′ of SF such that in(ALab′)⊊in(ALab). Suppose, towards a contradiction, that out(ALab) is not minimal among all complete arrow labellings of SF. Then there exists a complete arrow labelling ALab′ such that out(ALab′)⊊out(ALab). It then follows from Lemma 62 (point 3) that in(ALab′)⊊in(ALab). Contradiction.
from 4 to 3	Similar to the previous point.
from 5 to 3	Suppose undec(ALab) is maximal among all complete arrow labellings of SF. That is, there is no complete arrow labelling ALab′ of SF such that undec(ALab)⊊undec(ALab′). Suppose, towards a contradiction, that in(ALab) is not maximal among all complete arrow labellings of SF. Then there exists a complete arrow labelling ALab′ such that in(ALab)⊊in(ALab′). It then follows from Lemma 63 (point 3) that undec(ALab′)⊊undec(ALab). Contradiction.

As for the last point to be proved (from 3 to 5), a particular difficulty is that we cannot just use the same proof strategy as the previous point (from 5 to 3). This is because point 3 of Lemma 63 only goes one-way (it’s an “if” instead of an “iff”). To overcome this, we will need to make use of the uniqueness of the grounded arrow labelling.

uniqueness grounded arrow labelling

Suppose ALab1 and ALab2 are complete arrow labellings of SF with minimal in. That is, they are grounded arrow labellings of SF. From Theorem 21 (point 3)12 12 it follows that NLab1=ALab2NLab(ALab1) and NLab2=ALab2NLab(ALab2) are grounded node labellings of SF. However, since the grounded node labelling is unique [35] it follows that NLab1=NLab2, so also NLab2ALab(NLab1)=NLab2ALab(NLab2). However, since NLab2ALab(NLab1)=ALab1 and NLab2ALab(NLab2)=ALab2 (Theorem 21 point 2) it follows that ALab1=ALab2.

Using the uniqueness of the grounded arrow labelling, we can then proceed to show that point 3 implies point 5.

from 3 to 5

Suppose ALab1 is a complete arrow labelling of SF with minimal in. That is, ALab1 is a minimal element of the set of complete arrow labellings of SF (when applying an ordering based on set-inclusion on the in-labelled part of the labellings). As this minimal element is unique, it is also the smallest element, meaning that it is less or equal to each element of the set. That is, for each complete arrow labelling ALab′ of SF, it holds that in(ALab)⊆in(ALab′). From Lemma 63 (point 1) it then follows that undec(ALab′)⊆undec(ALab). It then follows that there is there is no complete arrow labelling ALab′ of SF such that undec(ALab)⊊undec(ALab′). That is, ALab is a complete arrow labelling with maximal undec.

□

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).

Appendix F.

Appendix F.Equivalence of node labellings and arrow labellings for SETAFs

Lemma 65.

Let SF=(N,arr) be a SETAF. If NLab is a complete node labelling of SF then ALab=NLab2ALab(NLab) is a complete arrow labelling of SF.

Proof.

We need to prove that the three bullet points of Definition 20 are satisfied. Let (M,A)∈arr. We distinguish three cases:

(1) ALab((M,A))=in. From the definition of NLab2ALab it then follows that NLab(B)=in for each B∈M. From the fact that NLab is a complete node labelling, it then follows that for every (M′,B)∈arr with B∈M there is a C∈M′ such that NLab(C)=out. From the definition of NLab2ALab it then follows that ALab((M′,B))=out.
(2) ALab((M,A))=out. From the definition of NLab2ALab it then follows that NLab(B)=out for some B∈M. From the fact that NLab is a complete node labelling, it then follows that there is an (M′,B)∈arr such that NLab(C)=in for each C∈M′. From the definition of NLab2ALab it then follows that ALab((M′,B))=in.
(3) ALab((M,A))=undec. From the definition of NLab2ALab it then follows that not for all B∈M:NLab(B)=in and there is no B∈M:NLab(B)=out. Since for each B∈M the label NLab(B) can only be in, out or undec, there is some B∈M such that NLab(B)=undec. From the fact that NLab is a complete node labelling, it then follows that not for each M′⊆N such that (M′,B)∈arr it holds that there is a C∈M′:NLab(C)=out and there does not exist an M′⊆N such that (M′,B)∈arr and ∀C∈M′:NLab(C)=in. From the definition of NLab2ALab it then follows that ALab((M′,B))=undec, which means that not for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out. From the fact that there is B∈M:NLab(B)=out and the fact that NLab is a complete node labelling it follows that there is no (M′,B)∈arr with B∈M such that ALab((M′,B))=in.

□

Lemma 66.

Let SF=(N,arr) be a SETAF. If ALab is a complete arrow labelling of SF then NLab=ALab2NLab(ALab) is a complete node labelling of SF.

Proof.

We need to prove that the three bullet points of Definition 17 are satisfied. Let A∈N. We distinguish three cases:

(1) NLab(A)=in. We need to show that for every (M,A)∈arr it holds that ∃B∈M:NLab(B)=out. Let (M,A)∈arr be an arbitrary arrow towards A. From the definition of ALab2NLab and the fact that NLab(A)=in it follows that ALab((M,A))=out. From the fact that ALab is a complete arrow labelling it then follows that there exists a (M′,B)∈arr with B∈M such that ALab((M′,B))=in. From the definition of ALab2NLab it then follows that NLab(B)=out.
(2) NLab(A)=out. We need to show that there exists a (M,A)∈arr such that ∀B∈M:NLab(B)=in. From the definition of ALab2NLab and the fact that NLab(A)=out it follows that there is a (M,A)∈arr such that ALab((M,A))=in. From the fact that ALab is a complete arrow labelling, it then follows that for each (M,B)∈arr such that B∈M, it holds that ALab((M,B))=out. From the definition of ALab2NLab, it then follows that NLab(B)=in.
(3) NLab(A)=undec. We need to show that not for all (M,A)∈arr it holds that ∃B∈M:NLab(B)=out, and that there is no (M,A)∈arr such that ∀B∈M:NLab(B)=in. From the definition of ALab2NLab and the fact that NLab(A)=undec it follows that (i) not for all (M,A)∈arr it holds that ALab((M,A))=out, and (ii) there is no (M,A)∈arr such that ALab((M,A))=in. From (i) it follows that there is a (M,A)∈arr such that ALab((M,A))≠out. From the fact that ALab is a complete arrow labelling, it then follows that there is no (M′,B)∈arr such that ALab((M′,B))=in, which from the definition of ALab2NLab implies that NLab(B)≠out. From (ii) it follows that for each (M,A)∈arr it holds that ALab((M,A))≠in. Let (M,A)∈arr be an arbitrary arrow towards A. It directly follows that ALab((M,A))≠in. From the fact that ALab is a complete arrow labelling, it follows that there is a (M′,B)∈arr with B∈M such that ALab((M′,B))≠out. From the definition of ALab2NLab, it then follows that NLab(B)≠in.

□

Lemma 67.

Let NLab be a complete node labelling of SETAF SF=(N,arr). It holds that ALab2NLab(NLab2ALab(NLab))=NLab.

Proof.

Let ALab=NLab2ALab(NLab). It suffices to prove the following three properties, for an arbitrary A∈N.

(1) If NLab(A)=in then ALab2NLab(ALab)(A)=in.
Suppose NLab(A)=in. Then from NLab being a complete node labelling, it follows that for each (M,A)∈arr it holds that NLab(B)=out for some B∈M, which from the definition of NLab2ALab implies that ALab((M,A))=out. From the definition of ALab2NLab it then follows that ALab2NLab(ALab)(A)=in.
(2) If NLab(A)=out then ALab2NLab(ALab)(A)=out.
Suppose NLab(A)=out. Then from NLab being a complete node labelling, it follows that there is a (M,A)∈arr such that ∀B∈M:NLab(B)=in, which from the definition of NLab2ALab implies that ALab((M,A))=in. From the definition of ALab2NLab it then follows that ALab2NLab(ALab)(A)=out.
(3) If NLab(A)=undec then ALab2NLab(ALab)(A)=undec.
Suppose NLab(A)=undec. Then from NLab being a complete node labelling, it follows that (i) not for each (M,A)∈arr it holds that NLab(B)=out for some B∈M, and (ii) there is no (M,A)∈arr such that ∀B∈M:NLab(B)=in. From (i) it directly follows that there exists a (M,A)∈arr such that NLab(B)≠out for some B∈M, thus ALab((M,A))≠out. Then, from the definition of ALab2NLab it follows that ALab2NLab(ALab)(A)≠in. From (ii) it directly follows that for each (M,A)∈arr it holds that ¬∀B∈M:NLab(B)=in. Then, from the definition of NLab2ALab it follows that ALab((M,A))≠in. Then, from the definition of ALab2NLab it follows that ALab2NLab(ALab)(A)≠out. This, together with the earlier obtained fact that ALab2NLab(ALab)(A)≠in implies that ALab2NLab(NLab)(A)=undec.

□

Lemma 68.

Let ALab be a complete arrow labelling of SETAF SF=(N,arr). It holds that NLab2ALab(ALab2NLab(ALab))=ALab.

Proof.

Let NLab=ALab2NLab(ALab). It suffices to prove the following three properties, for an arbitrary (M,A)∈arr.

(1) If ALab((M,A))=in then NLab2ALab(NLab)((M,A))=in.
Suppose ALab((M,A))=in. Then from the fact that ALab is a complete arrow labelling, it follows that for each (M′,B)∈arr with B∈M, ALab((M′,B))=out. From the definition of ALab2NLab it then follows that NLab(B)=in. From the definition of NLab2ALab it then follows that NLab2ALab(NLab)((M,A))=in.
(2) If ALab((M,A))=out then NLab2ALab(NLab)((M,A))=out.
Suppose ALab((M,A))=out. Then, from the fact that ALab is a complete arrow labelling, it follows that there exists a (M′,B)∈arr with B∈M such that ALab((M′,B))=in. From the definition of ALab2NLab it then follows that NLab(B)=out. From the definition of NLab2ALab it then follows that NLab2ALab(NLab)((M,A))=out.
(3) If ALab((M,A))=undec then NLab2ALab(NLab)((M,A))=undec.
Suppose ALab((M,A))=undec. Then from the fact that ALab is a complete arrow labelling, it follows that (i) not for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out, and (ii) there is no (M′,B)∈arr with B∈M such that ALab((M′,B))=in. From (i) it directly follows that there is a (M′,B)∈arr with B∈M such that ALab((M′,B))≠out. From the definition of ALab2NLab it then follows that NLab(B)≠in. From the definition of NLab2ALab it then follows that NLab2ALab(NLab)((M,A))≠in. From (ii) it directly follows that for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))≠in. From the definition of ALab2NLab it then follows that NLab(B)≠out. From the definition of NLab2ALab it then follows that NLab2ALab(NLab)((M,A))≠out. From this, together with the earlier observed fact that NLab2ALab(NLab)((M,A))≠in, it follows that NLab2ALab(NLab)((M,A))=undec.

□

Lemma 69.

Let NLab1 and NLab2 be complete node labellings of a SETAF SF=(N,arr). Let ALab1=NLab2ALab(NLab1) and ALab2=NLab2ALab(NLab2). It holds that:

(1) in(NLab1)⊆in(NLab2) iff in(ALab1)⊆in(ALab2).
(2) in(NLab1)=in(NLab2) iff in(ALab1)=in(ALab2).
(3) in(NLab1)⊊in(NLab2) iff in(ALab1)⊊in(ALab2).
(4) out(NLab1)⊆out(NLab2) iff out(ALab1)⊆out(ALab2).
(5) out(NLab1)=out(NLab2) iff out(ALab1)=out(ALab2).
(6) out(NLab1)⊊out(NLab2) iff out(ALab1)⊊out(ALab2).

Proof.

(1) “⇒”: Suppose in(NLab1)⊆in(NLab2). Let (M,A)∈in(ALab1). Then, from the definition of NLab2ALab it follows that ∀B∈M:B∈in(NLab1). The fact that in(NLab1)⊆in(NLab2) then implies that ∀B∈M:B∈in(NLab2). From the definition of NLab2ALab it then follows that (M,A)∈in(ALab2).
“⇐”: Suppose in(ALab1)⊆in(ALab2). Let A∈in(NLab1). First assume that there is a set of nodes M⊆in(NLab1)⊆N and a node B∈N such that (M,B)∈arr, i.e., A is involved in an outgoing arrow that is “in”. Then, from the definition of NLab2ALab it follows that (M,B)∈in(ALab1). The fact that in(ALab1)⊆in(ALab2) then implies that (M,B)∈in(ALab2). From the definition of NLab2ALab it then follows that A∈in(NLab2) and we are done. Now on the other hand assume that there is no arrow (M,B)∈arr with A∈M⊆in(NLab1), i.e., A is not involved in an outgoing arrow that is “in”. Towards contradiction assume that A∉in(NLab2). This means either A is not defended by in(NLab2) or there is some M⊆in(NLab2) such that (M,A)∈arr. Since we assume A∈in(NLab1) and NLab1 is complete we know that for each (M′,A)∈arr towards A there is a counter-attack (M″,C)∈arr with C∈M′ and M″⊆in(NLab1). From the definition of NLab2ALab it then follows that (M″,C)∈in(ALab1). From in(ALab1)⊆in(ALab2) we then get (M″,C)∈in(ALab2) and, hence, from the definition of NLab2ALab we get D∈in(NLab2) for each D∈M″. Since we chose an arbitrary attacker M′ of A, we know that A is defended by in(NLab2). It remains to handle the case where there is some M⊆in(NLab2) such that (M,A)∈arr, i.e., A is not in in(NLab2) due to a conflict. However, since NLab1 is complete this means that there is some B∈M such that B∈out(NLab1), and therefore (M,A)∈out(ALab1). From this and the fact that in(ALab1)⊆in(ALab2) and from Lemma 62 (point 1) we get (M,A)∈out(ALab2), which gives us from the definition of NLab2ALab that for some B∈M it holds B∈out(NLab2), a contradiction to our assumption M⊆in(NLab2).
(2) This follows directly from point 1.
(3) This follows directly from point 1 and point 2.
(4) “⇒”: Suppose out(NLab1)⊆out(NLab2). Let (M,A)∈out(ALab1). Then, from the definition of NLab2ALab it follows that B∈out(NLab1) for some B∈M. The fact that out(NLab1)⊆out(NLab2) then implies that B∈out(NLab2). From the definition of NLab2ALab it then follows that (M,A)∈out(ALab2).
“⇐”: Suppose out(ALab1)⊆out(ALab2). Let A∈out(NLab1). Then, since NLab1 is complete, there is a (M,A)∈arr such that M⊆in(NLab1). From the definition of NLab2ALab it follows that (M,A)∈in(ALab1). From our assumption out(ALab1)⊆out(ALab2) and Lemma 62 (point 1) we get in(ALab1)⊆in(ALab2), and therefore (M,A)∈in(ALab2). From the definition of NLab2ALab it follows that M⊆in(NLab2), and since NLab2 is complete we get A∈out(NLab2).
(5) This follows directly from point 4.
(6) This follows directly from point 4 and point 5.

□

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 undec(NLab1)⊆undec(NLab2) then undec(ALab1)⊆undec(ALab2). A counter example is SF in Example 70: We have undec(NLab2)⊆undec(NLab3) but undec(ALab2)⊈undec(ALab3).
7’ If undec(ALab1)⊆undec(ALab2) then undec(NLab1)⊆undec(NLab2). A counter example is AF in Example 9: We have undec(ALab2)⊆undec(ALab3) but undec(NLab2)⊈undec(NLab3).
8 If undec(NLab1)=undec(NLab2) then undec(ALab1)=undec(ALab2). A counter example is SF in Example 70: We have undec(NLab2)=undec(NLab3) but undec(ALab2)≠undec(ALab3).
8’ If undec(ALab1)=undec(ALab2) then undec(NLab1)=undec(NLab2). A counter example is AF in Example 9: We have undec(ALab2)=undec(ALab3) but undec(NLab2)≠undec(NLab3).
9 If undec(NLab1)⊊undec(NLab2) then undec(ALab1)⊊undec(ALab2). A counter example is AF in Example 9: We have undec(NLab3)⊊undec(NLab2) but undec(NLab3)⊊̸undec(NLab2).
9’ If undec(ALab1)⊊undec(ALab2) then undec(NLab1)⊊undec(NLab2). A counter example is AF in Example 10: We have undec(ALab3)⊊undec(ALab2) but undec(NLab3)⊊̸undec(NLab2).

Example 70.

Let SF=(N,arr) be a SETAF with N={A,B,C,D,E} and

arr={(∅,A),({A},B),({B},B),({B,C},E),({C},D),({D},C),(∅,E)}.

SF has three complete node labellings:

NLab1=(∅,{A,E},{B,C,D})NLab2=({C},{A,D,E},{B})NLab3=({D},{A,C,E},{B})

and three complete arrow labellings:

ALab1=({(∅,A),(∅,E)},{({A},B)},{({B},B),({B,C},E),({C},D),({D},C)})ALab2=({(∅,A),({C},D),(∅,E)},{({A},B),({D},C)},{({B},B),({B,C},E)})ALab3=({(∅,A),({D},C),(∅,E)},{({A},B),({B,C},E),({C},D)},{({B},B)})

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

Lemma 71.

Let ALab1 and ALab2 be complete arrow labellings of SETAF SF=(N,arr). Let NLab1=ALab2NLab(ALab1) and NLab2=ALab2NLab(ALab2). It holds that:

(1) in(ALab1)⊆in(ALab2) iff in(NLab1)⊆in(NLab2).
(2) in(ALab1)=in(ALab2) iff in(NLab1)=in(NLab2).
(3) in(ALab1)⊊in(ALab2) iff in(NLab1)⊊in(NLab2).
(4) out(ALab1)⊆out(ALab2) iff out(NLab1)⊆out(NLab2).
(5) out(ALab1)=out(ALab2) iff out(NLab1)=out(NLab2).
(6) out(ALab1)⊊out(ALab2) iff out(NLab1)⊊out(NLab2).

Proof.

(1) “⇒”: Suppose in(ALab1)⊆in(ALab2). Let A∈in(NLab1). Then, from the definition of ALab2NLab it follows that for every (M,A)∈arr, (M,A)∈out(ALab1). From the fact that in(ALab1)⊆in(ALab2) it follows that (Lemma 62) out(ALab1)⊆out(ALab2), so (M,A)∈out(ALab2). From the definition of ALab2NLab it then follows that NLab2(A)=in. That is, A∈in(NLab2).
“⇐”: Suppose in(NLab1)⊆in(NLab2). Let (M,A)∈in(ALab1). Since we assume that ALab1 is complete, it follows that for every (M′,B)∈arr towards some B∈M it holds (M′,B)∈out(ALab1), which in turn means for each of these (M′,B)∈arr there is some (M″,C)∈arr with C∈M′ and (M″,C)∈in(ALab1). Then, from the definition of ALab2NLab it then follows that C∈out(NLab1). From in(NLab1)⊆in(NLab2) and Lemma 59 (point 1) we then get out(NLab1)⊆out(NLab2). From this and C∈out(NLab1) we get C∈out(NLab2). Then from the definition of ALab2NLab it follows (M″,C)∈in(ALab2), and then since ALab2 is complete we get (M′,B)∈out(ALab2) and consequently (M,A)∈in(ALab2).
(2) This follows directly from point 1.
(3) This follows directly from point 1 and point 2.
(4) “⇒”: Suppose out(ALab1)⊆out(ALab2). Let A∈out(NLab1). Then, from the definition of ALab2NLab it follows that there exists a (M,A)∈arr such that (M,A)∈in(ALab1). From the fact that out(ALab1)⊆out(ALab2) it follows that (Lemma 62) in(ALab1)⊆in(ALab2), so (M,A)∈in(ALab2). From the definition of ALab2NLab it then follows that NLab2(A)=out. That is, A∈out(NLab2).
“⇐”: Suppose out(NLab1)⊆out(NLab2). Let (M,A)∈out(ALab1). Since we assume that ALab1 is complete, it follows that there exists a (M′,B) towards some B∈M such that (M′,B)∈in(ALab1). By completeness this means that for every (M″,C)∈arr towards some C∈M′ it holds (M″,C)∈out(ALab1). Then, from the definition of ALab2NLab it follows that C∈in(NLab1), and since this is the case for every C∈M′ we get M′⊆in(NLab1). From out(NLab1)⊆out(NLab2) and Lemma 62 we then get in(NLab1)⊆in(NLab2). From this and M′⊆in(NLab1) we get M′⊆in(NLab2). Then from the definition of ALab2NLab it follows that for each B∈M there is a C∈M′ such that (M″,C)∈out(ALab2) and hence (M′,B)∈in(ALab2), and then since ALab2 is complete we get (M,A)∈out(ALab2).
(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 NLab2ALab and ALab2NLab are each others inverses (see Theorem 21, point 2).

Lemma 72.

Let SF=(N,arr) be a SETAF.

(1) If NLab is a grounded node labelling of SF then NLab2ALab(NLab) is a grounded arrow labelling of SF.
(2) If ALab is a grounded arrow labelling of SF then ALab2NLab(ALab) is a grounded node labelling of SF.

Proof.

(1) Let NLab be a grounded node labelling of SF. Since a grounded node labelling is also a complete node labelling, it follows (Lemma 65) that ALab=NLab2ALab(NLab) is a complete arrow labelling. Suppose, towards a contradiction, that ALab does not have minimal in. That is, there exists a complete arrow labelling ALab′ such that in(ALab′)⊊in(ALab). From point 3 of Lemma 71 it then follows that in(ALab2NLab(ALab′))⊊in(ALab2NLab(ALab)). Let NLab′=ALab2NLab(ALab′). It follows (Lemma 66) that NLab′ is a complete node labelling. Furthermore, it follows from Lemma 67 that ALab2NLab(ALab)=NLab. Hence, we obtain in(NLab′)⊊in(NLab). But this is impossible since NLab is a grounded node labelling and therefore has minimal in among all complete node labellings.
(2) Let ALab be a grounded arrow labelling of SF. Since a grounded arrow labelling is also a complete arrow labelling, it follows (Lemma 66) that NLab=ALab2NLab(ALab) is a complete node labelling. Suppose, towards a contradiction, that NLab does not have minimal in. That is, there exists a complete node labelling NLab′ such that in(NLab′)⊊in(NLab). From point 3 of Lemma 69 it then follows that in(NLab2ALab(NLab′))⊊in(NLab2ALab(NLab)). Let ALab′=NLab2ALab(NLab′). It follows (Lemma 65) that ALab′ is a complete arrow labelling. Furthermore, it follows from lemma 68 that NLab2ALab(NLab)=ALab. Hence, we obtain in(ALab′)⊊in(ALab). But this is impossible since ALab is a grounded arrow labelling and therefore has minimal in among all complete arrow labellings.

□

Lemma 73.

Let SF=(N,arr) be a SETAF.

(1) If NLab is a preferred node labelling of SF then NLab2ALab(NLab) is a preferred arrow labelling of SF.
(2) If ALab is a preferred arrow labelling of SF then ALab2NLab(ALab) is a preferred node labelling of SF.

Proof.

Similar to the proof of Lemma 72 □

Lemma 74.

Let SF=(N,arr) be a SETAF.

(1) If NLab is a stable node labelling of SF then NLab2ALab(NLab) is a stable arrow labelling of SF.
(2) If ALab is a stable arrow labelling of SF then ALab2NLab(ALab) is a stable node labelling of SF.

Proof.

(1) Let NLab be a stable node labelling of SF. Since a stable node labelling is also a complete node labelling, it follows (Lemma 65) that ALab=NLab2ALab(NLab) is a complete arrow labelling. In order to prove that ALab is also a stable arrow labelling, we need to show that no arrow is labelled undec. Let (M,A)∈arr. The fact that NLab is a stable node labelling implies that all B∈M are labelled either in or out. We distinguish two cases (i) and (ii). (i) In case for all B∈M it holds NLab(B)=in, it follows from the definition of NLab2ALab that ALab((M,A))=in. (ii) In case NLab(B)=out for at least one B∈M, it follows from the definition of NLab2ALab that ALab((M,A))=out. In both cases, ALab((M,A))≠undec.
(2) Let ALab be a stable arrow labelling of SF. Since a stable arrow labelling is also a complete arrow labelling, it follows (Lemma 66) that NLab=ALab2NLab(ALab) is a complete node labelling. In order to prove that NLab is also a stable node labelling, we need to show that no node is labelled undec. Let A∈N and let a be the set of arrows towards A. The fact that ALab is a stable arrow labelling means that for every (M,A)∈a it holds that ALab((M,A)) is either in or out. This implies that either (i) there exists a (M,A)∈a such that ALab((M,A))=in, or (ii) for each (M,A)∈a it holds that ALab((M,A))=out. In the case (i), it follows from the definition of ALab2NLab that NLab(A)=out. In case (ii), it follows from the definition of ALab2NLab that NLab(A)=in. In both cases it holds that NLab(A)≠undec.

□

Remark 75.

Notice that it does not hold that if NLab is a semi-stable node labelling of SF then NLab2ALab(NLab) is a semi-stable arrow labelling of SF. Example 10 provides a counter example: while NLab2 is a semi-stable node labelling, ALab2 is not a semi-stable arrow labelling. Neither does the other direction hold (i.e., if ALab is a semi-stable arrow labelling of SF then ALab2NLab(ALab) is a semi-stable node labelling of SF), Example 9 provides a counter example: while ALab2 is a semi-stable arrow labelling, NLab2 is not a semi-stable node labelling. As SETAFs generalise AFs and the functions NLab2ALab and ALab2NLab generalise the functions NLab2ALab and ALab2NLab respectively, the same counter examples apply in the case of SETAFs as with AFs.

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 SF=(N,arr) be a SETAF and let NLab and ALab be a node labelling and an arrow labelling of SF, respectively. It holds that:

(1) If NLab is a complete node labelling, then NLab2ALab(NLab) is a complete arrow labelling.
If ALab is a complete arrow labelling, then ALab2NLab(ALab) is a complete node labelling.
(2) When restricted to complete node labellings and complete arrow labellings, the functions ALab2NLab and NLab2ALab become bijections and each other’s inverses.
(3) If NLab is a grounded node labelling, then NLab2ALab(NLab) is a grounded arrow labelling.
If ALab is a grounded arrow labelling, then ALab2NLab(ALab) is a grounded node labelling.
(4) If NLab is a preferred node labelling, then NLab2ALab(NLab) is a preferred arrow labelling.
If ALab is a preferred arrow labelling, then ALab2NLab(ALab) is a preferred node labelling.
(5) If NLab is a stable node labelling, then NLab2ALab(NLab) is a stable arrow labelling.
If ALab is a stable arrow labelling, then ALab2NLab(ALab) 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.

□

Appendix G.

Appendix G.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 (arr) are a subset of 2N×N in Definition 11, they are a subset of (2N∖∅)×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 out) 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.

Definition 11.

An argumentation framework with set attacks (SETAF) is a tuple SF=(N,arr) where N is a finite set of nodes, whose structure can be left implicit, and arr⊆2N×N.

Definition 76

Definition 76([42]).

An argumentation framework with collective attacks is a tuple SF=(N,arr) where N is a finite set of nodes, whose structure can be left implicit, and arr⊆(2N∖∅)×N.

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).

Definition 77.

Let SETAF2collAF:{SF|SF is a SETAF}→{SF|SF is a AF with collective attacks} be defined as follows: for a SETAF SF=(N,arr), we obtain the corresponding AF with collective attacks SETAF2collAF(SF)=(N′,arr′) with

N′={A∈N|∄(∅,A)∈arr},arr′={(M,A)∈arr|M≠∅,A∈N′,M⊆N′}=arr|(2N′∖∅)×N′.

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

Definition 78.

Two SETAFs SF1,SF2 are equivalent to each other (SF1≡SF2) iff

SETAF2collAF(SF1)=SETAF2collAF(SF2).

By CSETAF2collAF(SF)={SF′|SF≡SF′}, we denote the equivalence class of SETAF SF.

Each AF with collective attacks SF corresponds to an equivalence class CSF 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 SF is contained in the equivalence class CSF (it is the smallest SETAF contained in the class). For instance, the empty AF with collective attacks (∅,∅) is the minimal representative of the equivalence class

C(∅,∅)={(N,arr)|∀A∈N:(∅,A)∈arr}.

Interestingly, it can be the case that the empty set is stable in a given SETAF SF=(N,arr) although it contains nodes, i.e., N≠∅. For instance, the SETAF SF=(N,arr) with N={A,B} and arrows arr={(∅,A),(∅,B),({A,B},A)} admits an empty stable extension. We observe that the considered SETAF belongs to the equivalence class C(∅,∅) 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 SF=(N,arr), we write

cf(SF)={M⊆N|N is conflict-free in SF}.

Proposition 79.

Let SF=(N,arr) be a SETAF and let SETAF2collAF(SF)=SF′=(N′,arr′) be its corresponding AF with collective attacks. Then

(1) cf(SF)=cf(SF′);
(2) MSF+|N′=MSF′+|N′ for all M∈cf(SF)=cf(SF′);
(3) FSF(M)=FSF′(M) for all M∈cf(SF)=cf(SF′).

Proof.

By definition, we have N′⊆Nh and arr′⊆arr. Let A∅=N∖N′ denote all nodes that are attacked by the empty set in SF.

(1) We show cf(SF)=cf(SF′). First, consider a conflict-free set M∈cf(SF). By definition, M is not attacked by any subset of M; therefore, (∅,A)∉arr for any A∈M. Hence M⊆N′. Since arr′⊆arr, i.e., we do not add new attacks in the corresponding AF with collective attacks, we conclude that M is conflict-free in SF′, that is, M∈cf(SF′).
Now, consider a set M∈cf(SF′). We have M∈N′, hence (∅,A)∉arr for all A∈M, moreover, for all attacks (b,A)∈arr∖arr′ it holds that b∩A∅≠∅ (in the translation, we delete only attacks that involve arguments that are attacked by the empty set). Therefore, M∈cf(SF).
(2) Consider a conflict-free set M∈cf(SF)=cf(SF′). We show that MSF+|N′=MSF′+|N′, i.e., M attacks the same nodes in N′ in both SF and SF′. From arr′⊆arr we obtain MSF′+|N′⊆MSF+|N′. For the other direction, consider a node A∈MSF+|N′. Then there is (M′,A)∈arr with M′⊆M. It holds that M′∈N′ since M∈N′, therefore (M′,A)∈arr′. Hence A∈MSF′+|N′. We obtain MSF+|N′=MSF′+|N′, as desired.
(3) Consider a conflict-free set M∈cf(SF)=cf(SF′). We show that M defends the same nodes in SF and SF′.
First, we observe that M can only defend nodes in N∖A∅=N′ since the empty set cannot be counter-attacked.
Now, consider a node A∈N′. As shown above (cf. 2.), M attacks the same nodes in N′ in both frameworks SF and SF′. Hence, A is defended against the same attacks (b,A) with b⊆Nh′ in both SF and SF′. It remains to argue that A is defended against all attacks in arr∖arr′: consider an attack (b,A) with b⊈N′. That is, b contains some argument B∈A∅ that is attacked by the empty set. Since each set contains the empty set, A is defended against this attack in SF.

□

We obtain the following.

Theorem 80.

Let SF=(N,arr) be a SETAF and let SETAF2collAF(SF)=SF′=(N′,arr′) be its corresponding AF with collective attacks. Then cf(SF)=cf(SF′), moreover, for all M∈cf(SF),

M is admissible in SF iff M is admissible in SF′;
M is complete in SF iff M is complete in SF′;
M is grounded in SF iff M is grounded in SF′;
M is preferred in SF iff M is preferred in SF′;
M is stable in SF iff M is stable in SF′;
M is semi-stable in SF iff M is semi-stable in SF′.

Proof.

As shown above, the conflict-free sets coincide, and the characteristic function restricted to the conflict-free sets yields the same output. Hence, by definition, the statement follows for admissible, complete, preferred, grounded semantics. Regarding range-based semantics, it suffices to observe that for all sets M⊆N, it holds that N∖N′⊆MhSF+ (since ∅⊆M). That is, all arguments attacked by the empty set are contained in the range of M. We obtain that semi-stable and stable semantics coincide. □

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

Corollary 81.

Let SF be a SETAF and let CSETAF2collAF(SF) be its corresponding equivalence class. Then σ(SF1)=σ(SF2) for any two SETAFs SF1,SF2∈CSETAF2collAF(SF), for any semantics σ considered in this paper.

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 SF=(N,arr) be a SETAF, let SETAF2collAF(SF)=SF′=(N′,arr′) be its corresponding AF with collective attacks, and let A∅=N∖N′ denote all nodes that are attacked by the empty set in SF. Then,

for each SETAF node labelling NLab for SF, let NLab′=NLab|Nh′ denote the SETAF node labelling restricted to SF′. It holds that
- ∗ NLab is complete on SF iff NLab′ is complete on SF′;
- ∗ NLab is grounded on SF iff NLab′ is grounded on SF′;
- ∗ NLab is preferred on SF iff NLab′ is preferred on SF′;
- ∗ NLab is stable on SF iff NLab′ is stable on SF′;
- ∗ NLab is semi-stable on SF iff NLab′ is semi-stable on SF′.
for each SETAF node labelling NLab′ for SF′, let NLab=NLab∪{(A,out)|A∈A∅} denote the extension of NLab′ to the set of nodes in A∅ (observe that each such node is assigned out). It holds that
- ∗ NLab′ is complete on SF′ iff NLab is complete on SF;
- ∗ NLab′ is grounded on SF′ iff NLab is grounded on SF;
- ∗ NLab′ is preferred on SF′ iff NLab is preferred on SF;
- ∗ NLab′ is stable on SF′ iff NLab is stable on SF;
- ∗ NLab′ is semi-stable on SF′ iff NLab is semi-stable on SF.

Proof.

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

First, let NLab be a complete labelling for SF, and let NLab′=NLab|Nh′ denote the SETAF node labelling restricted to SF′. We show that NLab is complete on SF iff NLab′ is complete on SF′:

from left to right	By Theorem 58, in(NLab) is a complete node extension of SF. Moreover, by Theorem 80, in(NLab) is a complete node extension of M′. Applying Theorem 58 again, we obtain that in(NLab) induces a complete node labelling of SF′.
from right to left	Analogous to the other direction.

Now, let NLab′ be a complete node labelling for SF′ and let NLab=NLab∪{(A,out)|A∈A∅} denote the extension of NLab′ to the set of nodes in A∅. We show that NLab′ is complete on SF′ iff NLab is complete on SF:

from left to right	By Theorem 58, in(NLab′) is a complete node extension of SF′. By Theorem 80, in(NLab′) is a complete node extension of M. Applying Theorem 58 again, we obtain that in(NLab′) induces a complete node labelling of SF. Moreover, since each node A∈A∅ is attacked (by the empty set), we obtain that A is labelled out, as desired.
from right to left	Analogous to the first case above (the restriction of a complete node labelling of SF to SF′ is complete).

□

Appendix H.

Appendix H.Equivalence of arrow extensions and arrow labellings for argumentation frameworks

Definition 83.

Let (N,arr) be an argumentation framework and let a⊆arr be conflict-free. We define the function a2ALab(a)=(a,a+,arr∖(a∪a+)).

Definition 84.

Let (N,arr) be an argumentation framework and let ALab be an arrow labelling. We define the function ALab2a(ALab)=in(ALab).

Theorem 85.

Let (N,arr) be an argumentation framework.

(1) If a⊆arr is a complete extension then a2ALab(a) is a complete labelling.
(2) If ALab is a complete labelling then ALab2a(ALab) is a complete extension.

Proof.

(1) Let a2ALab(a)=ALab. Let a be a complete extension. We show that a2ALab(a)=ALab is a complete labelling:
- We show that ALab((A,B))=in implies ALab((C,A))=out for each arrow (C,A)∈arr. Let (A,B)∈in(ALab) and consider an arrow (C,A)∈arr. By Definition 84, in(ALab)=a. Since a is complete, the arrow (A,B) is defended by a (by Definition 6). Hence, (C,A)∈a+. By Definition 84, we obtain that (C,A)∈out(ALab).
- We show that ALab((A,B))=out implies ALab((C,A))=in for some (C,A)∈arr. Let (A,B)∈out(ALab). By Definition 84, (A,B)∈a+. That is, (A,B) is attacked by a. Hence, there is some arrow (C,A)∈arr such that (C,A)∈a. By Definition 83, we obtain (C,A)∈in(ALab).
- We show that if ALab((A,B))=undec then not for each (C,A)∈arr it holds that ALab((C,A))=out, and there does not exist a (C,A)∈arr such that ALab((C,A))=in.
  Let (A,B)∈undec(ALab). We provide a proof by contradiction.
  First assume for each (C,A)∈arr it holds that ALab((C,A))=out. By Definition 83, for each (C,A)∈arr it holds that (C,A)∈a+. Hence, each attacker of (A,B) is attacked. By Definition 5, we obtain that (A,B)∈F(a). By the fundamental lemma and by definition of complete extension semantics, we obtain that (A,B)∈a. Therefore, by definition of a2ALab, we obtain ALab((A,B))=in, contradiction to the assumption (A,B)∈undec(ALab). Hence, we obtain that not for each (C,A)∈arr it holds that ALab((C,A))=out.
  Now assume that there exists (C,A)∈arr such that ALab((C,A))=in. By Definition 83, (C,A)∈a. Since (C,A) attacks (A,B) it furthermore holds that (A,B)∈a+. Hence, ALab((A,B))=out, contradiction to our initial assumption. Hence we obtain that there does not exist a (C,A)∈arr such that ALab((C,A))=in.
(2) Let ALab2a(ALab)=a. Let ALab be a complete labelling. We show that ALab2a(ALab)=a is a complete extension.
- We show that a is conflict-free. Let (A,B),(C,D)∈a. By Definition 84, (A,B),(C,D)∈in(ALab). Towards a contradiction, assume (A,B) attacks (C,D), that is, B=C. By definition of a complete labelling, we obtain ALab((A,B))=out. Hence we obtain a contradiction.
- We show that a=F(a).
  First, let (A,B)∈a. By Definition 84, ALab((A,B))=in. By definition of a complete labelling, for all (C,A)∈arr it holds that ALab((C,A))=out. Hence, there exists (D,C)∈arr such that ALab((D,C))=in. Hence, (A,B) is defended by a against each attack. We obtain (A,B)∈F(a).
  For the other direction, let (A,B)∈F(a). Hence, each attacker of (A,B) is attacked by a: for all (C,A)∈arr it holds that (C,A)∈a+. Towards a contradiction, we assume ALab((A,B))≠in. Then ALab((A,B))∈{out,undec}. We proceed by case distinction.
  First assume, ALab((A,B))=out. By Definition 7, there exists a (C,A)∈arr such that ALab((C,A))=in. By Definition 84, (C,A)∈a. We obtain a contradiction since a is conflict-free.
  Now assume, ALab((A,B))=undec. By Definition 7, there is some (C,A)∈arr such that ALab((C,A))≠out, and there does not exist a (C,A)∈arr such that ALab((C,A))=in. By the first condition, there is some (C,A)∈arr such that ALab((C,A))∈{in,undec}. By the second condition, ALab((C,A))≠in. Hence, there is some (C,A)∈arr such that ALab((C,A))=undec. Since (C,A)∈a+ (by our initial assumption), there is some (D,C)∈a. By Definition 84, ALab((D,C))=in. By Definition 7, each arrow which is attacked by (D,C) is labelled out. Hence ALab((C,A))=out. Contradiction to the assumption that ALab((C,A))=undec.
  We obtain ALab((A,B))=in and therefore, (A,B)∈a, as desired.

□

Theorem 86.

Let (N,arr) be an argumentation framework and let a⊆arr. Then

(1) if a is a grounded extension then a2ALab(a) is a grounded labelling;
(2) if a is a preferred extension then a2ALab(a) is a preferred labelling;
(3) if a is a semi-stable extension then a2ALab(a) is a semi-stable labelling;
(4) if a is a stable extension then a2ALab(a) is a stable labelling.

Proof.

Let a2ALab(a)=ALab.

(1) Let a be the grounded extension. By Theorem 85, it holds that ALab is a complete labelling. We show that in(ALab) is ⊆-minimal among all complete arrow labellings. Towards a contradiction, assume there is a complete labelling AbLab′ such that in(ALab′)⊊in(ALab). By Theorem 85, a′=in(ALab′) is a complete extension. By Definition 83, in(ALab)=a, hence there is a complete extension a′ such that a′⊊a, contradiction to ⊆-minimality of a. We obtain that ALab is the grounded labelling.
(2) Let a be a preferred extension. By Theorem 85, it holds that ALab is a complete labelling. We show that in(ALab) is ⊆-maximal among all complete arrow labellings. Towards a contradiction, assume there is a complete labelling AbLab′ such that in(ALab)⊊in(ALab′). By Theorem 85, a′=in(ALab′) is a complete extension, contradiction to ⊆-maximality of a. We obtain that ALab is a preferred labelling.
(3) Let a be a semi-stable extension. By Theorem 85, it holds that ALab is a complete labelling. Moreover, by definition of semi-stable semantics, a∪a+ is ⊆-maximal among all complete extensions. We show that undec(ALab) is ⊆-minimal among all complete labellings.
Towards a contradiction, suppose there is a complete labelling ALab′ such that undec(ALab′)⊊undec(ALab). By Theorem 85, a′=in(ALab′) is a complete extension. By Definition 83, undec(ALab′)=arr∖(a′∪(a′)+). Hence, arr∖(a′∪(a′)+)⊊arr∖(a∪a+), therefore, a′∪(a′)+⊋a∪a+, that is, we have found a complete extension a′ showing that a is not semi-stable, contradiction to our initial assumption. We obtain that ALab is a semi-stable labelling.
(4) Let a be a stable extension. By Theorem 85, it holds that ALab is a complete labelling. Moreover, by definition of stable semantics, a∪a+=arr. Hence, by Definition 83, undec(ALab)=∅. We obtain that ALab is a stable labelling.

□

Theorem 87.

Let (N,arr) be an argumentation framework and let ALab be an arrow labelling. Then

(1) if ALab is a grounded labelling then ALab2a(ALab) is a grounded extension;
(2) if ALab is a preferred labelling then ALab2a(ALab) is a preferred extension;
(3) if ALab is a semi-stable labelling then ALab2a(ALab) is a semi-stable extension;
(4) if ALab is a stable labelling then ALab2a(ALab) is a stable extension.

Proof.

Let ALab2a(ALab)=a.

(1) Let ALab be the grounded labelling. By Theorem 85, it holds that a is a complete extension. We show that a is ⊆-minimal among all complete extensions. Towards a contradiction, assume there is a complete extension a′ such that a′⊊a. By Theorem 85, a2ALab(a′) is a complete arrow labelling. By Definition 83, a=in(ALab) and a′=in(a2ALab(a′)). Therefore, in(a2ALab(a′))⊊in(ALab), contradiction to the assumption that ALab is the grounded labelling. We obtain that a is the grounded extension.
(2) Let ALab be a preferred labelling. By Theorem 85, it holds that a is a complete extension. We show that a is ⊆-maximal among all complete extensions. Towards a contradiction, assume there is a complete extension a′ such that a′⊋a. By Theorem 85, a2ALab(a′) is a complete arrow labelling. By Definition 83, a=in(ALab) and a′=in(a2ALab(a′)). Therefore, in(a2ALab(a′))⊋in(ALab), contradiction to the assumption that ALab is ⊆-maximal. We obtain that a is a preferred extension.
(3) Let ALab be a semi-stable labelling. By Theorem 85, it holds that a is a complete extension. Moreover, by definition of semi-stable semantics, undec(ALab) is ⊆-minimal among all complete labellings. We show that a∪a+ is ⊆-maximal among all complete extensions.
Towards a contradiction, suppose there is a complete extension a′ such that a′∪(a′)+⊋a∪a+. By Theorem 85, ALab′=a2ALab(a′) is a complete labelling. By Definition 83, undec(ALab′)=arr∖(a′∪(a′)+). Hence, arr∖(a′∪(a′)+)⊊arr∖(a∪a+), and therefore, undec(ALab′)⊊undec(ALab). Consequently, ALab cannot be a semi-stable labelling; hence, we conclude that a is a semi-stable extension.
(4) Let ALab be a stable labelling. By Theorem 85, it holds that a is a complete extension. By definition of stable labellings, undec(ALab)=∅. Hence, each attack is either labelled in or labelled out. By Definition 84, in(ALab)=a. By Definition 7, if an attack (A,B) is labelled out then there is (C,A)∈arr such that ALab((C,A))=in. Hence, a+=arr∖a. We obtain that a is a stable labelling.

□

Lemma 88.

Let AF=(N,arr) be an argumentation framework.

(1) For a complete arrow labelling ALab it holds that a2ALab(ALab2a(ALab))=ALab.
(2) For a complete arrow extension a it holds that ALab2a(a2ALab(a))=a.

Proof.

(1) Let ALab2a(ALab)=a. We prove the following three properties, for an arbitrary arrow (A,B)∈arr.
- If AbLab((A,B))=in then a2ALab(a)((A,B))=in.
  Suppose AbLab((A,B))=in. By Definition 84, (A,B)∈a. By Definition 83, we obtain a2ALab(a)((A,B))=in.
- If ALab((A,B))=out then a2ALab(a)((A,B))=out.
  Suppose ALab((A,B))=out. Then by Definition of a complete arrow labelling, it follows that there exists a (C,A)∈arr such that ALab((C,A))=in. By Definition 84 (C,A)∈a. By Definition 83, we obtain a2ALab(a)((C,A))=in. We proceed by case distinction.
  First assume a2ALab(a)((A,B))=in. Then a2ALab(a)((C,A))=out, by definition of a complete arrow labelling. Hence we obtain a contradiction.
  Next assume a2ALab(a)((A,B))=undec. By definition of a complete arrow labelling, there is some (C,A)∈arr such that a2ALab(a)((C,A))≠out, and there does not exist a (C,A)∈arr such that a2ALab(a)((C,A))=in. The latter condition contradicts our assumption.
  We obtain a2ALab(a)((A,B))=out, as desired.
- If ALab((A,B))=undec then a2ALab(a)((A,B))=undec.
  Suppose AbLab((A,B))=undec. By definition of a complete arrow labelling, there is some (C,A)∈arr such that ALab((C,A))≠out, and there does not exist a (C,A)∈arr such that ALab((C,A))=in.
  To show that a2ALab(a)((A,B))=undec we provide a proof by contradiction. Towards a contradiction, assume a2ALab(a)((A,B))≠undec. Then either a2ALab(a)((A,B))=in or a2ALab(a)((A,B))=out. We proceed by case distinction.
  First assume a2ALab(a)((A,B))=in. By Definition 83, (A,B)∈a. By Definition 84, we obtain ALab((A,B))=in. This is a contradiction to ALab((A,B))=undec.
  Next assume a2ALab(a)((A,B))=out. By Definition 83, (A,B)∈a+. By definition of a complete arrow extension, there is some (C,A)∈arr with (C,A)∈a. By Definition 84, ALab((C,A))=in. This is a contradiction to the assumption that there does not exist a (C,A)∈arr such that ALab((C,A))=in.
  Hence we can conclude a2ALab(a)((A,B))=undec.
(2) Consider a complete extension a. By Definition 83, in(a2ALab(a))=a. By Definition 84, we obtain ALab2a(a2ALab(a))=in(a2ALab(a))=a.

□

Theorem 89.

When restricted to complete node labellings and complete arrow labellings, the functions ALab2a and a2ALab become bijections and each other’s inverses.

Proof.

This follows directly from Lemma 88. □

Appendix I.

Appendix I.Equivalence of node extensions and arrow extensions for argumentation frameworks

We define the functions

Args2a=ALab2a∘NLab2ALab∘Args2NLab

and

a2Args=Args2NLab∘ALab2NLab∘ALab2a.

Theorem 90.

Let AF=(N,arr) be an argumentation framework and let M⊆N and a⊆arr. It holds that:

(1) If M is complete node extension then Args2a(M) is a complete arrow extension.
If a is a complete arrow extension, then a2Args(a) is a complete node extension.
(2) When restricted to complete node labellings and complete arrow labellings, the functions ALab2NLab and NLab2ALab become bijections and each other’s inverses.
(3) If M is a grounded node extension, then Args2a(M) is a grounded arrow extension.
If a is a grounded arrow extension, then a2Args(a) is a grounded node extension.
(4) If M is a preferred node extension, then Args2a(M) is a preferred arrow extension.
If a is a preferred arrow extension, then a2Args(a) is a preferred node extension.
(5) If M is a stable node extension, then Args2a(M) is a stable arrow extension.
If a is a stable arrow extension, then a2Args(a) is a stable node extension.

Proof.

(1) First, let M is complete node extension. By results from [14] and as summarised in Table 2, Args2NLab(M) is a complete node labelling. By Theorem 8, NLab2ALab(Args2NLab(M)) is a complete arrow labelling. Finally, by Theorem 87, ALab2a(NLab2ALab(Args2NLab(M)))=Args2a(M) is a complete arrow extension.
Now, let a a complete arrow extension. By Theorem 86, a2ALab(a) is a complete arrow labelling. By Theorem 8, ALab2NLab(a2ALab(a)) is a complete node labelling. Finally, by results from [14] and as summarised in Table 2, NLab2Args(ALab2NLab(a2ALab(a)))=a2Args(a) is a complete node extensions.
(2) By results from [14], Theorem 8, and Theorem 89.
(3) Analogous to point 1.
(4) Analogous to point 1.
(5) Analogous to point 1.

□

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

Example 91.

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

The AF has three complete node extensions M1=∅, M2={A}, and M3={D,F} that are one-to-one related to the complete arrow extensions a1=∅, a2={(A,B),(A,D)}, and a3={(D,A),(D,E)} via the functions Args2a and a2Args.

Let us see the function Args2a=ALab2a∘NLab2ALab∘Args2NLab at work. Let us compute Args2a(M2) in three steps:

Args2NLab(M2)=({A},{B,D},{C,E,F})NLab2ALab(Args2NLab(M2))=({(A,B),(A,D)},{(D,A),(D,E)},{(C,B),(C,C),NLab2ALab(Args2NLab(M2))=(E,E),(E,F)})ALab2a(NLab2ALab(Args2NLab(M2)))={(A,B),(A,D)}

Hence, we obtain Args2a(M2)=a2.

The set M2 is the only semi-stable node extension of AF. However, the set a2 is not a semi-stable arrow extension since a3∪a3+⊃a2∪a2+. Indeed, a3 is the unique semi-stable arrow extension of AF. On the other hand, M3=a2Args(a3) is not a semi-stable node extension.

Appendix J.

Appendix J.Equivalence of arrow extensions and arrow labellings for SETAFs

Definition 92.

Let (N,arr) be a SETAF and let a⊆arr. We define the function a2ALab(a)=(a,a+,arr∖(a∪a+)).

Definition 93.

Let (N,arr) be a SETAF and let ALab be an arrow labelling. We define the function ALab2a(ALab)=in(ALab).

Theorem 94.

Let (N,arr) be a SETAF.

(1) If a⊆arr is a complete extension then a2ALab(a) is a complete labelling.
(2) If ALab is a complete labelling then ALab2a(ALab) is a complete extension.

Proof.

(1) Let a be a complete extension and let a2ALab(a)=ALab. We show that a2ALab(a)=ALab is a complete labelling:
- We show that if ALab((M,A))=in then for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out. Let (M,A)∈in(ALab) and consider an arrow (M′,B)∈arr with B∈M. By Definition 93, M∈a. Since a is complete, the arrow (M,A) is defended by a. Hence, (M′,B)∈a+. By Definition 93, we obtain that (M′,B)∈out(ALab).
- We show that if ALab((M,A))=out then there exists an (M′,B)∈arr such that B∈M and ALab((M′,B))=in. Let (Mh,A)∈out(ALab). By Definition 93, (M,A)∈a+. Hence, there is some arrow (M′,B)∈a such that B∈M. By Definition 92, we obtain (M′,B)∈in(ALab).
- We show that if ALab((M,A))=undec then not for each (M′,B)∈arr such that B∈M it holds that ALab((M′,B))=out and there does not exist an (M′,B)∈arr such that B∈M and ALab((M′,B))=in.
  Let (M,A)∈undec(ALab). We provide a proof by contradiction.
  First assume for each (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out. By Definition 92, for each (M′,B)∈arr with B∈M it holds that (M′,B)∈a+. By Definition 18, we obtain that (M,A)∈F(a). By the fundamental lemma and by definition of complete semantics, we obtain that (M,A)∈a. Therefore, by definition of a2ALab, we obtain ALab((M,A))=in, contradiction to the assumption (M,A)∈undec(ALab).
  Now assume that there exists (M′,B)∈arr with B∈M such that ALab((M′,B))=in. By Definition 92, (M′,B)∈a. Hence (M,A)∈a+. Therefore we obtain ALab((M,A))=out, contradiction to our initial assumption. This concludes the proof of the statement.
(2) Let ALab be a complete labelling and let ALab2a(ALab)=a. We show that ALab2a(ALab)=a is a complete extension.
- We show that a is conflict-free. Let (M,A),(M′,B)∈a. By Definition 93, (M,A),(C,D)∈in(ALab). Towards a contradiction, assume (M,A) attacks (M′,B), that is, B∈M. By definition of a complete labelling, we obtain ALab((M,A))=out. Hence we obtain a contradiction.
- We show that a=F(a).
  First, let (M,A)∈a. By Definition 93, ALab((M,A))=in. By definition of a complete labelling, for all (M′,B)∈arr with B∈M it holds that ALab((M′,B))=out. Hence, there exists (M″,C)∈arr with C∈M′ such that ALab((M″,C))=in. Hence, (M,A) is defended by a against each attack. We obtain (M,A)∈F(a).
  For the other direction, let (M,A)∈F(a). Each attacker of (M,A) is attacked by a: for all (M′,B)∈arr with B∈M it holds that (M′,B)∈a+. Towards a contradiction, we assume ALab((M,A))≠in. Then ALab((M,A))∈{out,undec}. We proceed by case distinction.
  First assume, ALab((M,A))=out. By Definition 17, there exists a (M′,B)∈arr with B∈M such that ALab((M′,B))=in. By Definition 93, (M′,B)∈a. We obtain a contradiction since a is conflict-free.
  Now assume, ALab((M,A))=undec. By Definition 17, there is some (M′,B)∈arr with B∈M such that ALab((M′,B))≠out, and there does not exist a (M′,B)∈arr with B∈M such that ALab((M′,B))=in. By the first condition, there is some (M′,B)∈arr such that ALab((M′,B))∈{in,undec}. By the second condition, ALab((M′,B))≠in. Hence, there is some (M′,B)∈arr such that ALab((M′,B))=undec. Since (M′,B)∈a+ (by our initial assumption), there is some (M″,C)∈a with C∈M. By Definition 93, ALab((M″,C))=in. By Definition 17, each arrow which is attacked by (M″,C) is labelled out. Hence ALab((M′,B))=out. Contradiction to the assumption that ALab((M′,B))=undec.
  We obtain ALab((M,A))=in and therefore, (M,A)∈a, as desired.

□

Theorem 95.

Let (N,arr) be a SETAF and let a⊆arr. Then

(1) if a is a grounded extension then a2ALab(a) is a grounded labelling;
(2) if a is a preferred extension then a2ALab(a) is a preferred labelling;
(3) if a is a semi-stable extension then a2ALab(a) is a semi-stable labelling;
(4) if a is a stable extension then a2ALab(a) is a stable labelling.

Proof.

Let a2ALab(a)=ALab.

(1) Let a be the grounded extension. By Theorem 94, it holds that ALab is a complete labelling. We show that in(ALab) is ⊆-minimal among all complete arrow labellings. Towards a contradiction, assume there is a complete labelling AbLab′ such that in(ALab′)⊊in(ALab). By Theorem 94, a′=in(ALab′) is a complete extension. By Definition 92, in(ALab)=a, hence there is a complete extension a′ such that a′⊊a, contradiction to ⊆-minimality of a. We obtain that ALab is the grounded labelling.
(2) Let a be a preferred extension. By Theorem 94, it holds that ALab is a complete labelling. We show that in(ALab) is ⊆-maximal among all complete arrow labellings. Towards a contradiction, assume there is a complete labelling AbLab′ such that in(ALab)⊊in(ALab′). By Theorem 94, a′=in(ALab′) is a complete extension, contradiction to ⊆-maximality of a. We obtain that ALab is a preferred labelling.
(3) Let a be a semi-stable extension. By Theorem 94, it holds that ALab is a complete labelling. Moreover, by definition of semi-stable semantics, a∪a+ is ⊆-maximal among all complete extensions. We show that undec(ALab) is ⊆-minimal among all complete labellings.
Towards a contradiction, suppose there is a complete labelling ALab′ such that undec(ALab′)⊊undec(ALab). By Theorem 94, a′=in(ALab′) is a complete extension. By Definition 92, undec(ALab′)=arr∖(a′∪(a′)+). Hence, arr∖(a′∪(a′)+)⊊arr∖(a∪a+), therefore, a′∪(a′)+⊋a∪a+, that is, we have found a complete extension a′ showing that a is not semi-stable, contradiction to our initial assumption. We obtain that ALab is a semi-stable labelling.
(4) Let a be a stable extension. By Theorem 94, it holds that ALab is a complete labelling. Moreover, by definition of stable semantics, a∪a+=arr. Hence, by Definition 92, undec(ALab)=∅. We obtain that ALab is a stable labelling.

□

Theorem 96.

Let (N,arr) be a SETAF and let ALab be an arrow labelling. Then

(1) if ALab is a grounded labelling then ALab2a(ALab) is a grounded extension;
(2) if ALab is a preferred labelling then ALab2a(ALab) is a preferred extension;
(3) if ALab is a semi-stable labelling then ALab2a(ALab) is a semi-stable extension;
(4) if ALab is a stable labelling then ALab2a(ALab) is a stable extension.

Proof.

Let ALab2a(ALab)=a.

(1) Let ALab be the grounded labelling. By Theorem 94, it holds that a is a complete extension. We show that a is ⊆-minimal among all complete extensions. Towards a contradiction, assume there is a complete extension a′ such that a′⊊a. By Theorem 95, Theorem 94, a2ALab(a′) is a complete arrow labelling. By Definition 92, a=in(ALab) and a′=in(a2ALab(a′)). Therefore, in(a2ALab(a′))⊊in(ALab), contradiction to the assumption that ALab is the grounded labelling. We obtain that a is grounded.
(2) Let ALab be a preferred labelling. By Theorem 94, it holds that a is a complete extension. We show that a is ⊆-maximal among all complete extensions. Towards a contradiction, assume there is a complete extension a′ such that a′⊋a. By Theorem 95, Theorem 94, a2ALab(a′) is a complete arrow labelling. By Definition 92, a=in(ALab) and a′=in(a2ALab(a′)). Therefore, in(a2ALab(a′))⊋in(ALab), contradiction to the assumption that ALab is ⊆-maximal. We obtain that a is preferred.
(3) Let ALab be a semi-stable labelling. By Theorem 94, it holds that ALab is a complete extension. Moreover, by definition of semi-stable semantics, undec(ALab) is ⊆-minimal among all complete labellings. We show that a∪a+ is ⊆-maximal among all complete extensions.
Towards a contradiction, suppose there is a complete extension a′ such that a′∪(a′)+⊋a∪a+. By Theorem 95, Theorem 94, ALab′=a2ALab(a′) is a complete labelling. By Definition 92, undec(ALab′)=arr∖(a′∪(a′)+). Hence, arr∖(a′∪(a′)+)⊊arr∖(a∪a+), and therefore, undec(ALab′)⊊undec(ALab). That is, ALab is not a semi-stable labelling, contradiction to our initial assumption. We conclude that a is semi-stable.
(4) Let ALab be a stable labelling. By Theorem 94, it holds that a is a complete extension. By definition of stable labellings, undec(ALab)=∅. Hence, each attack is either labelled ∈ or labelled out. By Definition 93, in(ALab)=a. By Definition 17, if an attack (M,A) is labelled out then there is (M′,B)∈arr such that ALab((M′,B))=in. Hence, a+=arr∖a. Consequently, a∪a+=arr. We obtain that a is stable.

□

Lemma 97.

Let (N,arr) be a SETAF.

(1) For a complete arrow labelling ALab it holds that a2ALab(ALab2a(ALab))=ALab.
(2) For a complete arrow extension a it holds that ALab2a(a2ALab(a))=a.

Proof.

(1) Let ALab2a(ALab)=a. We prove the following three properties, for an arbitrary arrow (M,A)∈arr.
- If AbLab((M,A))=in then a2ALab(a)((M,A))=in.
  Suppose AbLab((M,A))=in. By Definition 93, (M,A)∈a. By Definition 92, we obtain a2ALab(a)((M,A))=in.
- If ALab((M,A))=out then a2ALab(a)((M,A))=out.
  Suppose ALab((M,A))=out. Then by Definition of a complete arrow labelling, it follows that there exists a (M′,B)∈arr with B∈M such that ALab((M′,B))=in. By Definition 93 (M′,B)∈a. By Definition 92, we obtain a2ALab(a)((M′,B))=in. We proceed by case distinction.
  First assume a2ALab(a)((M,A))=in. Then a2ALab(a)((M′,B))=out, by definition of a complete arrow labelling. Hence we obtain a contradiction.
  Next assume a2ALab(a)((M,A))=undec. By definition of a complete arrow labelling, there is some (M′,B)∈arr with B∈M such that a2ALab(a)((M′,B))≠out, and there does not exist a (M′,B)∈arr with B∈M such that a2ALab(a)((Mh′,B))=in. The latter condition contradicts our assumption.
  We obtain a2ALab(a)((M,A))=out, as desired.
- If ALab((M,A))=undec then a2ALab(a)((M,A))=undec.
  Suppose AbLab((M,A))=undec. By definition of a complete arrow labelling, there is some (M′,B)∈arr with B∈M such that a2ALab(a)((M′,B))≠out, and there does not exist a (M′,B)∈arr with B∈M such that a2ALab(a)((Mh′,B))=in.
  To show that a2ALab(a)((M,A))=undec we provide a proof by contradiction. Towards a contradiction, assume a2ALab(a)((M,A))≠undec. Then either a2ALab(a)((M,A))=in or a2ALab(a)((M,A))=out. We proceed by case distinction.
  First assume a2ALab(a)((M,A))=in. By Definition 92, (M,A)∈a. By Definition 93, we obtain ALab((M,A))=in. This is a contradiction to ALab((M,A))=undec.
  Next assume a2ALab(a)((M,A))=out. By Definition 92, (M,A)∈a+. By definition of a complete arrow extension, there is some (M′,B)∈arr with B∈M and (M′,B)∈a. By Definition 93, ALab((M′,B))=in. This is a contradiction to the assumption that there does not exist a (M′,B)∈arr with B∈M such that ALab(M′,B))=in.
  Hence we can conclude a2ALab(a)((M,A))=undec.
(2) Consider a complete arrow extension a. By Definition 92, in(a2ALab(a))=a. By Definition 93, ALab2a(a2ALab(a))=in(a2ALab(a)). Therefore, we obtain ALab2a(a2ALab(a))=a.

□

Theorem 98.

When restricted to complete node labellings and complete arrow labellings, the functions ALab2a and a2ALab become bijections and each other’s inverses.

Proof.

This follows directly from Lemma 97. □

Appendix K.

Appendix K.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

Args2a=ALab2a∘NLab2ALab∘Args2NLab

and

a2Args=Args2NLab∘ALab2NLab∘ALab2a.

Theorem 99.

Let (N,arr) be a SETAF and let M⊆N and a⊆arr. It holds that:

(1) If M is complete node extension then Args2a(M) is a complete arrow extension.
If a is a complete arrow extension, then a2Args(a) is a complete node extension.
(2) When restricted to complete node labellings and complete arrow labellings, the functions Args2a and a2Args become bijections and each other’s inverses.
(3) If M is a grounded node extension, then Args2a(M) is a grounded arrow extension.
If a is a grounded arrow extension, then a2Args(a) is a grounded node extension.
(4) If M is a preferred node extension, then Args2a(M) is a preferred arrow extension.
If a is a preferred arrow extension, then a2Args(a) is a preferred node extension.
(5) If M is a stable node extension, then Args2a(M) is a stable arrow extension.
If a is a stable arrow extension, then a2Args(a) is a stable node extension.

Proof.

(1) First, let M is complete node extension. By [35, Theorem 5.10, Theorem 5.11] (and as summarised in Table 8), Args2NLab(M) is a complete node labelling. By Theorem 21, NLab2ALab(Args2NLab(M)) is a complete arrow labelling.
Finally, by Theorem 96, ALab2a(NLab2ALab(Args2NLab(M)))=Args2a(M) is a complete arrow extension.
Now, let a a complete arrow extension. By Theorem 95, a2ALab(a) is a complete arrow labelling. By Theorem 21, ALab2NLab(a2ALab(a)) is a complete node labelling. Finally, by [35, Theorem 5.10, Theorem 5.11], NLab2Args(ALab2NLab(a2ALab(a)))=a2Args(a) is a complete node extension.
(2) By [35, Theorem 5.10, Theorem 5.11], Theorem 21, and Theorem 98.
(3) Analogous to point 1.
(4) Analogous to point 1.
(5) Analogous to point 1.

□

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

Appendix L.

Appendix L.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.

Theorem 100.

Let SF=(N,arr) be a SETAF and AFSF=(N,arr) be its inside-out framework.

(1) If ALab is a complete arrow labelling of SF, then ALab is a complete node labelling of AFSF.
If NLab is a complete node labelling of AFSF, then NLab is a complete arrow labelling of SF.
(2) If ALab is a preferred (resp. grounded or stable) arrow labelling of SF, then ALab is a preferred (resp. grounded or stable) node labelling of AFSF.
If NLab is a preferred (resp. grounded, stable or semi-stable) node labelling of AFSF, then NLab is a preferred (resp. grounded, stable or semi-stable) arrow labelling of SF.

Proof.

(1) This follows directly from the definition of a complete node labelling (Definition 17, first three bullet points), the definition of a complete arrow labelling (Definition 20, first three bullet points) and the definition of an inside out argumentation framework (Definition 22).
(2) This follows directly from point 1, together with the definition of a preferred (resp. grounded, stable or semi-stable) node labelling (Definition 17) and the definition of a preferred (resp. grounded, stable or semi-stable) arrow labelling (Definition 20).

□

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].

Appendix M.

Appendix M.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.

Lemma 101.

Let D=(L,R,A,a‾) be an ABAF.

(1) The notion of a set of assumptions Asms⊆A attacking an assumption α∈A is equivalent when using arguments or derivations in Definition 30.
(2) The notion of a set of assumptions Asms1⊆A attacking a set of assumption Asms2⊆A is equivalent when using arguments or derivations in Definition 30.
(3) The set Asms+ of a set of assumptions Asms⊆A is equivalent when using arguments or derivations in Definition 30.
(4) The notion of a set of assumptions Asms⊆A being conflict-free is equivalent when using arguments or derivations in Definition 30.
(5) The notion of a set of assumptions Asms⊆A defending an assumption α∈A is equivalent when using arguments or derivations in Definition 30.
(6) The set F(Asms) of a set of assumption Asms⊆A is equivalent when using arguments or derivations in Definition 30.

Proof.

We prove all items.

(1) There exists an ABA-argument (Asms′,α¯) iff there exists at least one ABA-derivation for α¯ supported by Asms′. Thus, Asms attacks α no matter whether the notion of argument or derivation is used in the definition.
(2) Asms1⊆A attacks Asms2⊆A iff Asms1 attacks some α∈Asms2. Thus, the claim follows by the first item.
(3) For a set of assumptions Asms⊆A, Asms+={α∈A|Asms attacks α}. Thus, the claim follows by the first item.
(4) By the third item a set of assumptions Asms⊆A is conflict-free no matter whether the notion of argument or derivation is used in the definition.
(5) Asms⊆A defends α∈A iff each Asms′ attacking α is attacked by Asms. Thus, the claim follows by the first three items.
(6) For a set of assumptions Asms⊆A, F(Asms)={α∈A|α is defended by Asms}. Thus, the claim follows by the fourth item.

□

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.

Theorem 102.

Let D=(L,R,A,a‾) be an ABAF.

(1) The notion of a set of assumptions Asms⊆A being an admissible assumption set is equivalent when using arguments or derivations in Definition 31.
(2) The notion of a set of assumptions Asms⊆A being a complete (resp. grounded, preferred, semi-stable, stable) assumption extension is equivalent when using arguments or derivations in Definition 31.

Proof.

We prove both statements

(1) admissible: By Lemma 101.
(2)
- complete: By Lemma 101.
- grounded: By the equivalence of complete assumption extensions.
- preferred: By the equivalence of complete assumption extensions.
- semi-stable: By the equivalence of complete assumption extensions and because by Lemma 101 Asms+ is equivalent independent of the underlying notion.
- stable: Same as semi-stable.

□

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.

Theorem 103.

Let D=(L,R,A,a‾) be an ABAF and Asms⊆A. The following two statements are equivalent:

(1) The set Asms is a maximal admissible assumption set of D
(2) The set Asms is a maximal complete assumption extension of D

Proof.

(From 1 to 2) Let Asms be a maximal admissible assumption set. From [10, Corollary 5.8] it follows that Asms is a complete assumption extension. Suppose Asms is not maximal complete. Then there exists a complete assumption extension Asms′ with Asms⊊Asms′. However, since by definition, every complete assumption extension is also an admissible assumption set, it holds that Asms′ is an admissible assumption set. But this would mean that Asms is not a maximal admissible assumption set; contradiction.

(From 2 to 1) Let Asms be a maximal complete assumption extension. Then by definition, Asms is also an admissible assumption set. We now need to prove that it is also a maximal admissible assumption set. Suppose this is not the case, then there exists a maximal admissible assumption set Asms′ with Asms⊊Asms′. It follows from [10, Corollary 5.8] that Asms′ is also a complete assumption extension. But this would mean that Asms is not a maximal complete assumption extension; contradiction. □

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].

Theorem 104.

Let D=(L,R,A,a‾) be an ABAF and Asms⊆A. The following two statements are equivalent:

(1) Asms is a conflict-free assumption set that attacks every assumption in A∖Asms
(2) Asms is a complete assumption extension with Asms∪Asms+=A

Proof.

(From 1 to 2) Let Asms is a conflict-free assumption set attacking every assumption in A∖Asms. Thus, if α∉Asms, then α∈Asms+. Since Asms is conflict-free, if α∈Asms, then α∉Asms+. It follows that if α∈A, then α∈Asms or α∈Asms+, i.e. A=Asms∪Asms+. Clearly, if Asms′ attacks Asms, then Asms counter-attacks Asms′, so Asms is admissible. Since no superset of Asms is conflict-free, it even be complete.

(From 2 to 1) Let Asms is a complete assumption extension with Asms∪Asms+=A. Thus, if α∈A, then α∈Asms or α∈Asms+. It follows that for every assumption α∈A∖Asms, it holds that α∈Asms+, so α is attacked by Asms. Since Asms is complete, it is conflict-free. □

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

Theorem 32.

Let D=(L,R,A,a‾) be an ABAF.

(1) The set Asms⊆A is an admissible assumption set according to Definitions 26-31 iff Asms is an admissible assumption set according to the definitions in [10, 22].
(2) The set Asms⊆A is a complete (resp. grounded, preferred, semi-stable or stable) assumption extension according to Definitions 26-31 iff Asms is a complete (resp. grounded, preferred, semi-stable or stable) assumption extension according to the definitions in [10, 17, 22]

Proof.

We prove both items.

(1) By Theorem 102 and because the notion of admissible assumption set used here is a simple reformulation of the one in [10,22]: In [22], a set of assumption Asms is defined as an admissible assumption set iff it does not attack itself and it attacks every set of assumptions Asms′ that attacks Asms. However, by definition, Asms attacks every set of assumptions Asms′ that attacks Asms iff Asms⊆F(Asms).
(2) By Theorems 102, 103, and 104 and because by the same reasoning as for the first item, the notion of complete assumption extension is a reformulation of the definitions in [10,22] in terms of the function F.

□

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].

Definition 105.

Given an ABAF D=(L,R,A,a‾), we say that a derivation tree for c1 supported by Asms1 derivation-attacks a derivation tree for c2 supported by Asms2 iff c1=γ¯ for some γ∈Asms2.

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

Definition 106.

Given an ABAF D=(L,R,A,a‾), the associated derivation AF AFderD is defined as (Nder,arrder) with Nder being the set of derivation trees, and arrder being the derivation-attack relation among derivation trees.

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

Lemma 107.

Let D=(L,R,A,a‾) be an ABAF, AFD the associated AF, and AFderD the associated derivation AF. The following are equivalent:

(1) There exists an ABA-argument (Asms,c) in AFD.
(2) There exists a derivation tree for c supported by Asms in AFderD.

Proof.

It follows directly from Definitions 26 and 27 that an ABA-argument (Asms,c) represents the set of all derivation trees supported by the set Asms of assumptions and having conclusion c. □

Lemma 108.

Let D=(L,R,A,a‾) be an ABAF, AFD=(N,arr) the associated AF, and AFderD the associated derivation AF. The following are equivalent:

(1) The ABA-argument (Asms1,c1) attacks the ABA-argument (Asms2,c2) in AFD.
(2) A derivation tree for c1 supported by Asms1 derivation-attacks a derivation tree for c2 supported by Asms2 in AFderD.
(3) All ABA-derivations for c1 supported by Asms1 derivation-attack all derivation trees for c2 supported by Asms2 in AFderD.

Proof.

(1 to 2) Assume that the ABA-argument (Asms1,c1) attacks the ABA-argument (Asms2,c2) in AFD. By Lemma 107 there exists a derivation tree for c1 supported by Asms1 and a derivation tree for c2 supported by Asms2 in AFderD. Since (Asms1,c1) attacks (Asms2,c2), by Definition 27 c1=γ¯ for some γ∈Asms2. Thus, by Definition 105 the derivation tree for c1 supported by Asms1 derivation-attacks the derivation tree for c2 supported by Asms2.

(2 to 1) Analogously.

(2 to 3) Assume that a derivation tree for c1 supported by Asms1 derivation-attacks a derivation tree for c2 supported by Asms2. By Definition 105, c1=γ¯ for some γ∈Asms2. Since this holds for all derivation trees for c1 supported by Asms1 and all derivation tree for c2 supported by Asms2, by Definition 105 all derivation trees for c1 supported by Asms1 derivation-attack all derivation trees for c2 supported by Asms2.

(3 to 2) Analogously. □

Theorem 109.

Let D=(L,R,A,a‾) be an ABAF, AFD=(N,arr) the associated AF, and AFderD=(Nder,arrder) the associated derivation AF. Let M⊆N be a set of ABA-arguments and let Mder⊆Nder be a set of derivations such that all derivations for c supported by Asms are in Mder iff (Asms,c)∈M. Then M is an admissible set of AFD iff Mder is an admissible set of AFderD.

Proof.

(left to right) Assume M is an admissible set of AFD and assume that Mder is not an admissible set of AFderD. Then either Mder is not conflict-free or F(Mder)⊈Mder.

Assume first that Mder is not conflict-free, i.e. there exists some ABA-derivation for c2 supported by Asms2 contained in Mder and contained in Mder+. This means that there exists some derivation tree for c1 supported by Asms1 in Mder which derivation-attacks the derivation tree for c2 supported by Asms2 in Mder. By the definition of M and by Lemma 107, there exist ABA-arguments (Asms1,c1) and (Asms2,c2) in M, and by Lemma 108 (Asms1,c1) attacks (Asms2,c2). Thus, M is not conflict free; contradiction.

Assume now that F(Mder)⊈Mder, i.e. there exists some derivation tree for c3 from Asms3 in Mder which is not defended by Mder. This means that there exists a derivation tree for c4 from Asms4 derivation-attacking the derivation tree for c3 from Asms3 and the derivation tree for c4 from Asms4 is not derivation-attacked by any derivation tree in Mder. By the definition of M and by Lemma 107 there exists an ABA-argument (Asms3,c3) in M and there exists an ABA-argument (Asms4,c4) which by Lemma 108 attacks (Asms3,c3) and (Asms4,c4) is not attacked by any argument in Mder. Thus, (Asms3,c3) is not defended by M and therefore (Asms3,c3)∉F(M); contradiction.

(right to left) Assume that Mder is an admissible set of AFderD and that M is not an admissible set of AFD. Then either M is not conflict-free or F(M)⊈M. Assume first that M is not conflict-free, i.e. there exists some ABA-argument (Asms1,c1) contained in M and contained in M+. Consequently, (Asms1,c1) is attacked by some ABA-argument (Asms2,c2)∈M. By Lemma 108, all derivation trees for c1 supported by Asms1 are derivation-attacked by all derivation trees for c2 supported by Asms2. By definition of Mder, all derivation trees for c1 supported by Asms1 and all derivation trees for c2 supported by Asms2 are contained in Mder. Thus, Mder∩Mder+≠∅ which contradicts the assumption that Mder is an admissible set.

Assume now that F(M)⊈M, i.e. there exists some ABA-argument for (Asms3,c3)∈M which is not defended by M. This means that there exists an ABA-argument (Asms4,c4) attacking (Asms3,c3) which is not attacked by any argument in M. By Lemma 108, all derivation trees for c4 from Asms4 derivation-attack all derivation trees for c3 from Asms3. Furthermore, by the definition of Mder all derivation trees for c4 from Asms4 are not derivation-attacked by any derivation tree in Mder and all derivation trees for c3 from Asms3 are contained in Mder. This means that all derivation trees for c3 from Asms3 are not defended by Mder; contradiction. □

Theorem 110.

Let D=(L,R,A,a‾) be an ABAF, AFD=(N,arr) the associated AF, and AFderD=(Nder,arrder) the associated derivation AF. Let M⊆N be a set of ABA-arguments and let Mder⊆Nder be a set of derivations such that all derivations for c supported by Asms are in Mder iff (Asms,c)∈M. Then M is a complete (resp. grounded, preferred, semi-stable, stable) extension of AFD iff Mder is a complete (resp. grounded, preferred, stable) extension of AFderD.

Proof.

We prove the statement for all listed semantics.

complete: Analogue to the proof of Theorem 109.
grounded: Follows from complete.
preferred: Follows from complete.
semi-stable:
(left to right) Assume M is a semi-stable extension of AFD and assume that Mder is not a semi-stable extension of AFderD, i.e. there exists some Mder′ such that
Mder∪Mder+⊊Mder′∪Mder′+.
Thus, there exists some derivation tree for some c supported by some Asms in Mder′ or in Mder′+ which is not contained in Mder and is not contained in Mder+. By the definition of Mder, the argument (Asms,c) it not contained in M. By Lemma 108 since the derivation tree for c supported by Asms is not in Mder+, there is no ABA-argument in M attacking (Asms,c) and therefore (Asms,c)∉M+. Since M∪M+ is maximal, there exists no M′ such that (Asms,c) is contained in M′ or M′+. Consequently by the definition of Mder and by Lemma 107, there exists no Mder′ such that Mder′ contains an derivation tree for c supported by Asms. Furthermore, by Lemma 108, no derivation tree for c supported by Asms is contained in Mder′+; contradiction.
(right to left) Assume Mder is a semi-stable extension of AFderD and assume that M is not a semi-stable extension of AFD, i.e. there exists some M′ such that
M∪M+⊊M′∪M′+.
Thus, there exists some ABA-argument (Asms,c) in M′ or in M′+ which is not contained in M and is not contained in M+. By the definition of Mder, no derivation tree for c supported by Asms is contained in Mder. However, by Lemma 107 there exists at least one derivation tree for c supported by Asms in Nder. By Lemma 108 since (Asms,c)∉M+ there is no derivation tree in Mder which derivation-attacks the derivation tree for c supported by Asms and therefore the derivation tree for c supported by Asms is not in Mder+. Since Mder∪Mder+ is maximal, there exists no Mder′ such that the derivation tree for c supported by Asms is contained in Mder′ or Mder′+. Consequently by the definition of Mder and by Lemma 107, there exists no M′ such that M′ contains (Asms,c). Furthermore, by Lemma 108, (Asms,c) is not contained in M′+; contradiction.
stable:
(left to right) Assume M is a stable extension of AFD and assume that Mder is not a stable extension of AFderD, i.e. Mder∪Mder+≠Nder. This means there exists some derivation tree for some conclusion c supported by some Asms in Nder which is not contained in Mder and not contained in Mder+. By definition of Mder, the ABA-argument (Asms,c) is not contained in M. Since M is a stable extension, (Asms,c)∈M+. This means that (Asms,c) is attacked by an ABA-argument (Asms1,c1)∈M. By Lemma 107 there is at least one derivation tree for c1 supported by (Asms1) in Nder. By definition of Mder, all derivation trees for c1 supported by (Asms1) are contained in Mder and by Lemma 108 they all attack the derivation of c supported by Asms. Thus, the derivation of c supported by Asms is contained in Mder+; contradiction.
(right to left) Assume Mder is a stable extension of AFderD and assume that M is not a stable extension of AFD, i.e. M∪M+≠Nder. This means that there exists some ABA-argument (Asms,c)∈N which is not contained in M and not contained in M+. By definition of Mder, no derivation tree for c supported by Asms is contained in Mder, but by Lemma 107 there exists at least one derivation for c supported by Asms in AFderD. Since Mder is a stable extension, all derivation trees for c supported by Asms are contained in Mder+. This means that there exist some derivation trees for some c1 supported by some Asms1 which attack all derivation trees for c supported by Asms. By definition of Mder, the argument (Asms1,c1 is contained in Mder and by Lemma 108 (Asms1,c1) attacks (Asms,c). Thus, (Asms,c)∈M+; contradiction.

□

Theorem 35.

Let D=(L,R,A,a‾) be an ABAF, SFD be the associated SETAF, and Asms⊆A. It holds that

(1) Asms is a complete extension of SFD iff Asms is a complete extension of D in the sense of [10, 22];
(2) Asms is a grounded extension of SFD iff Asms is a grounded extension of D in the sense of [10, 22];
(3) Asms is a preferred extension of SFD iff Asms is a preferred extension of D in the sense of [10, 22];
(4) Asms is a semi-stable extension of SFD iff Asms is a semi-stable extension of D in the sense of [15];
(5) Asms is a stable extension of SFD iff Asms is a stable extension of D in the sense of [10, 22].

Proof.

This follows directly from definitions 30, 31, 15, 16 and 33. □

Proposition 36.

Let AF1=(N1,arr1) and AF2=(N2,arr2) be two AFs such that conditions (1) and (2) are met.

(i) If NLab1 is a complete (resp. grounded, preferred or stable) node labelling of AF1, then
NLab2=NLab1∪{(A,in)|A∈N2∖N1,∀(B,A)∈arr2:NLab1(B)=out}∪{(A,out)|A∈N2∖N1,∃(B,A)∈arr2:NLab1(B)=in}∪{(A,undec)|A∈N2∖N1,¬∀(B,A)∈arr2:NLab1(B)=out,¬∃(B,A)∈arr2:NLab1(B)=in}
is a complete (resp. grounded, preferred or stable) node labelling of AF2.
(ii) If NLab2 is a complete (resp. grounded, preferred or stable) node labelling of AF2, then NLab1 is a complete (resp. grounded, preferred or stable) node labelling of AF1.

Proof.

Let AF1=(N1,arr1) and AF2=(N2,arr2) be two AFs such that conditions (1) and (2) are met. For complete, grounded, and preferred semantics, the result is an immediate consequence of the directionality principle. It remains to prove the proposition for stable semantics.

(i) Let NLab1 be stable, i.e., NLab1 is a complete labelling such that undec(NLab1)=∅. By directionality, it holds that NLab2 is a complete node labelling of AF2. To show that NLab2 is a stable node labelling it suffices to prove that undec(NLab2)=∅.
Let A∈N2. In case A∈N1, we have either NLab2(A)=in or NLab2(A)=out since NLab1 is stable. Therefore, NLab2(A)≠undec in this case.
Now, let A∈N2∖N1. By condition (2), A receives no incoming attacks from nodes in N2∖N1. Therefore, all attackers of A are either labelled in or out. We proceed by case distinction: (a) all incoming attackers of A are labelled out. Then A is labelled in, by definition of NLab2. (b) there is an incoming attacker of A that is labelled in. Then A is labelled out, by definition of NLab2. Since no node in N1 is labelled undec, the case distinction is exhaustive. This proves that NLab2 is a stable node labelling of AF2.
(ii) Let NLab2 be a stable node labelling of AF2. It holds that NLab1 is a complete node labelling of AF1 (by directionality); moreover, undec(NLab1)=∅. Therefore, we obtain that NLab1 is a stable node labelling of AF1.

□

Proposition 37.

Proof.

Let AFD=AF2=(N2,arr2) be the AF associated with D. Suppose A is an node that has some out-going arrow. Then, by definition, A is some ABA-argument of the form A=(Asms,γ‾) where γ is some assumption in D. Again by definition the SETAF SFD contains some arrow (Asms,γ) and consequently the inside-out AF AFSFD=AF1=(N1,arr1) contains an argument B=(Asms,γ) corresponding to this arrow. Thus we can assign to any node A in AFD with an out-going arrow a corresponding node B in AFSFD. In the same vein, the arrow relation is preserved: If there is an arrow from A1=(Asms1,γ1‾) to A2=(Asms2,γ2‾) in AFD, then there is an arrow from B1=(Asms1,γ1) to B2=(Asms2,γ2) in AFSFD.

Vice versa, if B=(Asms,γ) is a node in the inside-out AF AFSFD, then we can similarly argue that there is some ABA-argument of the form A=(Asms,γ‾) in AFD. This node must have at least one out-going arrow in AFD since it entails the contrary of γ. The arrow relation is preserved analogously. □

References

[1]	L. Amgoud and C. Cayrol, On the acceptability of arguments in preference-based argumentation framework, in: Proceedings of UAI 1998, (1998) , pp. 1–7.
[2]	P. Baroni, M.W.A. Caminada and M. Giacomin, An introduction to argumentation semantics, Knowledge Engineering Review 26: (4) ((2011) ), 365–410. doi:10.1017/S0269888911000166.
[3]	P. Baroni and M. Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171: (10–15) ((2007) ), 675–700.
[4]	P. Baroni, M. Giacomin and G. Guida, scc-recursiveness: A general schema for argumentation semantics, Artificial Intelligence 168: (1–2) ((2005) ), 165–210.
[5]	R. Baumann, G. Brewka and M. 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.
[6]	R. Baumann and H. 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.
[7]	T.J.M. Bench-Capon, 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.
[8]	A. Bikakis, A. Cohen, W. Dvořák, G. Flouris and S. Parsons, Joint attacks and accrual in argumentation frameworks, FLAP 8: (6) ((2021) ), 1437–1501, https://collegepublications.co.uk/ifcolog/?00048.
[9]	G. Boella, D.M. Gabbay, L.W.N. van der Torre and S. Villata, Meta-argumentation modelling I: Methodology and techniques, Studia Logica 93: (2–3) ((2009) ), 297–355. doi:10.1007/s11225-009-9213-2.
[10]	A. Bondarenko, P.M. Dung, R.A. Kowalski and F. Toni, An abstract, argumentation-theoretic approach to default reasoning, Artificial Intelligence 93: ((1997) ), 63–101. doi:10.1016/S0004-3702(97)00015-5.
[11]	M.W.A. Caminada, On the issue of reinstatement in argumentation, in: Proceedings of JELIA 2006, LNAI 4160, Springer, (2006) , pp. 111–123.
[12]	M.W.A. Caminada, Comparing two unique extension semantics for formal argumentation: Ideal and eager, in: Proceedings of BNAIC 2007, (2007) , pp. 81–87.
[13]	M.W.A. Caminada and L. Amgoud, On the evaluation of argumentation formalisms, Artificial Intelligence 171: (5–6) ((2007) ), 286–310.
[14]	M.W.A. Caminada and D.M. Gabbay, A logical account of formal argumentation, Studia Logica 93: (2–3) ((2009) ), 109–145. Special issue: new ideas in argumentation theory.
[15]	M.W.A. Caminada, S. Sá and J. Alcântara, On the equivalence between logic programming semantics and argumentation semantics, in: Proceedings of ECSQARU 2013, (2013) , pp. 97–108.
[16]	M.W.A. Caminada, S. Sá, J. Alcântara and W. 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]	M.W.A. Caminada, S. Sá, J. Alcântara and W. Dvořák, On the difference between assumption-based argumentation and abstract argumentation, IfCoLog Journal of Logic and its Applications 2: ((2015) ), 15–34.
[18]	C. Cayrol and M. 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]	K. Čyras, X. Fan, C. Schulz and F. Toni, Assumption-based argumentation: Disputes, explanations, preferences, in: Handbook of Formal Argumentation, Vol. 1: , College Publications, (2018) , pp. 365–408.
[20]	P.M. Dung, 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]	P.M. Dung, R.A. Kowalski and F. Toni, Assumption-based argumentation, in: Argumentation in Artificial Intelligence, G. Simari and I. Rahwan, eds, Springer US, (2009) , pp. 199–218. ISBN 978-0-387-98196-3. doi:10.1007/978-0-387-98197-0_10.
[22]	P.M. Dung, P. Mancarella and F. Toni, Computing ideal sceptical argumentation, Artificial Intelligence 171: (10–15) ((2007) ), 642–674.
[23]	P.E. Dunne, W. Dvořák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, Artificial Intelligence 228: ((2015) ), 153–178. doi:10.1016/j.artint.2015.07.006.
[24]	W. Dvořák, J. Fandinno and S. Woltran, On the expressive power of collective attacks, Argument & Computation 10: (2) ((2019) ), 191–230. doi:10.3233/AAC-190457.
[25]	W. Dvořák and S.A. Gaggl, 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]	W. Dvořák, A. Greßler and S. Woltran, Evaluating SETAFs via answer-set programming, in: Proceedings of SAFA 2018, CEUR Workshop Proceedings, Vol. 2171: , CEUR-WS.org (2018) , pp. 10–21, http://ceur-ws.org/Vol-2171/paper_2.pdf.
[27]	W. Dvořák, M. König, M. Ulbricht and S. 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]	W. Dvořák, M. König and S. 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]	W. Dvořák, M. König and S. 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]	W. Dvořák, M. König and S. Woltran, Treewidth for argumentation frameworks with collective attacks, in: Proceedings of COMMA 2022, FAIA, Vol. 353: , IOS Press, (2022) , pp. 140–151.
[31]	W. Dvořák, A. Rapberger and J.P. Wallner, 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]	W. Dvořák, A. Rapberger and S. 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]	W. Dvořák, A. Rapberger and S. 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]	W. Dvořák, A. Rapberger and S. 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]	G. Flouris and A. 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]	D.M. Gabbay, 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]	A.J. García, J. Dix and G.R. Simari, Argument-based logic programming, in: Argumentation in Artificial Intelligence, G. Simari and I. Rahwan, eds, Springer US, (2009) , pp. 153–171. ISBN 978-0-387-98196-3. doi:10.1007/978-0-387-98197-0_8.
[38]	G. Governatori, M.J. Maher, G. Antoniou and D. Billington, Argumentation semantics for defeasible logic, Journal of Logic and Computation 14: (5) ((2004) ), 675–702. doi:10.1093/logcom/14.5.675.
[39]	M. König, A. Rapberger and M. 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]	S. Modgil and H. Prakken, A general account of argumentation with preferences, Artificial Intellligence 195: ((2013) ), 361–397. doi:10.1016/j.artint.2012.10.008.
[41]	S. Modgil and H. Prakken, Abstract rule-based argumentation, in: Handbook of Formal Argumentation, Vol. 1: , College Publications, (2018) , pp. 287–364.
[42]	S.H. Nielsen and S. 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]	S. Polberg, Developing the abstract dialectical framework, PhD thesis, Vienna University of Technology, Institute of Information Systems, (2017) .
[44]	H. Prakken, An abstract framework for argumentation with structured arguments, Argument & Computation 1: (2) ((2010) ), 93–124. doi:10.1080/19462160903564592.
[45]	A. 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]	A. Rapberger and M. Ulbricht, On dynamics in structured argumentation formalisms, Journal of Artificial Intelligence Research 77: ((2023) ), 563–643. doi:10.1613/JAIR.1.14481.
[47]	C. Schultz and F. Toni, Complete assumption labellings, in: Proceedings of COMMA 2014, (2014) , pp. 405–412.
[48]	G.R. Simari and R.P. Loui, A mathematical treatment of defeasible reasoning and its implementation, Artificial Intelligence 53: ((1992) ), 125–157. doi:10.1016/0004-3702(92)90069-A.
[49]	F. Toni, Reasoning on the web with assumption-based argumentation, in: Reasoning Web. Semantic Technologies for Advanced Query Answering, T. Eiter and T. Krennwallner, eds, (2012) , pp. 370–386. doi:10.1007/978-3-642-33158-9_10.
[50]	M. 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]	B. Verheij, Two approaches to dialectical argumentation: Admissible sets and argumentation stages, in: Proceedings of NAIC 1996, (1996) , pp. 357–368.
[52]	S. Villata, G. Boella and L. van der Torre, Attack semantics for abstract argumentation, in: Proceedings of IJCAI 2011, (2011) , pp. 164–171.
[53]	G.A.W. Vreeswijk, Abstract argumentation systems, Artificial Intelligence 90: ((1997) ), 225–279. doi:10.1016/S0004-3702(96)00041-0.
[54]	Y. Wu, M.W.A. Caminada and D.M. Gabbay, 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.