Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems

Abstract

Dung’s famous abstract argumentation frameworks represent the core formalism for many problems and applications in the field of argumentation which significantly evolved within the last decade. Recent work in the field has thus focused on implementations for these frameworks, whereby one of the main approaches is to use Answer-Set Programming (ASP). While some of the argumentation semantics can be nicely expressed within the ASP language, others required rather cumbersome encoding techniques. Recent advances in ASP systems, in particular, the metasp optimization front-end for the ASP-package gringo/claspD provide direct commands to filter answer sets satisfying certain subset-minimality (or -maximality) constraints. This allows for much simpler encodings compared to the ones in standard ASP language. In this paper, we experimentally compare the original encodings (for the argumentation semantics based on preferred, semi-stable, and respectively, stage extensions) with new metasp encodings. Moreover, we provide novel encodings for the recently introduced resolution-based grounded semantics. Our experimental results indicate that the metasp approach works well in those cases where the complexity of the encoded problem is adequately mirrored within the metasp approach.

This work has been funded by the Vienna Science and Technology Fund (WWTF) through project ICT08-028.

1 Introduction

In Artificial Intelligence (AI), the area of argumentation (the survey by Bench-Capon and Dunne  [3] gives an excellent overview) has become one of the central issues during the last decade. Although there are now several branches within this area, there is a certain agreement that Dung’s famous abstract argumentation frameworks (AFs) [7] still represent the core formalism for many of the problems and applications in the field. In a nutshell, AFs formalize statements together with a relation denoting rebuttals between them, such that the semantics gives a handle to solve the inherent conflicts between statements by selecting admissible subsets of them, but without taking the concrete contents of the statements into account. Several semantical principles how to select those subsets have already been proposed by Dung [7] but numerous other proposals have been made over the last years. In this paper we shall focus on the preferred [7], semi-stable [4], stage [18], and the resolution-based grounded semantics [1]. Each of these semantics is based on some kind of $\subseteq$-maximality (resp. -minimality) and thus is well amenable for the novel metasp concepts which we describe below.

Let us first talk about the general context of the paper, which is the realization of abstract argumentation within the paradigm of Answer-Set Programming (see [17] for an overview ). We follow here the ASPARTIX¹approach [11], where a single program is used to encode a particular argumentation semantics, while the instance of an argumentation framework is given as an input database. For problems located on the second level of the polynomial hierarchy (i.e. for preferred, stage, and semi-stable semantics) ASP encodings turned out to be quite complicated and hardly accessible for non-experts in ASP (we will sketch here the encoding for the stage semantics in some detail, since it has not been presented in [11]). This is due to the fact that tests for subset-maximality have to be done “by hand” in ASP requiring a certain saturation technique. However, recent advances in ASP solvers, in particular, the metasp optimization front-end for the ASP-system gringo/claspD allows for much simpler encodings for such tests. More precisely, metasp allows to use the traditional $\# minimize$ statement (which in its standard variant minimizes wrt. cardinality or weights, but not wrt. subset inclusion) also for selection among answer sets which are minimal wrt. subset inclusion in certain predicates. Details about metasp can be found in [13].

