=Paper=
{{Paper
|id=Vol-2171/paper_2
|storemode=property
|title=Evaluating SETAFs via Answer-Set Programming
|pdfUrl=https://ceur-ws.org/Vol-2171/paper_2.pdf
|volume=Vol-2171
|authors=Wolfgang Dvořák,Alexander Greßler,Stefan Woltran,Odinaldo Rodrigues,Elizabeth Black,Michael Luck,Josh Murphy,Tastuki Kawasaki,Sosuke Moriguchi,Kazuko Takahashi,Grzegorz Lisowski,Sylvie Doutre,Umberto Grandi,Sosuke Moriguchi,Kazuko Takahashi
|dblpUrl=https://dblp.org/rec/conf/comma/DvorakGW18
}}
==Evaluating SETAFs via Answer-Set Programming==
https://ceur-ws.org/Vol-2171/paper_2.pdf
10 W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming
Evaluating SETAFs via Answer-Set
Programming
Wolfgang DVOŘÁK a , Alexander GRESSLER a and Stefan WOLTRAN a
a Institute of Logic and Computation, TU Wien
Abstract. Following the tradition of the ASPARTIX system, we present answer-set
programming encodings for the main semantics of argumentation frameworks with
collective attacks (also known as SETAFs). By that, we provide the first system
dedicated to reasoning in SETAFs. Since to date, no known polynomial-time (with
respect to the number of arguments) translation from SETAFs to Dung-style frame-
works is known, genuine implementations for SETAFs appear necessary towards
practically efficient systems for this particular formalism. As a by-product, we in-
troduce semi-stable and stage semantics for SETAFs and pinpoint the complexity
of all considered semantics.
Keywords. abstract argumentation, answer-set programming, collective attacks,
SETAF
1. Introduction
Abstract argumentation frameworks (AFs) as introduced by Dung in his seminal pa-
per [7] are a core formalism in formal argumentation and have been extensively studied
in the literature. In Dung AFs, conflicts and attacks are restricted to be binary in the sense
that a single attack only concerns two arguments.
SETAFs as introduced by Nielsen and Parsons [23] are a generalization of Dung AFs
which generalize the binary attacks in Dung AFs to collective attacks. This enables the
formalization of the fact that a set B of arguments may jointly attack another argument
a but no proper subset of B attacks a. The semantics as proposed in [23], make SETAFs
a conservative generalization of Dung AFs; in other words, a SETAF where all attacks
are binary is evaluated in the same way as the corresponding Dung AF. As illustrated
in [23], there are several scenarios where arguments interact and can constitute an attack
on another argument only if these arguments are jointly taken into account. Representing
such a situation in Dung AFs often requires additional artificial arguments to “encode”
the conjunction of arguments, potentially causing an exponential blow-up in the number
of arguments [24]. In [24] it is also shown that SETAFs allow for more straightforward
and compact encodings of support between arguments than AFs do. Moreover, recent
work [11] shows that the collective attacks of SETAFs increase the expressiveness when
compared to Dung AFs.
Computational properties of SETAFs have been neglected so far. One notable excep-
tion is by Nielsen and Parsons [22] who adapted the algorithms by Doutre and Mengin [6]
for enumerating preferred extensions in Dung AFs to SETAFs. Besides that, SETAFs
have been identified as special case of the more general Abstract Dialectical Frameworks
W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming 11
(ADFs) [2] and thus systems for ADFs, e.g. the DIAMOND system [18], can in principle
be used to evaluate SETAFs as well. However, these systems have a significant drawback
since SETAFs are encoded in a more complex formalism leading to a potential computa-
tional overhead. Another way to evaluate SETAFs is to translate them to Dung AFs and
use existing systems. However, since to date, no known polynomial-time (with respect
to the number of arguments) translation from SETAFs to AFs is known, this again might
cause a non-negligible computational overhead. Genuine implementations for SETAFs
thus appear necessary towards practically efficient systems.
The main aim of this work is to provide a flexible system dedicated to reasoning in
SETAFs with a broad range of semantics. Answer-Set Programming (ASP) [1] proved
useful for rapid prototyping of systems for Dung AFs (see e.g. [13,19,25]) and gener-
alization thereof (see e.g. [18,12]). We follow the approach of the ASPARTIX system,
where for each semantics a fixed encoding is provided which when combined with an
AF as input returns the corresponding extensions. We provide ASP-encodings for all the
SETAF-semantics defined in [23] as well as semi-stable and stage semantics. These en-
codings are also provided in executable format 1 and can be used to enumerate extensions
or to decide credulous and skeptical acceptance for SETAFs.
Our contributions and the organization of the paper are as follows. We first recall
the definitions and fundamental results from [23] (see Section 2) and then generalize
the definitions of semi-stable and stage semantics to SETAFs (see Section 2.1). Next,
we clarify the complexity landscape of SETAFs for the standard reasoning problems
(see Section 2.2). In the main part of our paper we provide ASP-encodings for the dif-
ferent semantics of SETAFs (see Section 3). Finally, we discuss our results in a con-
clusion section. The appendices with some technical results are omitted in this version
but a full version is provided at https://dbai.tuwien.ac.at/research/report/
dbai-tr-2018-112.pdf.
2. Argumentation Frameworks with Collective Attacks
We first introduce formal definitions of argumentation frameworks with collective attacks
following [23].
Definition 1. A SETAF is a pair F = (A, R) where A is finite, and R ⊆ (2A \ 0) / × A is the
attack relation. We write S 7→R b if there is a set S0 ⊆ S with (S0 , b) ∈ R. Moreover, we
write S0 7→R S if S0 7→R b for some b ∈ S. For S ⊆ A, the range of S (w.r.t. R), denoted SR⊕ ,
is the set S ∪ {b | S 7→R b}.
We call a SETAF with binary attacks only, i.e. |S| = 1 for each (S, a) ∈ R, Dung argu-
mentation framework (AF) as such SETAFs are equivalent to the AFs introduced in [7].
Example 1. Consider an argumentation framework with arguments a, b, c where each
pair of arguments attacks the third argument. This is modeled by the SETAF F = (A, R)
with arguments A = {a, b, c} and attacks R = {({a, b}, c), ({a, c}, b), ({b, c}, a)}. ♦
The notion of defense naturally generalizes to SETAFs.
1 See www.dbai.tuwien.ac.at/research/argumentation/aspartix/setaf.html.
12 W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming
Definition 2. Given a SETAF F = (A, R), an argument a ∈ A is defended (in F) by a set
S ⊆ A if for each B ⊆ A, such that B 7→R a, also S 7→R B. A set T of arguments is defended
(in F) by S if each a ∈ T is defended by S (in F).
Based on the concept of defense also the definition of the characteristic function of
an argumentation framework can be extended to SETAFs.
Definition 3. The characteristic function of an SETAF F = (A, R) is the function FF :
2A → 2A with FF (S) = {a ∈ A : a is defended by S}.
2.1. Semantics
Next, we introduce the semantics we study in this work. These are the naive, stable, pre-
ferred, complete, grounded, stage, and semi-stable semantics, which we will abbreviate
by naive, stb, pref, com, grd, stage, and sem, respectively. All semantics except semi-
stable and stage are defined according to [23], while semi-stable and stage are straight
forward generalizations of the according semantics for Dung AFs [26,3]. For a given
semantics σ , σ (F) denotes the set of extensions of F under σ .
Definition 4. Given a SETAF F = (A, R), a set S ⊆ A is conflict-free (in F), if S0 ∪{a} 6⊆ S
for each (S0 , a) ∈ R. We denote the set of all conflict-free sets in F as cf(F). S ∈ cf(F) is
called admissible (in F) if S defends itself. We denote the set of admissible sets in F as
adm(F). For a conflict-free set S ∈ cf(F), we say that
• S ∈ naive(F), if there is no T ∈ cf(F) such that T ⊃ S,
• S ∈ stb(F), if S 7→R a for all a ∈ A \ S,
• S ∈ pref(F), if S ∈ adm(F) and there is no T ∈ adm(F) such that T ⊃ S,
• S ∈ com(F), if S ∈T adm(F) and a ∈ S for all a ∈ A defended by S,
• S ∈ grd(F), if S = T ∈com(F) T ,
• S ∈ stage(F), if there is no T ∈ cf(F) such that TR⊕ ⊃ SR⊕ , and
• S ∈ sem(F), if S ∈ adm(F) and there is no T ∈ adm(F) such that TR⊕ ⊃ SR⊕ .
As shown in [23], most of the fundamental properties of Dung AFs extend to
SETAFs. We have the same relations between the semantics as in Dung AFs, i.e. stb(F) ⊆
sem(F) ⊆ pref(F) ⊆ com(F) ⊆ adm(F) ⊆ cf(F) and stb(F) ⊆ stage(F) ⊆ naive(F). The
grounded extension is the unique minimal complete extension for any SETAF F. If there
is at least one stable extension then stable, semi-stable, and stage semantics coincide.
The properties for semi-stable and stage semantics follow from straightforward adapta-
tions of the proofs for Dung AFs (see Appendix A in the full version). Moreover, Dung’s
fundamental lemma generalizes to SETAFs.
Lemma 1 ([23]). Given a SETAF F = (A, R), a set B ⊂ A, and arguments a, b ∈ A that
are defended by B. Then (a) B ∪ {a} is admissible in F and (b) B ∪ {a} defends b in F.
2.2. Complexity
In this section we assume the reader to have basic knowledge in computational complex-
ity theory2 , in particular we make use of the complexity classes L (logarithmic space), P
(polynomial time), NP (non-deterministic polynomial time), coNP, ΣP2 and ΠP2 .
2 For a gentle introduction to complexity theory in the context of formal argumentation, see [10].
W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming 13
Table 1. Complexity of SETAFs (C -c denotes completeness for class C ).
σ Credσ Skeptσ Verσ Existsσ Exists¬
σ
0/
cf in L trivial in L trivial in L
naive in L in L in L trivial in L
grd P-c P-c P-c trivial in L
stb NP-c coNP-c in L NP-c NP-c
adm NP-c trivial in L trivial NP-c
com NP-c P-c in L trivial NP-c
pref NP-c ΠP
2 -c coNP-c trivial NP-c
sem ΣP
2 -c ΠP
2 -c coNP-c trivial NP-c
stage ΣP
2 -c ΠP
2 -c coNP-c trivial in L
For a given SETAF we consider the standard reasoning problems in formal argu-
mentation: Credulous acceptance Credσ : Is a given argument contained in at least one σ
extension?; Skeptical acceptance Skeptσ : Is a given argument contained in all σ exten-
sions?; Verification Verσ : Is a given set a σ extensions of the SETAF?; Existence of a
Extension Existsσ : Does the SETAF have a σ extension?; and Existence of a nonempty
Extension Exists¬σ 0/ : Does the SETAF have a non-empty σ extension?
The complexity landscape of SETAFs coincides with that of Dung AFs and is
depicted in Table 1. As SETAFs generalize Dung AFs the hardness results for Dung
AFs [4,5,8,14,15,9] (for a survey see [10]) carry over to SETAFs. Interestingly also the
same upper bounds hold for SETAFs. In SETAFs checking whether a set is conflict-free
and evaluating the characteristic function is more evolved than in Dung AFs but still can
be done in L. As this is at the basis of the complexity upper bounds for Dung AFs, these
upper bounds also apply to SETAFs with slight adaptations in the algorithms (details are
provided in Appendix B of the full version). Notice that also our ASP-encodings implic-
itly show matching upper bounds for many of the decision problems (by the complexity
of the corresponding fragments of the ASP language).
However, we want to highlight a subtle difference between the complexity results for
Dung AFs and SETAFs. In both cases the complexity is w.r.t. the size of the input frame-
work, which in case of Dung AFs is often interpreted as w.r.t. the number of arguments
|A| in the input framework. However, this interpretation is not valid for SETAFs where
the number of attacks |R| can be exponentially larger than the number of arguments |A|
(this even holds for normal forms where redundant attacks are removed). Thus, the re-
sults for SETAFs should be understood as complexity w.r.t. |A| + |R|. This also reflects
the fact that when translating SETAFs to AFs there can be an exponential blow up in the
number of arguments [24].
3. ASP-Encodings
In this part of the paper we provide ASP-encodings for the different SETAF semantics.
We do this by following the same approach as in the ASPARTIX system [16,19] for
Dung AFs. That is, for each of the semantics we provide a fixed encoding (a.k.a. query)
that, when combined with the encoding of a SETAF as input, returns the corresponding
extensions as answer-sets.
14 W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming
In what follows, we first give an overview on disjunctive logic programs under the
answer-sets semantics (Section 3.1), then we state the input format for SETAFs (Sec-
tion 3.2), and finally we present our encodings for the different semantics (Section 3.3).
3.1. Background on ASP
We give an overview of the syntax and semantics of disjunctive logic programs under the
answer-sets semantics [21].
We fix a countable set U of (domain) elements, also called constants. An atom is
an expression p(t1 , . . . ,tn ), where p is a predicate of arity n ≥ 0 and each ti is either a
variable or an element from U . An atom is ground if it is free of variables. BU denotes
the set of all ground atoms over U . A (disjunctive) rule r is of the form
a1 | · · · | an ← b1 , . . . , bk , not bk+1 , . . . , not bm (1)
with n ≥ 0, m ≥ k ≥ 0, n + m > 0, where a1 , . . . , an , b1 , . . . , bm are literals, and “not ”
stands for default negation. The head of r is the set H(r) = {a1 , . . . , an } and the body
of r is B(r) = {b1 , . . . , bk , not bk+1 , . . . , not bm }. Furthermore, B+ (r) = {b1 , . . . , bk } and
B− (r) = {bk+1 , . . . , bm }. A rule r is normal if n ≤ 1 and a constraint if n = 0. A rule r is
safe if each variable in r occurs in B+ (r). A rule r is ground if no variable occurs in r.
A fact is a ground rule without disjunction and empty body. An (input) database is a set
of facts. A program is a finite set of disjunctive rules. If each rule in a program is normal
(resp. ground), we call the program normal (resp. ground).
For any program π, let Uπ be the set of all constants appearing in π. Gr(π) is the
set of rules rσ obtained by applying, to each rule r ∈ π, all possible substitutions σ from
the variables in r to elements of Uπ . An interpretation I ⊆ BU satisfies a ground rule r
iff H(r) ∩ I 6= 0/ whenever B+ (r) ⊆ I and B− (r) ∩ I = 0. / I satisfies a ground program π,
if each r ∈ π is satisfied by I. A non-ground rule r (resp., a program π) is satisfied by an
interpretation I iff I satisfies all groundings of r (resp., Gr(π)). I ⊆ BU is an answer-set
of π iff it is a subset-minimal set satisfying the Gelfond-Lifschitz reduct π I = {H(r) ←
B+ (r) | I ∩ B− (r) = 0, / r ∈ Gr(π)}. For a program π, we denote the set of its answer-sets
by AS(π).
Modern ASP solvers offer additional language features. Among them we make use
of the conditional literal [20]. In the head of a disjunctive rule literals may have condi-
tions, e.g. consider the head of rule “p(X) : q(X) ←”. Intuitively, this represents a head
of disjunctions of atoms p(a) where also q(a) is true. As well rules might have condi-
tions in their body, e.g. consider the body of rule “← p(X) : q(X)”, which intuitively
represents a conjunction of atoms p(a) where also q(a) is true.
3.2. Encoding SETAFs
Before specifying the encodings for the specific semantics, we need to fix an encoding
πseta f (A, R) of SETAFs as input databases. A SETAF F = (A, R) is encoded by predicates
arg, att, and mem. The former is used to encode arguments, the latter two to encode the
set attacks. Notice that the encoding uses a unique identifier for each attack in R.
W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming 15
πseta f (A, R) : {arg(a). | for a ∈ A} ∪
{att(r, x). | for r ∈ R and r = (S, x)} ∪
{mem(r, y). | for r ∈ R, r = (S, x) and y ∈ S}
We next exemplify this encoding on the SETAF from Example 1.
Example 2. Consider the SETAF F from Example 1. The encoding πseta f (F) of F is
given by
arg(a). arg(b). arg(c).
att(r1, c). mem(r1, a). mem(r1, b).
att(r2, b). mem(r2, a). mem(r2, c).
att(r3, a). mem(r3, b). mem(r3, c). ♦
3.3. Encoding Semantics
In this section we provide encodings πσ for the semantics under our considerations, such
that the answer-sets of πseta f (F) ∪ πσ are in certain correspondence to the σ -extensions
of F = (A, R). Intuitively, in an answer-set we are interested in the set of atoms for which
the predicate in holds true and we require these sets to be in a one to one correspondence
to the extensions of the SETAF F. We make our notion of correspondence precise by the
next definition.
Definition 5. Let S ⊆ 2U be a collection of sets of domain elements and let I ⊆ 2BU
be a collection of sets of ground atoms. We say that S and I correspond to each other, in
symbols S ∼ = I , iff (i) for each S ∈ S, there exists an I ∈ I , such that {a | in(a) ∈ I} = S;
(ii) for each I ∈ I , it holds that {a | in(a) ∈ I} ∈ S; and (iii) |S| = |I|.
Notice that by the above definition we want to avoid situations where several answer-
sets correspond to the same extension of the SETAF.
3.3.1. Conflict-free Semantics
We start with a program fragment that, when augmented by πseta f (F), generates any sub-
set S ⊆ A and can then be augmented by further program fragments to filter out exten-
sions of specific semantics.
πguess : in(Y ) ← arg(Y ), not out(Y ).
out(Y ) ← arg(Y ), not in(Y ).
We call an attack (B, a) ∈ R blocked w.r.t. a set S ⊆ A if B 6⊆ S. In our encoding of
the conflict-freeness test we first compute the blocked attacks and then use a constraint
that checks whether there is a non-blocked attack that attacks an argument in S.
πc f 0 : blocked(R) ← mem(R, X), out(X).
← in(X), att(R, X), not blocked(R).
To enumerate the conflict-free sets of a SETAF F we combine the above code frag-
ments, i.e. we define πc f = πguess ∪ πc f 0 and obtain that cf(F) ∼
= AS(πseta f (F) ∪ πc f ).
16 W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming
3.3.2. Admissible & Complete Semantics
For admissible semantics we start from the encoding of conflict-free semantics and add
constraints to make sure that all arguments in the set are defended. To this end we intro-
duce the concept of defeated attacks. An attack (S, a) ∈ R is considered to be defeated by
a set E iff E attacks at least one x ∈ S. Given the blocked (resp. the unblocked) attacks we
can easily compute the defeated attacks. Now the definition of defense can be restated
as, an argument x is defended by as set E iff all attacks (S, x) are defeated. The code
fragment πde f consists of a rule that computes the defeated attacks and a constraint that
checks that each argument in the extension is defended by the extension.
πde f : defeated(R) ← att(R, X), mem(R,Y ), att(R2,Y ), not blocked(R2).
← in(X), att(R, X), not defeated(R).
Now we obtain the encoding πadm for admissible semantics by adding the above code
fragment to the encoding of conflict-free semantics, i.e, πadm = πc f ∪ πde f and we have
adm(F) ∼ = AS(πseta f (F) ∪ πadm ).
For complete semantics we, additionally to admissible semantics, have to make
sure that no argument outside the set is defended. We do so by computing a predicate
notDefended of arguments not defended by the extension and then add a constraint that
checks whether there is an argument outside the extension for which the predicate does
not hold true.
πcl : notDefended(X) ← att(R, X), not defeated(R).
← out(X), not notDefended(X).
Now we obtain πcomp = πadm ∪ πcl as encoding for complete semantics, i.e. com(F) ∼
=
AS(πseta f (F) ∪ πcomp ).
3.3.3. Stable Semantics
To test whether a conflict-free set is stable we first compute all arguments that are at-
tacked, and store them in the predicate attArg(Y ). We then apply a constraint to test
whether there is an argument that is neither in nor attacked by the extension.
πstb0 : attArg(X) ← att(R, X), not blocked(R).
← out(X), not attArg(X).
Combining the above fragment with the encoding for conflict-free semantics results the
encoding πstb = πc f ∪ πstb0 of stable semantics with stb(F) ∼
= AS(πseta f (F) ∪ πstb ).
3.3.4. Naive Semantics
Given a conflict-free set E, it is either a naive extension or there is an argument a ∈ A \ E
such that E ∪ {a} is conflict-free. Thus, we first compute a binary predicate blocked(r, a)
encoding that an attack r is blocked for the set E ∪ {a}. We then use this predicate to
check whether E ∪{a} has a conflict and if so, we set conflArg(a) true. Finally, we check
whether there is an argument a ∈ A \ E such that E ∪ {a} is conflict-free.
W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming 17
πc f max : blocked(R, A) ← out(A), mem(R, X), out(X), X 6= A.
conflArg(A) ← out(A), in(X), att(R, X), not blocked(R, A).
conflArg(A) ← out(A), att(R, A), not blocked(R, A).
← out(A), not conflArg(A).
Now the full encoding for naive semantics is πnaive = πc f ∪ πc f max , i.e. we have
naive(F) ∼
= AS(πseta f (F) ∪ πnaive ).
3.3.5. Preferred Semantics
For the encoding of preferred semantics we start from the encoding of admissible sets
and add a maximality check using the so-called saturation technique [17] (see also [16]).
The idea is to use disjunctive rules to construct a superset (stored in the sIn predicate) of
the admissible set stored in the in predicate. We first use a disjunctive rule to guess an
argument that can be added to the set and then add further arguments in order to defend
all arguments in the set. We then perform certain tests to check whether the set is actually
admissible. If one of the tests fails we derive an atom fail and force all arguments to be
in the sIn predicate and all attacks to be in the necAtt predicate (which we introduce
later on), to make sure there is at most one answer-set for each extension. In case all tests
succeed, i.e. the set is admissible, there is a constraint ensuring that the guess does not
produce an answer-set.
We first consider the construction of the superset. In a first step we test whether
the admissible set already contains all arguments of the AF. In that case it is the only
preferred extension and we can skip the saturation part. Otherwise, we (a) require all
arguments in in to be also contained in sIn and (b) use the conditional disjunction to
force that at least one of the arguments not in in (thus in out) is in sIn. 3
π pr f −guess : notTrivial ← out(X).
sIn(X) ← in(X), notTrivial.
sIn(X) : out(X) ← notTrivial.
For the saturation technique to work we are not allowed to use not with any predicate that
appears in the head of any rule in the saturation block, except for the not fail at the very
end. In particular we cannot compute the unblocked attacks w.r.t. the set stored sIn via a
predicate for the blocked attacks (as we did for the blocked attacks w.r.t. the arguments in
in). To overcome this we compute the unblocked attacks, i.e. the predicate unBlocked,
directly using conditionals in the body of the rule.
πunblocked : unBlocked(R) ← att(R,Y ), sIn(X) : mem(R, X).
3 Conditional disjunction allows for more compact saturation based encodings and investigations on AF also
show computational benefits [19].
18 W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming
Next, we make sure that the constructed set either defends all its arguments or derives
fail. To this end we introduce a new predicate necAtt that holds attacks that must be
unblocked in order to defend all the arguments of the set. First, we have a rule stating
that if an argument x of the set is attacked by r = (S, x) ∈ R then there must be a r0 ∈ R
that attacks one argument y ∈ S. If such attacks r0 exist, one of them is added to necAtt,
otherwise the set is obviously not admissible and we derive fail. Our second rule states
that if a rule r = (S, x) ∈ R is unblocked then all arguments in S must be in the extension.
π pr f −adm : fail|necAtt(R2) : att(R2,Y ), mem(R1,Y ) ← sIn(X), att(R1, X).
sIn(X) ← necAtt(R), mem(R, X).
Next, we have a rule that derives fail if the constructed set of arguments is not conflict-
free, i.e. if we have a unblocked attack whose target argument is in the set.
π pr f −c f : fail ← sIn(Y ), att(R,Y ), unBlocked(R).
Finally, we have a fragment that completes the saturation. Whenever we derive fail we
make sure that (a) all arguments are in sIn and (b) all attacks are in necAtt. Otherwise,
if we can derive not fail then we have found a larger admissible set and thus we have a
constraint excluding such answer-sets.
π pr f −spoil : sIn(X) ← fail, arg(X).
necAtt(R) ← fail, att(R, X).
← not fail, notTrivial.
If the predicate in already stores a preferred extensions, all guesses from π pr f −guess will
eventually derive fail and thus all end up with the same answer-set where all arguments
are in sIn and all attacks are in necAtt. Otherwise, if the set of predicate in is admissible
but not preferred, then at least one guess from π pr f −guess will not derive fail. For this
guess, because of the constraint in π pr f −spoil , no answer-set will be returned. Moreover,
also all the guesses which derive fail and thus have all arguments in sIn and all attacks
in necAtt, do not return an answer-set because of the subset-minimal model criteria of
answer-set semantics.
Finally, we obtain the encoding π pre f for preferred semantics by augmenting the en-
coding for admissible (or alternatively complete) semantics by all the above code frag-
ments, i.e. π pre f = πadm ∪ π pr f −guess ∪ πunblocked ∪ π pr f −adm ∪ π pr f −c f ∪ π pr f −spoil and we
have pref(F) ∼ = AS(πseta f (F) ∪ π pre f ).
3.3.6. Semi-Stable and Stage Semantics
We next introduce the encodings for semi-stable and stage semantics. The former starts
from the encoding of admissible semantics while the latter starts from the encoding of
conflict-free sets. We will again make use of the saturation technique with the additional
challenge that we have to encode the range and maximize along the range.
We first define the predicate sPlus that holds the range of the admissible/conflict-
free set stored in. That is, we have two rules, one stating that each argument in the set is
also in the range and one stating that each target of an unblocked rule is in the range.
W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming 19
πrange : sPlus(Y ) ← in(Y ).
sPlus(Y ) ← att(X,Y ), not blocked(X).
notSPlus(Y ) ← not sPlus(Y ), arg(Y ).
Before starting with the saturation technique, we test whether the admissible/conflict-
free set is already stable and thus semi-stable/stage. If not we again make a guess for sat-
uration technique, but this time, as we are maximizing the range, we guess an argument
that can be added to the range.
πextRange : notStable ← arg(Y ), not sPlus(Y ).
extRange(Y ) : notSPlus(Y ) ← notStable.
extRange(Y ) ← sPlus(Y ), notStable.
Now we have to make sure that each argument is either in the constructed extensions, i.e.
in sIn, or the target of an unblocked attack, i.e. in necAtt. We then have an additional rule
that makes sure that each attack (S, x) ∈ necAtt is unblocked by adding all arguments of
S to sIn.
π justRange : sIn(X)|necAtt(R) : att(R, X) ← extRange(X).
sIn(X) ← att(R,Y ), necAtt(R), mem(R, X).
We next add code fragments to test whether the constructed set is actually an extension.
The next fragment tests whether the constructed set is conflict-free and if not derives fail.
πsatC f : unBlocked(R) ← att(R,Y ), sIn(X) : mem(R, X).
fail ← sIn(Y ), att(R,Y ), unBlocked(R).
The following rule test whether the constructed set is admissible and is thus only used
for semi-stable but not for stage semantics.
πsatAdm : fail|necAtt(R2) : att(R2,Y ), mem(R1,Y ) ← sIn(X), att(R1, X).
Finally, we complete the saturation with a code fragment that again spoils the answer-set
that can derive fail and avoids answer-sets for guesses where one cannot derive fail. In
comparison to preferred semantics we additionally require that whenever we derive fail
then all arguments are added to extRange.
πspoil : sIn(X) ← fail, arg(X).
extRange(X) ← fail, arg(X).
necAtt(R) ← fail, att(R, X).
← not fail, notStable.
Now we get our encoding πsemi for semi-stable semantics by combing all the above
code fragments with the encoding of admissible semantics, i.e. πsemi = πadm ∪ πrange ∪
20 W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming
πextRange ∪ π justRange ∪ πsatC f ∪ πsatAdm ∪ πspoil and we have sem(F) ∼ = AS(πseta f (F) ∪
πsemi ). Moreover, to obtain the encoding πstage for stage semantics we combine all
the above code fragments, except πsatAdm with the encoding of conflict-free sets, i.e.
πstage = πc f ∪ πrange ∪ πextRange ∪ π justRange ∪ πsatC f ∪ πspoil and we have stage(F) ∼=
AS(πseta f (F) ∪ πstage ).
4. Conclusion
In this work we first clarified the complexity landscape of SETAFs and provided def-
initions for semi-stable and stage semantics that generalize their counterparts in Dung
AFs. We then provided ASP-encodings for the standard SETAF semantics as introduced
in [23] as well as for the semi-stable and stage semantics. Our ASP-encodings can be
executed with the clingo [20] solver and are available at www.dbai.tuwien.ac.at/
research/argumentation/aspartix/setaf.html. Beside enumerating all exten-
sions, the solver features brave (a.k.a. credulous) and cautious (a.k.a. skeptical) reason-
ing. In particular, in order to compute the grounded extension, one can perform cautious
reasoning on complete semantics.
Acknowledgments. This research has been supported by the Austrian Science Fund
(FWF): I2854, Y698.
References
[1] Gerhard Brewka, Thomas Eiter, and Mirosław Truszczyński. Answer set programming at a glance.
Commun. ACM, 54(12):92–103, 2011.
[2] Gerhard Brewka, Stefan Ellmauthaler, Hannes Strass, Johannes P. Wallner, and Stefan Woltran. Abstract
dialectical frameworks. An overview. IfCoLog Journal of Logics and their Applications, 4(8):2263–
2318, 2017.
[3] Martin Caminada, Walter A. Carnielli, and Paul E. Dunne. Semi-stable semantics. J. Log. Comput.,
22:1207–1254, 2012.
[4] Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis. Symmetric argumentation frameworks.
In Lluis Godo, editor, Proceedings of the 8th European Conference on Symbolic and Quantitative Ap-
proaches to Reasoning with Uncertainty (ECSQARU 2005), volume 3571 of Lecture Notes in Computer
Science, pages 317–328. Springer, 2005.
[5] Yannis Dimopoulos and Alberto Torres. Graph theoretical structures in logic programs and default
theories. Theor. Comput. Sci., 170(1-2):209–244, 1996.
[6] Sylvie Doutre and Jérôme Mengin. Preferred extensions of argumentation frameworks: Query answer-
ing and computation. In Rajeev Goré, Alexander Leitsch, and Tobias Nipkow, editors, Automated Rea-
soning, First International Joint Conference, IJCAR 2001, Siena, Italy, June 18-23, 2001, Proceedings,
volume 2083 of Lecture Notes in Computer Science, pages 272–288. Springer, 2001.
[7] Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reason-
ing, logic programming and n-person games. Artif. Intell., 77(2):321–358, 1995.
[8] Paul E. Dunne and Trevor J. M. Bench-Capon. Coherence in finite argument systems. Artif. Intell.,
141(1/2):187–203, 2002.
[9] Wolfgang Dvořák. Computational Aspects of Abstract Argumentation. PhD thesis, Vienna University
of Technology, Institute of Information Systems, 2012.
[10] Wolfgang Dvořák and Paul E. Dunne. Computational problems in formal argumentation and their com-
plexity. IfCoLog Journal of Logic and its Applications, 4(8):2557–2622, 2017.
[11] Wolfgang Dvořák, Jorge Fandinno, and Stefan Woltran. On the expressive power of collective attacks.
In Sanjay Modgil, editor, to appear in Proceedings of COMMA 20018, 2018.
W. Dvořák et al. / Evaluating SETAFs via Answer-Set Programming 21
[12] Wolfgang Dvořák, Sarah Alice Gaggl, Thomas Linsbichler, and Johannes Peter Wallner. Reduction-
based approaches to implement Modgil’s extended argumentation frameworks. In Thomas Eiter, Hannes
Strass, Miroslaw Truszczynski, and Stefan Woltran, editors, Advances in Knowledge Representation,
Logic Programming, and Abstract Argumentation - Essays Dedicated to Gerhard Brewka on the Occa-
sion of His 60th Birthday, volume 9060 of Lecture Notes in Computer Science, pages 249–264. Springer,
2015.
[13] Wolfgang Dvořák, Sarah Alice Gaggl, Johannes Peter Wallner, and Stefan Woltran. Making use of
advances in answer-set programming for abstract argumentation systems. CoRR, abs/1108.4942, 2011.
In Proceedings of the 19th International Conference on Applications of Declarative Programming and
Knowledge Management (INAP 2011).
[14] Wolfgang Dvořák and Stefan Woltran. Complexity of semi-stable and stage semantics in argumentation
frameworks. Inf. Process. Lett., 110(11):425–430, 2010.
[15] Wolfgang Dvořák and Stefan Woltran. On the intertranslatability of argumentation semantics. J. Artif.
Intell. Res. (JAIR), 41:445–475, 2011.
[16] Uwe Egly, Sarah Alice Gaggl, and Stefan Woltran. Answer-set programming encodings for argumenta-
tion frameworks. Argument and Computation, 1(2):147–177, 2010.
[17] Thomas Eiter and Axel Polleres. Towards automated integration of guess and check programs in answer
set programming: a meta-interpreter and applications. TPLP, 6(1-2):23–60, 2006.
[18] Stefan Ellmauthaler and Hannes Strass. DIAMOND 3.0 - A native C++ implementation of DIAMOND.
In Pietro Baroni, Thomas F. Gordon, Tatjana Scheffler, and Manfred Stede, editors, Computational Mod-
els of Argument - Proceedings of COMMA 2016, Potsdam, Germany, 12-16 September, 2016., volume
287 of Frontiers in Artificial Intelligence and Applications, pages 471–472. IOS Press, 2016.
[19] Sarah Alice Gaggl, Norbert Manthey, Alessandro Ronca, Johannes Peter Wallner, and Stefan Woltran.
Improved answer-set programming encodings for abstract argumentation. TPLP, 15(4-5):434–448,
2015.
[20] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Marius Lindauer, Max Ostrowski, Javier
Romero, Torsten Schaub, and Sven Thiele. Potassco User Guide. Univ. Potsdam, second edition edition,
2015.
[21] Michael Gelfond and Vladimir Lifschitz. Classical negation in logic programs and disjunctive databases.
New Generation Computing, 9(3/4):365–386, 1991.
[22] Søren Holbech Nielsen and Simon Parsons. Computing preferred extensions for argumentation systems
with sets of attacking arguments. In Paul E. Dunne and Trevor J. M. Bench-Capon, editors, Compu-
tational Models of Argument: Proceedings of COMMA 2006, September 11-12, 2006, Liverpool, UK,
volume 144 of Frontiers in Artificial Intelligence and Applications, pages 97–108. IOS Press, 2006.
[23] Søren Holbech Nielsen and Simon Parsons. A generalization of Dung’s abstract framework for argu-
mentation: Arguing with sets of attacking arguments. In Proc. ArgMAS, volume 4766 of Lecture Notes
in Computer Science, pages 54–73. Springer, 2006.
[24] Sylwia Polberg. Developing the abstract dialectical framework. PhD thesis, TU Wien, Institute of
Information Systems, 2017.
[25] Francesca Toni and Marek Sergot. Argumentation and answer set programming. In Marcello Balduccini
and Tran C. Son, editors, Logic Programming, Knowledge Representation, and Nonmonotonic Reason-
ing: Essays in Honor of Michael Gelfond, volume 6565 of Lecture Notes in Computer Science, pages
164–180. Springer, 2011.
[26] Bart Verheij. Two approaches to dialectical argumentation: admissible sets and argumentation stages.
In John Jules C. Meyer and Linda C. van der Gaag, editors, Proceedings of the 8th Dutch Conference on
Artificial Intelligence (NAIC’96), pages 357–368, 1996.