Our first main contribution will be the practical comparison between handcrafted encodings (i.e. encodings in the standard ASP language without the new semantics for the $\# minimize$ statement) and the much simpler metasp encodings for argumentation semantics. The experiments show that the metasp encodings do not necessarily result in longer runtimes. In fact, the metasp encodings for the semantics located on the second level of the polynomial hierarchy outperform the handcrafted saturation-based encodings. We thus can give additional evidence to the observations in [13], where such a speed-up was reported for encodings in a completely different application area.

Our second contribution is the presentation of ASP encodings for the resolution-based grounded semantics  [1]. To the best of our knowledge, no implementation for this recently proposed semantics has been released so far. In this paper, we present a rather involved handcrafted encoding (basically following the $\text{ NP }$-algorithm presented in [1]) but also two much simpler encodings (using metasp) which rely on the original definition of the semantics.

Our results indicate that metasp is a very useful tool for problems known to be hard for the second-level, but one might loose performance in case metasp is used for “easier” problems just for the sake of comfortability. Nonetheless, we believe that the concept of the advanced $\# minimize$ statement is vital for ASP, since it allows for rapid prototyping of second-level encodings without being an ASP guru.

The remainder of the paper is organized as follows: Section 2 provides the necessary background. Section 3 then contains the ASP encodings for the argumentation semantics we are interested in this work. We begin with the handcrafted saturation-based encoding for stage semantics. Then, in Sect. 3.2 we provide the novel metasp encodings for all considered semantics and afterwards, in Sect. 3.3, we present an alternative encoding for the resolution-based grounded semantics which better mirrors the complexity of this semantics. Section 4 then presents our experimental evaluation. We conclude the paper with a brief summary and discussion for future research directions.

2 Background

2.1 Abstract Argumentation

In this section we introduce (abstract) argumentation frameworks [7] and recall the semantics we study in this paper (see also [1, 2]). Moreover, we highlight complexity results for typical decision problems associated to such frameworks.

Definition 1.

An argumentation framework (AF) is a pair $F=(A,R)$ where $A$ is a set of arguments and $R \subseteq A \times A$ is the attack relation. The pair $(a,b) \in R$ means that $a$ attacks $b$.An argument $a \in A$ is defended by a set $S \subseteq A$ if, for each $b \in A$ such that $(b,a) \in R$, there exists a $c \in S$ such that $(c,b) \in R$.

Example 1.

Consider the AF $F=(A,R)$ with $A=\{a,b,c,d,e,f\}$ and $R=\{(a,b)$, $(b,d)$, $(c,b)$, $(c,d)$, $(c,e)$, $(d,c)$, $(d,e)$, $(e,f)\}$, and the graph representation of $F$:

Semantics for argumentation frameworks are given via a function $\sigma$ which assigns to each AF $F=(A,R)$ a set $\sigma (F)\subseteq 2^A$ of extensions. We shall consider here for $\sigma$ the functions ${ stb }$, $adm$, $com$, $prf$, $grd$, $grd^*$, $stg$, and $sem$ which stand for stable, admissible, complete, preferred, grounded, resolution-based grounded, stage, and semi-stable semantics respectively. Towards the definition of these semantics we have to introduce two more formal concepts.

Definition 2.

Given an AF $F=(A,R)$. The characteristic function $\mathcal {F}_F: 2^A \Rightarrow 2^A$ of $F$ is defined as $\mathcal {F}_F(S) = \{x \in A \mid x \text{ is } \text{ defended } \text{ by } S\}$. Moreover, for a set $S\subseteq A$, we denote the set of arguments attacked by $S$ as $S^\oplus _R= \{ x\mid \exists y\in S \text { such that } (y,x) \in R\}$, and define the range of $S$ as $S^+_R=S\cup S^\oplus _R$.

Definition 3.

Let $F=(A,R)$ be an AF. A set $S\subseteq A$ is conflict-free (in $F$), if there are no $a, b \in S$, such that $(a,b) \in R$. $cf (F)$ denotes the collection of conflict-free sets of $F$. For a conflict-free set $S \in cf (F)$, it holds that

• $S\in { stb }(F)$, if $S^+_R = A$;

• $S\in adm (F)$, if $S \subseteq \mathcal {F}_F(S)$;

• $S\in com (F)$, if $S=\mathcal {F}_F(S)$;

• $S\in grd (F)$, if $S\in com (F)$ and there is no $T\in com (F)$ with $T\subset S$;

• $S\in prf (F)$, if $S\in adm (F)$ and there is no $T\in adm (F)$ with $T\supset S$;

• $S\in sem (F)$, if $S\in adm (F)$ and there is no $T\in adm (F)$ with $T^+_R\supset S^+_R$;

• $S\in stg (F)$, if there is no $T\in cf (F)$ in $F$, such that $T^+_R\supset S^+_R$.

We recall that for each AF $F$, the grounded semantics yields a unique extension, the grounded extension, which is the least fixed point of the characteristic function $\mathcal {F}_F$.

Example 2.

Consider the AF $F$ from Example 1. We have $\{a,d,f\}$ and $\{a,c,f\}$ as the stable extensions and thus ${ stb }(F)= stg (F)= sem (F)=\{\{a,d,f\},\{a,c,f\}\}$. The admissible sets of $F$ are $\{\}, \{a\}, \{c\}, \{a,c\}, \{a,d\}, \{c,f\}, \{a,c,f\}, \{a,d,f\}$ and therefore $prf (F)=\{\{a,c,f\},\{a,d,f\}\}$. Finally we have $com (F)=\{\{a\}, \{a,c,f\}, \{a,d,f\}\}$, with $\{a\}$ being the grounded extension.

On the base of these semantics one can define the family of resolution-based semantics [1], with the resolution-based grounded semantics being the most popular instance.

Definition 4.

A resolution $\beta \subset R$ of an AF $F=(A,R)$ contains exactly one attack from each bidirectional attack in $F$, i.e. $\forall a,b \in A$, if $(a,b),(b,a) \in R$ then $\mid \{(a,b),(b,a)\} \; \cap \; \beta \mid \; = 1$ and $\{(c,d) \mid (c,d) \in R, (d,c) \not \in R\} \cap \beta = \emptyset$. A set $S\subseteq A$ is a resolution-based grounded extension of $F$, denoted by S $\in grd^* (F)$, if (i) there exists a resolution $\beta$ such that $S= grd ((A,R \setminus \beta ))$ ²; and (ii) there is no resolution $\beta '$ such that $grd ((A,R \setminus \beta ')) \subset S$.

Example 3.

Recall the AF $F=(A,F)$ from Example 1. There is one mutual attack and thus we have two resolutions $\beta _1=\{(c,d)\}$ and $\beta _2=\{(d,c)\}$. Definition 4 gives us two candidates, namely $grd ((A,R \setminus \beta _1))= \{a,d,f\}$ and $grd ((A,R \setminus \beta _2))= \{a,c,f\}$; as they are not in $\subset$-relation they are the resolution-based grounded extensions of $F$.

We now turn to the complexity of reasoning in AFs. To this end, we define the following decision problems for the semantics $\sigma$ introduced in Definitions 3 and 4:

• Credulous Acceptance $\mathsf{Cred_{\sigma }}$: Given AF $F=(A,R)$ and an argument $a\in A$. Is $a$ contained in some $S\in \sigma (F)$?

• Skeptical Acceptance $\mathsf{Skept_{\sigma }}$: Given AF $F=(A,R)$ and an argument $a\in A$. Is $a$ contained in each $S\in \sigma (F)$?

• Verification of an extension $\mathsf{Ver_{\sigma }}$: Given AF $F=(A,R)$ and a set of arguments $S \subseteq A$. Is $S\in \sigma (F)$?

We assume the reader has knowledge about standard complexity classes like $\mathrm{P}$ and $\text{ NP }$ and recall that $\mathrm{\Sigma }_{2}^{P}$ is the class of decision problems that can be decided in polynomial time using a nondeterministic Turing machine with access to an $\text{ NP }$-oracle. The class $\mathrm{\Pi }_{2}^{P}$ is defined as the complementary class of $\mathrm{\Sigma }_{2}^{P}$, i.e. $\mathrm{\Pi }_{2}^{P}=\text{ co }\mathrm{\Sigma }_{2}^{P}$.

In Table 1 we summarize complexity results relevant for our work [1, 6, 8–10].

Table 1. Complexity of abstract argumentation ($\mathcal{C}$-c denotes completeness for class $\mathcal{C}$)

2.2 Answer-Set Programming

We give a brief overview of the syntax and semantics of disjunctive logic programs under the answer-sets semantics [15]; for further background, see [16].

We fix a countable set $\mathcal{U}$ of (domain) elements, also called constants; and suppose a total order $<$ over the domain elements. An atom is an expression $p(t_{1},\ldots ,t_{n})$, where $p$ is a predicate of arity $n\ge 0$ and each $t_{i}$ is either a variable or an element from $\mathcal{U}$. An atom is ground if it is free of variables. ${B_\mathcal{U}}$ denotes the set of all ground atoms over $\mathcal{U}$.

A (disjunctive)rule $r$ with $n\ge 0,$ $m\ge k\ge 0$, $n+m > 0$ is of the form

$$\begin{aligned} a_1\ \vee \ \cdots \ \vee \ a_n\ \leftarrow b_1,\ldots , b_k,\ { not}\,b_{k+1},\ldots ,\ { not}\,b_m \end{aligned}$$

where $a_1,\ldots ,a_n,b_1,\ldots ,b_m$ are atoms, and “${ not}\,$” stands for default negation. An atom $a$ is a positive literal, while ${ not}\,a$ is a default negated literal. The head of $r$ is the set $H(r)$ = $\{a_1,\ldots ,a_n\}$ and the body of $r$ is $B(r)=B^+(r) \cup B^-(r)$ with $B^+(r)$ = $\{b_{1},\ldots ,b_{k}\}$ and $B^-(r)$ = $\{b_{k+1},\ldots ,b_m\}$. A rule $r$ is normal if $n \le 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 with an empty body. An (input) database is a set of facts. A program is a finite set of disjunctive rules. For a program ${\pi }$ and an input database $D$, we often write ${\pi }{(D)}$ instead of $D\cup {\pi }$. If each rule in a program is normal (resp. ground), we call the program normal (resp. ground). Besides disjunctive and normal program, we consider here the class of optimization programs, i.e. normal programs which additionally contain $\# minimize$ statements

$$\begin{aligned} \# minimize [l_1=w_1@J_1,\dots ,l_k=w_k@J_k] \end{aligned}$$

(1)

where $l_i$ is a literal, $w_i$ an integer weight and $J_i$ an integer priority level.

For any program ${\pi }$, let $U_{{\pi }}$ be the set of all constants appearing in ${\pi }$. $Gr({\pi })$ is the set of rules $r\tau$ obtained by applying, to each rule $r\in {\pi }{}$, all possible substitutions $\tau$ from the variables in $r$ to elements of $U_{{\pi }}{}$. An interpretation $I\subseteq {B_\mathcal{U}}$ satisfies a ground rule $r$ iff $H(r) \cap I \ne \emptyset$ whenever $B^+(r)\subseteq I$ and $B^-(r) \cap I = \emptyset$. $I$ satisfies a ground program ${\pi }$, if each $r\in {\pi }$ is satisfied by $I$. A non-ground rule $r$ (resp., a program ${\pi }$) is satisfied by an interpretation $I$ iff $I$ satisfies all groundings of $r$ (resp., $Gr({\pi })$). $I \subseteq {B_\mathcal{U}}$ is an answer set of ${\pi }$ iff it is a subset-minimal set satisfying the Gelfond-Lifschitz reduct ${\pi }^I=\{ H(r) \leftarrow B^+(r) \mid I\cap B^-(r) = \emptyset , r \in Gr({\pi })\}$. For a program ${\pi }$, we denote the set of its answer sets by ${\mathcal {AS}}({\pi })$.

For semantics of optimization programs, we interpret the $\# minimize$ statement wrt. subset-inclusion: For any sets $X$ and $Y$ of atoms, we have $Y\subseteq ^w_J X$, if for any weighted literal $l=w@J$ occurring in (1), $Y\models l$ implies $X\models l$. Then, $M$ is a collection of relations of the form $\subseteq ^w_J$ for priority levels $J$ and weights $w$. A standard answer set (i.e. not taking the minimize statements into account) $Y$ of ${\pi }$ dominates a standard answer set $X$ of ${\pi }$ wrt. $M$ if there are a priority level $J$ and a weight $w$ such that $X\subseteq ^w_J Y$ does not hold for $\subseteq ^w_J\in M$, while $Y\subseteq ^{w'}_{J'} X$ holds for all $\subseteq ^{w'}_{J'}\in M$ where $J'\ge J$. Finally a standard answer set $X$ is an answer set of an optimization program ${\pi }$ wrt. $M$ if there is no standard answer set $Y$ of ${\pi }$ that dominates $X$ wrt. $M$.

Credulous and skeptical reasoning in terms of programs is defined as follows. Given a program ${\pi }$ and a set of ground atoms $A$. Then, we write ${\pi }\models _c A$ (credulous reasoning), if $A$ is contained in some answer set of ${\pi }$; we write ${\pi }\models _s A$ (skeptical reasoning), if $A$ is contained in each answer set of ${\pi }$.

We briefly recall some complexity results for disjunctive logic programs. In fact, since we will deal with fixed programs we focus on results for data complexity. Depending on the concrete definition of $\models$, we give the complexity results in Table 2 (cf. [5] and the references therein). We note here, that even normal programs together with the optimization technique have a worst case complexity of $\mathrm{\Sigma }_{2}^{P}$ (resp. $\mathrm{\Pi }_{2}^{P}$). Inspecting Table 1 one can see which kind of encoding is appropriate for an argumentation semantics.

Table 2. Data Complexity for logic programs (all results are completeness results).

3 Encodings of AF Semantics

In this section we first show how to represent AFs in ASP and we discuss three programs which we need later on in this section.³ Then, in Subsect. 3.1 we exemplify on the stage semantics the saturation technique for encodings that solve associated problems which are on the second level of the polynomial hierarchy. In Subsect. 3.2 we will make use of the newly developed metasp optimization technique. In Subsect. 3.3 we give an alternative encoding based on the algorithm by Baroni et al. in [1], which respects the lower complexity of resolution-based grounded semantics.

All our programs are fixed which means that the only translation required, is to give an AF $F$ as input database $\hat{F}$ to the program $\pi _{\sigma }$ for a semantics $\sigma$. In fact, for an AF $F=(A,R)$, we define $\hat{F}$ as

$$\begin{aligned} \hat{F} = \{ \; \arg (a) \mid a\in A\} \cup \{{\mathrm {defeat}}(a,b)\mid (a,b)\in R \; \}. \end{aligned}$$

In what follows, we use unary predicates ${\mathrm {in}}/1$ and ${\mathrm {out}}/1$ to perform a guess for a set $S\subseteq A$, where ${\mathrm {in}}(a)$ represents that $a\in S$. The following notion of correspondence is relevant for our purposes.

Definition 5.

Let $\mathcal {S}\subseteq$ $2^\mathcal{U}$ be a collection of sets of domain elements and let $\mathcal{I}\subseteq 2^{B_\mathcal{U}}$ be a collection of sets of ground atoms. We say that $\mathcal {S}$ and $\mathcal{I}$ correspond to each other, in symbols $\mathcal {S}\cong \mathcal{I}$, iff (i) for each $S\in \mathcal {S}$, there exists an $I\in \mathcal{I}$, such that $\{ a \mid {\mathrm {in}}(a)\in I\} = S$; (ii) for each $I\in \mathcal{I}$, it holds that $\{ a \mid {\mathrm {in}}(a)\in I\}\in \mathcal {S}$; and (iii) $|\mathcal {S}| = |\mathcal{I}|$.

Consider an AF $F$. The following program fragment guesses, when augmented by $\hat{F}$, any subset $S\subseteq A$ and then checks whether the guess is conflict-free in $F$:

$$\begin{aligned} \pi _{ cf } = \{&{\mathrm {in}}(X) \leftarrow { not}\,{\mathrm {out}}(X), \arg (X);\; \\&{\mathrm {out}}(X) \leftarrow { not}\,{\mathrm {in}}(X), \arg (X);\;\\&\leftarrow {\mathrm {in}}(X), {\mathrm {in}}(Y), {\mathrm {defeat}}(X,Y) \; \,\,\}. \end{aligned}$$

Proposition 1.

For any AF $F$, $cf (F)\cong {\mathcal {AS}}(\pi _{ cf }(\hat{F})).$

Sometimes we have to avoid the use of negation. This might either be the case for the saturation technique or if a simple program can be solved without a Guess&Check approach. Then, encodings typically rely on a form of loops where all domain elements are visited and it is checked whether a desired property holds for all elements visited so far. We will use this technique in our saturation-based encoding in the upcoming subsection, but also for computing the grounded extension in Subsect. 3.2. For this purpose, an order $<$ over the domain elements (usually provided by common ASP solvers) is used together with a few helper predicates defined in the program $\pi _{<}$ below; in fact, predicates $\inf /1, {\mathrm {succ}}/2$ and $\sup /1$ denote infimum, successor and supremum of the order $<$.

$$\begin{aligned} \pi _{<} = \{&\mathrm{{lt}} (X,Y) \leftarrow \arg (X),\arg (Y),X<Y; \\&{\mathrm {nsucc}}(X,Z) \leftarrow \mathrm{{lt}} (X,Y),\mathrm{{lt}} (Y,Z); \\&{\mathrm {succ}}(X,Y) \leftarrow \mathrm{{lt}} (X,Y),{ not}\,{\mathrm {nsucc}}(X,Y); \\&{\mathrm {ninf}}(Y) \leftarrow \mathrm{{lt}} (X,Y);\\&\inf (X) \leftarrow \arg (X), { not}\,{\mathrm {ninf}}(X);\\&{\mathrm {nsup}}(X) \leftarrow \mathrm{{lt}} (X,Y); \\&\sup (X)\leftarrow \arg (X), { not}\,{\mathrm {nsup}}(X) \; \}. \end{aligned}$$

Finally, the following module computes for a guessed subset $S \subseteq A$ the range $S^+_R$ (see Def. 2) of $S$ in an AF $F=(A,R)$.

$$\begin{aligned} \pi _{ range } = \{&{\mathrm {in\_range}}(X) \leftarrow {\mathrm {in}}(X); \\&{\mathrm {in\_range}}(X) \leftarrow {\mathrm {in}}(Y), {\mathrm {defeat}}(Y,X);\\&{\mathrm {not\_in\_range}}(X) \leftarrow \arg (X), { not}\,{\mathrm {in\_range}}(X) \;\, \}. \end{aligned}$$

3.1 Saturation Encodings

In this subsection we make use of the saturation technique introduced by Eiter and Gottlob in [12]. In [11], this technique was already used to encode the preferred and semi-stable semantics. Here we give the encodings for the stage semantics, which is similar to the one of semi-stable semantics, to exemplify the use of the saturation technique.

In fact, for an AF $F=(A,R)$ and $S\in cf (F)$ we need to check whether no $T\in cf (F)$ with $S^+_R\subset T^+_R$ exists. Therefore we have to guess an arbitrary set $T$ and saturate in case (i) $T$ is not conflict-free, or (ii) $S^+_R\not \subset T^+_R$. Together with $\pi _{ cf }$ this is done with the following module, where ${\mathrm {in}}/1$ holds the current guess for $S$ and ${\mathrm {inN}}/1$ holds the current guess for $T$. More specifically, rule ${\mathrm {fail}}\leftarrow {\mathrm {inN}}(X),{\mathrm {inN}}(Y),{\mathrm {defeat}}(X,Y)$ checks for (i) and the remaining two rules with ${\mathrm {fail}}$ in the head fire in case $S^+_R= T^+_R$ (indicated by predicate ${\mathrm {eqplus}}/0$ described below), or there exists an $a\in S^+_R$ such that $a\notin T^+_R$ (here we use predicate ${\mathrm {in\_range}}/1$ from above and predicate ${\mathrm {not\_in\_rangeN}}/1$ which we also present below). As is easily checked one of these two conditions holds exactly if (ii) holds.

$$\begin{aligned} \pi _{{ satstage }} = \{&{\mathrm {inN}}(X) \vee {\mathrm {outN}}(X) \leftarrow \arg (X); \\&{\mathrm {fail}}\leftarrow {\mathrm {inN}}(X),{\mathrm {inN}}(Y),{\mathrm {defeat}}(X,Y);\\&{\mathrm {fail}}\leftarrow {\mathrm {eqplus}};\\&{\mathrm {fail}}\leftarrow {\mathrm {in\_range}}(X), {\mathrm {not\_in\_rangeN}}(X);\\&{\mathrm {inN}}(X) \leftarrow {\mathrm {fail}}, \arg (X); \\&{\mathrm {outN}}(X) \leftarrow {\mathrm {fail}}, \arg (X);\\&\leftarrow { not}\,{\mathrm {fail}}\; \}. \end{aligned}$$

For the definition of predicates ${\mathrm {not\_in\_rangeN}}/1$ and ${\mathrm {eqplus}}/0$ we make use of the aforementioned loop technique and predicates from program $\pi _{<}$.

Proposition 2.

For any AF $F$, $stg (F)\cong {\mathcal {AS}}(\pi _{ stg }(\hat{F}))$, where $\pi _{ stg } = \pi _{ cf } \cup \pi _{<} \cup \pi _{ range } \cup \pi _{{ rangeN }} \cup \pi _{{ eq }^+} \cup \pi _{{ satstage }}$.

3.2 Meta ASP Encodings

The following encodings for preferred, semi-stable and stage semantics are written using the $\# minimize$ statement when evaluated with the subset-minimization semantics provided by metasp. For our encodings we do not need prioritization and weights, therefore these are omitted (i.e. set to default) in the minimization statements. The minimization technique is realized through meta programming techniques, which themselves are answer-set programs. This works as follows: The ASP encoding to solve is given to the grounder gringo which reifies the program, i.e. outputs a ground program consisting of facts, which represent the rules and facts of the original input encoding. The grounder is then again executed on this output with the meta programs which encode the optimization. Finally, claspD computes the answer sets. Note that here we use the version of clasp which supports disjunctive rules. Therefore for a program $\pi$ and an AF $F$ we have the following execution.

Here, meta.lp, metaO.lp and metaD.lp are the encodings for the minimization statement. The statement optimize(incl,1,1) indicates that we use subset inclusion for the optimization technique using priority and weight $1$.

We now look at the encodings for the preferred, semi-stable and stage semantics using this minimization technique. First, we need one auxiliary module for admissible extensions.

$$\begin{aligned} \pi _{ adm } = \pi _{ cf }\cup \{&{\mathrm {defeated}}(X) \leftarrow {\mathrm {in}}(Y), {\mathrm {defeat}}(Y,X);\; \\&\leftarrow {\mathrm {in}}(X), {\mathrm {defeat}}(Y,X), { not}\,{\mathrm {defeated}}(Y) \}. \end{aligned}$$

Now the modules for preferred, semi-stable and stage semantics are easy to encode using the minimization statement of metasp. For the preferred semantics we take the module $\pi _{ adm }$ and minimize the ${\mathrm {out}}/1$ predicate. This in turn gives us the subset-maximal admissible extensions which captures the definition of preferred semantics. The encodings for the semi-stable and stage semantics are similar. Here we minimize the predicate ${\mathrm {not\_in\_range}}/1$ from the $\pi _{ range }$ module.

$$\begin{aligned} \pi _{{ prf \_metasp }}&= \pi _{ adm } \cup \{ \# minimize [{\mathrm {out}}]\}. \\ \pi _{{ sem \_metasp }}&= \pi _{ adm } \cup \pi _{ range } \cup \{ \# minimize [{\mathrm {not\_in\_range}}] \}. \\ \pi _{{ stg \_metasp }}&= \pi _{ cf } \cup \pi _{ range } \cup \{ \# minimize [{\mathrm {not\_in\_range}}] \}. \end{aligned}$$

The following results follow now directly.

Proposition 3.

For any AF $F$, we have

• 1. $prf (F)\cong {\mathcal {AS}}(\pi _{{ prf \_metasp }}(\hat{F}))$,

• 2. $sem (F)\cong {\mathcal {AS}}(\pi _{{ sem \_metasp }}(\hat{F}))$, and

• 3. $stg (F)\cong {\mathcal {AS}}(\pi _{{ stg \_metasp }}(\hat{F}))$.

Next we give two different encodings for computing resolution-based grounded extensions. Both encodings use subset-minimization for the resolution part, i.e. the resulting extension is subset-minimal with respect to all possible resolutions. The difference between the two encodings is that the first one computes the grounded extension for the guessed resolution explicitly (making use of looping concepts presented already in [11]). The second encoding uses the metasp subset-minimization also to get the grounded extension from the complete extensions of the current resolution (recall that the grounded extension is in fact the unique subset-minimal complete extension).The module $\pi _{ grd }$ below for computing the grounded extension is taken from [11] with a small modification: instead of the ${\mathrm {defeat}}$ predicate we use ${\mathrm {defeat\_minus\_beta}}$, since we need the grounded extensions of a restricted ${\mathrm {defeat}}$ relation. In fact, the $\pi _{{ res }}$ module guesses this restricted ${\mathrm {defeat}}$ relation $\{R \setminus \beta \}$ for a resolution $\beta$.

$$\begin{aligned} \pi _{{ res }} = \{&{\mathrm {defeat\_minus\_beta}}(X,Y) \leftarrow {\mathrm {defeat}}(X,Y), { not}\,{\mathrm {defeat\_minus\_beta}}(Y,X),\\&\qquad \qquad \qquad \qquad \qquad \qquad X \not = Y;\\&{\mathrm {defeat\_minus\_beta}}(X,Y) \leftarrow {\mathrm {defeat}}(X,Y), { not}\,{\mathrm {defeat}}(Y,X); \\&{\mathrm {defeat\_minus\_beta}}(X,X) \leftarrow {\mathrm {defeat}}(X,X)\,\, \}. \end{aligned}$$

We repeat the definition of $\pi _{ grd }$ here, which includes the module $\pi _{ defended }$.

Now we can give the first encoding for resolution-based grounded semantics.

$$\begin{aligned} \pi _{{ grd^* \_metasp }} = \pi _{ grd } \cup \pi _{{ res }} \cup \{ \# minimize [{\mathrm {in}}]\}. \end{aligned}$$

The second encoding for resolution-based grounded semantics performs the metasp subset-minimization from the complete extensions of the current resolution to compute the grounded extension. We again use the restricted ${\mathrm {defeat}}$ relation.

$$\begin{aligned} \pi _{ com } = \pi _{ adm } \cup \{&{\mathrm {undefended}}(X) \leftarrow {\mathrm {defeat\_minus\_beta}}(Y,X), { not}\,{\mathrm {defeated}}(Y);\\&\leftarrow {\mathrm {out}}(X), { not}\,{\mathrm {undefended}}(X) \; \}. \end{aligned}$$

We obtain the following metasp encoding:

$$\begin{aligned} \pi _{{ grd^* \_metasp }'} = \pi _{ com } \cup \pi _{{ res }} \cup \{ \# minimize [{\mathrm {in}}] \}. \end{aligned}$$

Proposition 4.

For any AF $F$ and $\pi \in \{\pi _{{ grd^* \_metasp }},\pi '_{{ grd^* \_metasp }}\}, grd ^*(F)$ corresponds to ${\mathcal {AS}}(\pi (\hat{F}))$ in the sense of Definition 5, but without property (iii).

As the proposition suggests there is a caveat for these two encodings of the resolution-based grounded semantics. In general we have that several answer sets map to the same extension, i.e. there is no one-to-one correspondence between answer sets and extensions. The reason for this behavior lies in the guessing of a resolution. Whereas the other encodings guess basically the ${\mathrm {in}}/1$ predicate, these two metasp encodings guess the resolution. Therefore the result might include the same extension with different resolutions guessed. While this does not harm credulous or skeptical reasoning, some measures have to be taken to remove these duplicates when enumerating or counting extensions. The solver clasp already features such a technique which is presented in [14]. This feature is not yet implemented in claspD. Furthermore the meta encodings for metasp use disjunctive ASP, which increases the computational complexity to the second level of the polynomial hierarchy, whereas the problem of resolution based grounded semantics is situated on the first level.

3.3 Alternative Encodings for Resolution-based Grounded Semantics

So far, we have shown two encodings for the resolution-based grounded semantics via optimization programs, i.e. we made use of the $\# minimize$ statement under the subset-inclusion semantics. From the complexity point of view this is not adequate, since we expressed a problem on the $\text{ NP }$-layer (see Table 1) via an encoding which implicitly makes use of disjunction (see Table 2 for the actual complexity of optimization programs). Hence, we provide here an alternative encoding for the resolution-based grounded semantics based on the verification algorithm proposed by Baroni et al. in [1]. This encoding is just a normal program and thus located at the right level of complexity.

We need some further notation. For an AF $F=(A,R)$ and a set $S\subseteq A$ we define $F|_{S}=((A\cap S),R\cap (S\times S))$ as the sub-framework of $F$ wrt. $S$; furthermore we also use $F-S$ as a shorthand for $F|_{A\setminus S}$. By ${ SCCs(F) }$, we denote the set of strongly connected components of an AF $F=(A,R)$ which identify the vertices of a maximal strongly connected⁴ subgraph of $F$; ${ SCCs(F) }$ is thus a partition of $A$. A partial order $\prec _F$ over ${ SCCs(F) }=\{C_1,\dots ,C_n\}$, denoted as $(C_i\prec _F C_j)$ for $i\ne j$, is defined, if $\exists x\in C_i, y\in C_j$ such that there is a directed path from $x$ to $y$ in $F$.

Definition 6.

A $C\in { SCCs(F) }$ is minimal relevant (in an AF $F$) iff $C$ is a minimal element of $\prec _F$ and $F|_C$ satisfies the following:

• (a) the attack relation $R(F|_C)$ of $F$ is irreflexive, i.e. $(x,x)\not \in R(F|_C)$ for all arguments $x$;

• (b) $R(F|_C)$ is symmetric, i.e. $(x,y)\in R(F|_C) \Leftrightarrow (y,x)\in R(F|_C)$;

• (c) the undirected graph obtained by replacing each (directed) pair $\{(x,y),(y,x)\}$ in $F|_C$ with a single undirected edge $\{x,y\}$ is acyclic.

The set of minimal relevant SCCs in $F$ is denoted by ${ MR }(F)$.

Proposition 5.

([1]). Given an AF $F=(A,R)$ such that $(F-S^+_R)\ne (\emptyset , \emptyset )$ and ${ MR }(F-S^+_R)\ne \emptyset$, where $S = grd (F)$, a set $U\subseteq A$ of arguments is resolution-based grounded in $F$, i.e. $U\in grd^* (F)$ iff the following conditions hold:

• (i) $U\cap S^+_R =S$;

• (ii) $(T\cap \varPi _F) \in { stb }(F|_{\varPi _F})$, where $T=U\setminus S^+_R$, and $\varPi _F=\bigcup _{V\in { MR }(F-S^+_R)}V$;

• (iii) $(T\cap \varPi _F^C)\in grd^* (F|_{\varPi _F^C} -(S^+_R \cup (T\cap \varPi _F)^\oplus _R))$, where $T$ and $\varPi _F$ are as in (ii) and $\varPi _F^C = A\setminus \varPi _F$.

To illustrate the conditions of Proposition 5, let us have a look at our example.

Example 4.

Consider the AF $F$ of Example 1. Let us check whether $U\!=\{a,d,f\}$ is resolution-based grounded in $F$, i.e. whether $U\in grd^* (F)$. $S=\{a\}$ is the grounded extension of $F$ and $S^+_R=\{a,b\}$, hence the Condition (i) is satisfied. We obtain $T=\{d,f\}$ and $\varPi _F=\{c,d\}$. We observe that $T\cap \varPi _F=\{d\}$ is a stable extension of the AF $F|_{\varPi _F}$; that satisfies Condition (ii). Now we need to check Condition (iii); we first identify the necessary sets: $\varPi _F^C=\{a,b,e,f\}$, $T\cap \varPi _F^C=\{f\}$ and $(T\cap \varPi _F)^\oplus _R=\{c,e\}$. It remains to check $\{f\}\in grd^* (\{f\},\emptyset )$ which is easy to see. Hence, $U\in grd^* (F)$.

The following encoding is based on the Guess&Check procedure which was also used for the encodings in [11]. After guessing all conflict-free sets with the program $\pi _{ cf }$, we check whether the conditions of Definition 6 and Proposition 5 hold. Therefore the program $\pi _{{ arg\_set }}$ makes a copy of the actual arguments, defeats and the guessed set to the predicates ${\mathrm {arg\_set}}/2, {\mathrm {defeatN}}/3$ and ${\mathrm {inU}}/2$. The first variable in these three predicates serves as an identifier for the iteration of the algorithm (this is necessary to handle the recursive nature of Proposition 5). In all following predicates we will use the first variable of each predicate like this. As in some previous encodings in this paper, we use the program $\pi _{<}$ to obtain an order over the arguments, and we start our computation with the infimum represented by the predicate $\inf /1$.

$$\begin{aligned} \pi _{{ arg\_set }} =\{&{\mathrm {arg\_set}}(N,X) \leftarrow \arg (X), \inf (N);\\&{\mathrm {inU}}(N,X) \leftarrow {\mathrm {in}}(X), \inf (N);\\&{\mathrm {defeatN}}(N,Y,X) \leftarrow {\mathrm {arg\_set}}(N,X), {\mathrm {arg\_set}}(N,Y), {\mathrm {defeat}}(Y,X)\;\, \}. \end{aligned}$$

We use here the program $\pi _{{ defendedN }}$ (which is a slight variant of the program $\pi _{ defended }$) together with the program $\pi _{{ groundN }}$ where we perform a fixed-point computation of the predicate ${\mathrm {defendedN}}/2$, as in the definition of the characteristic function $\mathcal {F}_F$ in Definition 2. The basic difference here is that now, we use an additional argument $N$ for the iteration step where predicates ${\mathrm {arg\_set}}/2$, ${\mathrm {defeatN}}/3$ and ${\mathrm {inS}}/2$ replace $\arg /1$, ${\mathrm {defeat}}/2$ and ${\mathrm {in}}/1$.

In $\pi _{{ groundN }}$ we then obtain the predicate ${\mathrm {inS}}(N,X)$ which identifies argument $X$ to be in the grounded extension of the iteration $N$.

$$\begin{aligned} \pi _{{ groundN }} = \pi _{ cf } \cup \pi _{<} \cup \pi _{{ arg\_set }} \cup \pi _{{ defendedN }} \cup \{\,\,{\mathrm {inS}}(N,X) \leftarrow {\mathrm {defendedN}}(N,X)\; \}. \end{aligned}$$

The next module $\pi _{{ F\_minus\_range }}$ computes the arguments in $(F-S^+_R)$, represented by the predicate ${\mathrm {notInSplusN}}/2$, via predicates ${\mathrm {in\_SplusN}}/2$ and ${\mathrm {u\_cap\_Splus}}/2$ (for $S^+_R$ and $U\cap S^+_R$). The two constraints check condition (i) of Proposition 5.

$$\begin{aligned} \pi _{{ F\_minus\_range }} =\{&{\mathrm {in\_SplusN}}(N,X) \leftarrow {\mathrm {inS}}(N,X); \\&{\mathrm {in\_SplusN}}(N,X) \leftarrow {\mathrm {inS}}(N,Y), {\mathrm {defeatN}}(N,Y,X); \\&{\mathrm {u\_cap\_Splus}}(N,X) \leftarrow {\mathrm {inU}}(N,X), {\mathrm {in\_SplusN}}(N,X); \\&\leftarrow {\mathrm {u\_cap\_Splus}}(N,X), { not}\,{\mathrm {inS}}(N,X); \\&\leftarrow { not}\,{\mathrm {u\_cap\_Splus}}(N,X), {\mathrm {inS}}(N,X); \\&{\mathrm {notInSplusN}}(N,X) \leftarrow {\mathrm {arg\_set}}(N,X), { not}\,{\mathrm {in\_SplusN}}(N,X) \;\, \}. \end{aligned}$$

The module $\pi _{{ MR }}$ computes $\Pi _F=\bigcup _{V\in { MR }(F-S^+_R)}V$, where ${\mathrm {mr}}(N,X)$ denotes that an argument is contained in a set $V\in { MR }$. Therefore we need to check all three conditions of Definition 6. The first two rules compute the predicate ${\mathrm {reach}}(N,X,Y)$ if there is a path between the arguments $X,Y\in (F-S^+_R)$. With this predicate we will identify the SCCs. The third rule computes ${\mathrm {self\_defeat}}/2$ for all arguments violating Condition (a). Next we need to check Condition (b). With ${\mathrm {nsym}}/2$ we obtain those arguments which do not have a symmetric attack to any other argument from the same component. Condition (c) is a bit more tricky. With predicate ${\mathrm {reachnotvia}}/4$ we say that there is a path from $X$ to $Y$ not going over argument $V$ in the framework $(F-S^+_R)$. With this predicate at hand we can check for cycles with ${\mathrm {cyc}}/4$. Then, to complete Condition (c) we derive ${\mathrm {bad}}/2$ for all arguments which are connected to a cycle (or a self-defeating argument). In the predicate ${\mathrm {pos\_mr}}/2$, we put all the three conditions together and say that an argument $x$ is possibly in a set $V\in { MR }$ if (i) $x\in (F-S^+_R)$, (ii) $x$ is neither connected to a cycle nor self-defeating, and (iii) for all $y$ it holds that $(x,y)\in (F-S^+_R)\Leftrightarrow (y,x)\in (F-S^+_R)$. Finally we only need to check if the SCC obtained with ${\mathrm {pos\_mr}}/2$ is a minimal element of $\prec _F$. Hence we get with ${\mathrm {notminimal}}/2$ all arguments not fulfilling this, and in the last rule we obtain with ${\mathrm {mr}}/2$ the arguments contained in a minimal relevant SCC.

We now turn to Condition (ii) of Proposition 5, where the first rule in $\pi _{{ stableN }}$ computes the set $T=U\setminus S^+_R$. Then we check whether $T=\emptyset$ and ${ MR }(F-S^+_R)=\emptyset$ via predicates ${\mathrm {emptyT}}/1$ and ${\mathrm {not\_exists\_mr}}/1$. If this is so, we terminate the iteration in the last module $\pi _{{ iterate }}$. The first constraint eliminates those guesses where ${ MR }(F-S^+_R)=\emptyset$ but $T\ne \emptyset$, because the algorithm is only defined for AFs fulfilling this. Finally we derive the arguments which are defeated by the set $T$ in the ${ MR }$ denoted by ${\mathrm {defeated}}/2$, and with the last constraint we eliminate those guesses where there is an argument not contained in $T$ and not defeated by $T$ in ${ MR }$ and hence $(T\cap \varPi _F)\not \in { stb }(F|_{\varPi _F})$.

$$\begin{aligned} \pi _{{ stableN }} =\{\,\,&{\mathrm t}(N,X) \leftarrow {\mathrm {inU}}(N,X), { not}\,{\mathrm {inS}}(N,X); \\&{\mathrm {nemptyT}}(N) \leftarrow {\mathrm t}(N,X); \\&{\mathrm {emptyT}}(N) \leftarrow { not}\,{\mathrm {nemptyT}}(N), {\mathrm {arg\_set}}(N,X); \\&{\mathrm {existsMR}}(N) \leftarrow {\mathrm {mr}}(N,X), {\mathrm {notInSplusN}}(N,X); \\&{\mathrm {not\_exists\_mr}}(N) \leftarrow { not}\,{\mathrm {existsMR}}(N), {\mathrm {notInSplusN}}(N,X); \\&{\mathrm {true}}(N) \leftarrow {\mathrm {emptyT}}(N), { not}\,{\mathrm {existsMR}}(N); \\&\leftarrow {\mathrm {not\_exists\_mr}}(N), {\mathrm {nemptyT}}(N); \\&{\mathrm {defeated}}(N,X) \leftarrow {\mathrm {mr}}(N,X), {\mathrm {mr}}(N,Y), {\mathrm t}(N,Y), {\mathrm {defeatN}}(N,Y,X); \\&\leftarrow { not}\,{\mathrm t}(N,X), { not}\,{\mathrm {defeated}}(N,X), {\mathrm {mr}}(N,X)\; \}. \end{aligned}$$

With the last module $\pi _{{ iterate }}$ we perform Step (iii) of Proposition 5. The predicate ${\mathrm {t\_mrOplus}}/2$ computes the set $(T\cap \varPi _F)^\oplus _R$ and with the second rule we start the next iteration for the AF $(F|_{\varPi _F^C} -(S^+_R \cup (T\cap \varPi _F)^\oplus _R))$ and the set $(T\cap \varPi _F^C)$.

Finally we put everything together and obtain the program $\pi _{ grd^* }$.

$$\begin{aligned} \pi _{ grd^* } = \pi _{{ groundN }} \cup \pi _{{ F\_minus\_range }} \cup \pi _{{ MR }} \cup \pi _{{ stableN }} \cup \pi _{{ iterate }}. \end{aligned}$$

Proposition 6.

For any AF $F$, $grd^* (F)\cong {\mathcal {AS}}(\pi _{ grd^* }(\hat{F}))$.

4 Experimental Evaluation

In this section we present our results of the performance evaluation. We compared the time needed for computing all extensions for the semantics described earlier, using both the handcraft saturation-based and the alternative metasp encodings.

The tests were executed on an openSUSE based machine with eight Intel Xeon processors (2.33 GHz) and 49 GB memory. For computing the answer sets, we used gringo (version 3.0.3) for grounding and the solver claspD (version 1.1.1). The latter being the variant for disjunctive answer-set programs.

Fig. 1.

Average computation time for preferred semantics.

Fig. 2.

Average computation time for semi-stable semantics.

Fig. 3.

Average computation time for stage semantics.

Fig. 4.

Average computation time for resolution-based grounded semantics.

We randomly generated AFs (i.e. graphs) ranging from $20$ to $110$ arguments. We used two parametrized methods for generating the attack relation. The first generates arbitrary AFs and inserts for any pair $(a,b)$ the attack from $a$ to $b$ with a given probability $p$. The other method generates AFs with an $n \times m$ grid-structure. We consider two different neighborhoods, one connecting arguments vertically and horizontally and one that additionally connects the arguments diagonally. Such a connection is a mutual attack with a given probability $p$ and in only one direction otherwise. The probability $p$ was chosen between $0.1$ and $0.4$.

Overall 14388 tests were executed, with a timeout of five minutes for each execution. Timed out instances are considered as solved in 300 seconds. The time consumption was measured using the Linux time command. For all the tests we let the solver generate all answer sets, but only outputting the number of models. To minimize external influences on the test runs, we alternated the different encodings during the tests.

Figures 1, 2 and 3 depict the results for the preferred, semi-stable and stage semantics respectively. The figures show the average computation time for both the handcraft and the metasp encoding for a certain number of arguments. We distinguish here between arbitrary, i.e. completely random AFs and grid structured ones. One can see that the metasp encodings have a better performance, compared to the handcraft encodings. In particular, for the stage semantics the performance difference is noticeable. Recall that the average computation time includes the timeouts, which strongly influence the diagrams.

For the resolution-based grounded semantics, Fig. 4 shows again the average computation time needed for a certain number of arguments. Let us first consider the case of arbitrary AFs. The handcraft encoding struggled with AFs of size $40$ or larger. Many of those instances could not be solved due to memory faults. This is indicated by the missing data points. Both metasp encodings performed better overall, but still many timeouts were encountered. If we look more closely at the structured AFs then we see that $\pi _{{ grd^* \_metasp }'}$ performs better overall than the other metasp variant. Interestingly, computing the grounded part with a handcraft encoding without a Guess&Check part did not result in a lower computation time on average. The handcraft encoding performed better than $\pi _{{ grd^* \_metasp }}$ on grids.

One reason for the performance problems of the handcraft encoding lies in the relatively high arity of some predicates. The encoding uses predicates with up to four variables, in contrast to the encoding for e.g. the stage semantics which needs only predicates with up to three variables. This can increase the time needed for grounding drastically. On the other side, the metasp encodings, as mentioned in Proposition 4, suffer from the fact that the answer sets are not in a one-to-one correspondence to the solutions, i.e. several answer sets may represent the same extension.

Overall the metasp encodings outperform the direct encodings. This is partially due to the fact that the former utilize encodings tailored to the gringo/claspD package.

5 Conclusion

In this paper, we inspected various ASP encodings for four prominent semantics in the area of abstract argumentation. (1) For the preferred and the semi-stable semantics, we compared existing saturation-based encodings [11] (here we called them handcrafted encodings) with novel alternative encodings which are based on the recently developed metasp approach [13], where subset-minimization can be directly specified and a front-end (i.e. a meta-interpreter) compiles such statements back into the core ASP language. (2) For the stage semantics, we presented here both a handcrafted and a metasp encoding. Finally, (3) for the resolution-based grounded semantics we provided three novel encodings, two of them using the metasp techniques.

While with some performance optimization techniques for ASP the readability of the encodings change for the worse, the metasp encodings are shorter than the handcrafted saturation encodings. Furthermore, they are much simpler to design (since saturation techniques are delegated to the meta-interpreter), and they perform surprisingly well when compared with the handcrafted encodings which are directly given to the ASP solver. This shows the practical relevance of the metasp technique also in the area of abstract argumentation. Future work will be to investigate performance improvements of other optimization features like aggregates, which are provided by most of the prominent ASP solvers.