Problems in abstract argumentation are typically beyond NP, but stay in the polynomial hierarchy. Answer set programming with quantifiers, ASP(Q), has recently been proposed as an extension of answer set programming, suitable for expressing problems in the polynomial hierarchy in arguably elegant ways. Already in the original paper, argumentation has been mentioned as an application domain for ASP(Q), but to our knowledge this has not been followed up yet. In this paper we provide a preliminary study of encoding problems in argumentation using ASP(Q). We also examine the computational behaviour of these encodings.
Following Dung’s seminal paper [
While ASP is a declarative formalism, encoding problems beyond NP is often involved and involves techniques such as saturation, which are notoriously dificult to handle and read. Several attempts were made to improve this, the most recent being Answer Set Programming with Quantifiers, ASP(Q), which combines several ASP parts with quantifiers over answer sets, which is an arguably much more accessible way of expressing problems beyond NP (but within PH).
It is therefore natural to use ASP(Q) for representing computational tasks arising in abstract
argumentation, which we propose in this paper. Actually, one such task has already been discussed in [
In particular, we focus on three “classic” semantics for Dung-style argumentation frameworks,
preferred [
We conjecture that many problems in argumentation can be encoded in similarly readable ways, which would allow for new syntaxtic extensions and semantics to be handled using ASP(Q) relatively easily, while still providing a reasonable computational tool in terms of performance.
We recall some definitions of abstract argumentation, originally defined in [
Definition 1. An argumentation framework (AF) is a pair = (, ) where is a set of arguments and ⊆ × . (, ) ∈ means that attacks . An argument ∈ is defended by ⊆ (in ) if, for each ∈ such that (, ) ∈ , there exists a ∈ , such that (, ) ∈ . An argument is admissible (in ) w.r.t. a set ⊆ if each ∈ which attacks is defended by .
While many semantics have been defined for AFs, we focus here on extension-based semantics,
where an extension is a set of acceptable arguments. There are diferent extension-based semantics,
reflecting diferent notions of acceptability. In this paper we look at admissible, preferred, semi-stable,
and stage extensions. The definition mostly follows the one in [
Definition 2. Let = (, ) be an AF. A set ⊆ is said to be conflict-free (in ), if there are no , ∈ , such that (, ) ∈ . For a set ⊆ , let the range + be ∪ { | ∃ ∈ : (, ) ∈ } (so and all arguments attacked from within ).
A set ⊆ is an admissible extension of , if is conflict-free in and each ∈ is admissible in w.r.t. . The set of admissible extensions of is denoted as ( ).
A set ⊆ is an preferred extension of , if ∈ ( ) and there is no ∈ ( ) with ⊃ . The set of preferred extensions of is denoted as ( ).
A set ⊆ is a semi-stable extension of , if ∈ ( ) and there is no ∈ ( ) with + ⊃ +. The set of semi-stable extensions of is denoted as ( ).
A set ⊆ is a stage extension of , if is conflict-free in and there is no conflict-free in with + ⊃ +. The set of stage extensions of is denoted as ( ).
Answer Set Programming with Quantifiers (ASP(Q)) has been proposed in [
□ 11□ 22 · · · □ : , where, for each ∈ {1, . . . , }, □ ∈ {∃, ∀}, is an ASP program, and is a stratified normal ASP program (this is, as intended by the ASP(Q) authors, a “check” in the sense of constraints). ∃ and ∀ are called existential and universal answer set quantifiers , respectively.
As a brief example, the intuitive reading of an ASP(Q) program ∃1∀2 : is that there exists an answer set 1 of 1 such that for each answer set 2 of 2 ∪ 1 it holds that ∪ 2 is consistent (i.e. has an answer set).
Let us be more precise about the program ∪ , that is, a program being extended by an answer set (or rather by an interpretation ): For an interpretation , let () be the ASP program that contains all atoms in as facts and all atoms appearing in but not in as constraints (i.e. as a rule ⊥ ← ). Furthermore, for a program and an interpretation , let (Π, ) be the ASP(Q) program obtained from an ASP(Q) program Π by replacing the first program 1 in Π with 1 ∪ (). Coherence of an ASP(Q) program is then defined inductively: • ∃ : is coherent if there exists an answer set of such that ∪ ( ) has at least one answer set. • ∀ : is coherent if for all answer sets of it holds that ∪ ( ) has at least one answer set. • ∃ Π is coherent if there exists an answer set of such that (Π, ) is coherent. • ∀ Π is coherent if for all answer sets of it holds that (Π, ) is coherent.
In addition, for an existential ASP(Q) program Π (one that starts with ∃), the witnessing answer sets of the first ASP program 1 are referred to as quantified answer sets .
Here, we provide ASP(Q) encodings for preferred, semi-stable, and stage extensions of argumentation frameworks. Here we assume (, ) to be given in the apx format, which is in fact an ASP fact base: for each ∈ it contains a fact arg(a)., and for each (, ) ∈ it contains a fact att(a,b).. For representing an ASP(Q) program we use the pyqasp syntax, in which ∃ and ∀ are replaced by the strings %@exists and %@forall, respectively, and the colon is replaced by %@constraint.
We begin with the encoding for preferred extensions, which builds on the well-known encoding for admissible extensions available in the system ASPARTIX1. ASPARTIX is a collection of ASP encodings for a wide range of argumentation tasks. %% S has to be conflict-free :- in(X), in(Y), att(X,Y). %% Argument X is defeated by S defeated(X) :- in(Y), att(Y,X). %% Argument X is not defended by S not_defended(X) :- att(Y,X), not defeated(Y). %% Each X \in S has to be defended by S :- in(X), not_defended(X). %% Argument X is defeated by S1 defeated1(X) :- in1(Y), att(Y,X).
%% If one S1 is a proper superset and admissible, then S is not preferred. :- in1(X), not in(X), arg(X).
In fact, the admissible extension encoding is essentially duplicated in the ∀ program, with the addition of a rule that only admits supersets of the admissible extension determined in the ∃ program. The check just makes sure that no strict superset is actually admissible. It is clear that the quantified answer sets correspond to preferred extensions.
We next present the encoding for semi-stable extensions, which is similar to the previous ASP(Q) program, but it additionally defines the ranges of the sets and uses these for the check. %% S has to be conflict-free :- in(X), in(Y), att(X,Y). %% Argument X is defeated by the set S defeated(X) :- in(Y), att(Y,X). %% Argument X is not defended by S not_defended(X) :- att(Y,X), not defeated(Y). %% Each X \in S has to be defended by S :- in(X), not_defended(X). %% S+ : S plus all arguments attacked by any argument in S inplus(X) :- in(X). inplus(X) :- in(Y), att(Y,X). %% Guess a set S1 \supseteq S in1(X) :- in(X). in1(X) :- not out1(X), arg(X). out1(X) :- not in1(X), arg(X). %% S1 has to be conflict-free :- in1(X), in1(Y), att(X,Y). %% Argument X is not defended by S1 not_defended1(X) :- att(Y,X), not defeated1(Y). %% Each X \in S has to be defended by S :- in1(X), not_defended1(X). %% S1+ : S1 plus all arguments attacked by any argument in S1 inplus1(X) :- in1(X). inplus1(X) :- in1(Y), att(Y,X). %% If one S1+ is a proper superset of S+ and S1 is admissible, then S is not preferred. :- inplus1(X), not inplus(X), arg(X).
So here it is checked that no range of a superset of an admissible extension is a superset of the range of the admissible extension. Again it is clear that the quantified answer sets correspond to semi-stable extensions.
Finally, we present the encoding for stage extensions. Here, we only look at conflict-free sets rather than admissible extensions, but the check involves the ranges, as for semi-stable extensions. %% Guess S \subseteq A in(X) :- not out(X), arg(X). out(X) :- not in(X), arg(X). %% S has to be conflict-free :- in(X), in(Y), att(X,Y). inplus(X) :- in(X). inplus(X) :- in(Y), att(Y,X). %% Guess a set S1 \supseteq S in1(X) :- in(X). in1(X) :- not out1(X), arg(X). out1(X) :- not in1(X), arg(X). %% S+ : S plus all arguments attacked by any argument in S %% Conflict-freeness of S1 %% S1 has to be conflict-free :- in1(X), in1(Y), att(X,Y). %% If one S1+ is a proper superset of S+ and S1 is conflict-free, then S is not a stage extens :- inplus1(X), not inplus(X), arg(X).
Again it is clear that the quantified answer sets correspond to stage extensions.
We have conducted some preliminary results with the encodings presented in the previous section. We
have used the 107 instances of the ICCMA 2019 competition2 and ran them using pyqasp in the version
presented in [
For preferred extensions, 42 instances were solved within the time limit, with 65 timing out. For semi-stable extensions, 43 instances were solved within the time limit, with 64 timing out. For stage extensions, only 17 were solved within the time limit, with 90 timing out. Overall, we believe that this is an acceptable result, as these are comparatively hard instances.
We have also compared the runtime to the ASPARTIX encodings for clingo. Interestingly, clingo had memory issues when computing semi-stable extensions, 56 instances exceeded the memory limit. 19 more timed out, leaving 32 solved instances. The picture was quite diferent when computing stage extensions: 91 were successfully solved by clingo, and only 16 timed out. Clingo was very performant for preferred extensions, only 7 timed out.
In Figures 3, 1, and 2 we provide scatter plots comparing pyqasp’s and clingo’s performance. The runtime for pyqasp on a specific instance determines the vertical position, while the runtime for clingo for the same instance determines the horizontal position of a dot. So, each dot in these diagrams represents one instance - if it is in the upper left of the diagram, clingo was faster, if it is in the lower right, then pyqasp was faster. We can see that pyqasp seems more performant for computing a semistable extension, whereas clingo seems more performant for computing a preferred or stage extension overall.
We have shown that some well-known semantics for argumentation frameworks can be encoded in a very intuitive way using ASP(Q). While this is not surprising, we believe that these are the most readable representations available. What we could show in our experiments is that there is no significant penalty in terms of performance, which was less clear. Indeed, for the semi-stable semantics the more readable encoding actually also seems to be computationally better with the compared tools, which is perhaps surprising. 2Folder 2019 in https://argumentationcompetition.org/2021/instances.tar.gz 0 50 100 200 250
300 150 clingo clingo 200 250 300
We believe that this can open the ground for a flexible tool similar to ASPARTIX, which can allow for rapid prototyping for many variations and extensions of argumentation frameworks.
This research was funded in part by the Austrian Science Fund (FWF) projects 10.55776/PIN8782623 and 10.55776/COE12. clingo 200 250 300
For completeness and comparison, we also provide the encodings for preferred, semi-stable, and stage extensions of ASPARTIX3
A.1. Preferred Extensions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Encoding for preferred extensions % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Guess a set S \subseteq A in(X) :- not out(X), arg(X). out(X) :- not in(X), arg(X). %% S has to be conflict-free :- in(X), in(Y), att(X,Y). %% The argument x is defeated by the set S defeated(X) :- in(Y), att(Y,X). %% The argument x is not defended by S not_defended(X) :- att(Y,X), not defeated(Y). %% All arguments x \in S need to be defended by S (admissibility) :- in(X), not_defended(X). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % For the remaining part we need to put an order on the domain. % Therefore, we define a successor-relation with infinum and supremum % as follows %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% lt(X,Y) :- arg(X),arg(Y), X<Y, not input_error. nsucc(X,Z) :- lt(X,Y), lt(Y,Z). succ(X,Y) :- lt(X,Y), not nsucc(X,Y). ninf(X) :- lt(Y,X). nsup(X) :- lt(X,Y). inf(X) :- not ninf(X), arg(X). sup(X) :- not nsup(X), arg(X). %% Guess S’ \supseteq S inN(X) :- in(X). inN(X) | outN(X) :- out(X). %% If S’ = S then spoil. %% Use the sucessor function and check starting from supremum whether %% elements in S’ is also in S. If this is not the case we "stop" %% If we reach the supremum we spoil up. % eq indicates whether a guess for S’ is equal to the guess for S eq_upto(Y) :- inf(Y), in(Y), inN(Y). eq_upto(Y) :- inf(Y), out(Y), outN(Y). eq_upto(Y) :- succ(Z,Y), in(Y), inN(Y), eq_upto(Z). eq_upto(Y) :- succ(Z,Y), out(Y), outN(Y), eq_upto(Z). eq :- sup(Y), eq_upto(Y). undefeated_upto(X,Y) :- inf(Y), outN(X), outN(Y). undefeated_upto(X,Y) :- inf(Y), outN(X), not att(Y,X). undefeated_upto(X,Y) :- succ(Z,Y), undefeated_upto(X,Z), outN(Y). undefeated_upto(X,Y) :- succ(Z,Y), undefeated_upto(X,Z), not att(Y,X). undefeated(X) :- sup(Y), undefeated_upto(X,Y). %% spoil if the AF is empty not_empty :- arg(X). spoil :- not not_empty. %% spoil if S’ equals S for all preferred extensions spoil :- eq. %% S’ has to be conflict-free - otherwise spoil spoil :- inN(X), inN(Y), att(X,Y). %% S’ has to be admissible - otherwise spoil spoil :- inN(X), outN(Y), att(Y,X), undefeated(Y). inN(X) :- spoil, arg(X). outN(X) :- spoil, arg(X). %% do the final spoil-thing ... :- not spoil. %in(X)? #show in/1.
A.2. Semi-stable Extensions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Encoding for semi-stable extensions % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Guess a set S \subseteq A in(X) :- not out(X), arg(X). out(X) :- not in(X), arg(X). %% S has to be conflict-free :- in(X), in(Y), att(X,Y). %% The argument x is not defended by S not_defended(X) :- att(Y,X), not defeated(Y). %% All arguments x \in S need to be defended by S (admissibility) :- in(X), not_defended(X). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % For the remaining part we need to put an order on the domain. % Therefore, we define a successor-relation with infinum and supremum % as follows %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% lt(X,Y) :- arg(X),arg(Y), X<Y, not input_error. nsucc(X,Z) :- lt(X,Y), lt(Y,Z). succ(X,Y) :- lt(X,Y), not nsucc(X,Y). ninf(X) :- lt(Y,X). nsup(X) :- lt(X,Y). inf(X) :- not ninf(X), arg(X). sup(X) :- not nsup(X), arg(X). %% Guess S’ \supseteq S for semi-stable inN(X) | outN(X) :- arg(X), not input_error. % eqplus checks wheter S’+ equals S+ eqplus_upto(Y) :- inf(Y), in(Y), inN(Y). eqplus_upto(Y) :- inf(Y), in(Y), inN(X), att(X,Y). eqplus_upto(Y) :- inf(Y), in(X), inN(Y), att(X,Y). eqplus_upto(Y) :- inf(Y), in(X), inN(Z), att(X,Y), att(Z,Y). eqplus_upto(Y) :- inf(Y), out(Y), outN(Y), not defeated(Y), undefeated(Y). eqplus_upto(Y) :- succ(Z,Y), in(Y), inN(Y), eqplus_upto(Z). eqplus_upto(Y) :- succ(Z,Y), in(Y), inN(X), att(X,Y), eqplus_upto(Z). eqplus_upto(Y) :- succ(Z,Y), in(X), inN(Y), att(X,Y), eqplus_upto(Z). eqplus_upto(Y) :- succ(Z,Y), in(X), inN(U), att(X,Y), att(U,Y), eqplus_upto(Z). eqplus_upto(Y) :- succ(Z,Y), out(Y), outN(Y), not defeated(Y), undefeated(Y), eqplus_upto( eqplus :- sup(Y), eqplus_upto(Y). %% get those X \notin S’ which are not defeated by S’ %% using successor again... undefeated_upto(X,Y) :- inf(Y), outN(X), outN(Y). undefeated_upto(X,Y) :- inf(Y), outN(X), not att(Y,X). undefeated_upto(X,Y) :- succ(Z,Y), undefeated_upto(X,Z), outN(Y). undefeated_upto(X,Y) :- succ(Z,Y), undefeated_upto(X,Z), not att(Y,X). undefeated(X) :- sup(Y), undefeated_upto(X,Y). %% spoil if the AF is empty not_empty :- arg(X). spoil :- not not_empty. %% spoil if S’+ equals S+ spoil :- eqplus. %% S’ has to be conflictfree - otherwise spoil spoil :- inN(X), inN(Y), att(X,Y). %% spoil if not semi-stable spoil :- inN(X), outN(Y), att(Y,X), undefeated(Y). spoil :- in(X), outN(X), undefeated(X). spoil :- in(Y), att(Y,X), outN(X), undefeated(X). inN(X) :- spoil, arg(X). outN(X) :- spoil, arg(X). %% do the final spoil-thing ... :- not spoil.
A.3. Stage Extensions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Encoding for stage extensions % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Guess a set S \subseteq A in(X) :- not out(X), arg(X). out(X) :- not in(X), arg(X). %% S has to be conflict-free :- in(X), in(Y), att(X,Y). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % For the remaining part we need to put an order on the domain. % Therefore, we define a successor-relation with infinum and supremum % as follows %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% lt(X,Y) :- arg(X),arg(Y), X<Y, not input_error. nsucc(X,Z) :- lt(X,Y), lt(Y,Z). succ(X,Y) :- lt(X,Y), not nsucc(X,Y). ninf(X) :- lt(Y,X). nsup(X) :- lt(X,Y). inf(X) :- not ninf(X), arg(X). sup(X) :- not nsup(X), arg(X). %% Computing the range S+ of the guessed set S in_range(X) :- in(X). in_range(X) :- in(Y), att(Y,X). %% Guess S’ \supseteq S for semi-stable inN(X) | outN(X) :- arg(X), not input_error. % eqplus checks wheter S’+ equals S+ eqplus_upto(X) :- inf(X), in_range(X), in_rangeN(X). eqplus_upto(X) :- inf(X), not_in_range(X), not_in_rangeN(X). eqplus_upto(X) :- succ(Z,X), in_range(X), in_rangeN(X), eqplus_upto(Z). eqplus_upto(X) :- succ(Z,X), not_in_range(X), not_in_rangeN(X), eqplus_upto(Z). eqplus :- sup(X), eqplus_upto(X). %% get those X \notin S’ which are not defeated by S’ %% using successor again... undefeated_upto(X,Y) :- inf(Y), outN(X), outN(Y). undefeated_upto(X,Y) :- inf(Y), outN(X), not att(Y,X). undefeated_upto(X,Y) :- succ(Z,Y), undefeated_upto(X,Z), outN(Y). undefeated_upto(X,Y) :- succ(Z,Y), undefeated_upto(X,Z), not att(Y,X). not_in_rangeN(X) :- sup(Y), outN(X), undefeated_upto(X,Y). in_rangeN(X) :- inN(X). in_rangeN(X) :- outN(X), inN(Y), att(Y,X). %% fail if the AF is empty not_empty :- arg(X). fail :- not not_empty. %% S’ has to be conflictfree - otherwise fail fail :- inN(X), inN(Y), att(X,Y). %% fail if S’+ equals S+ fail :- eqplus. %% fail if S’+ \subset S+ fail :- in_range(X), not_in_rangeN(X). inN(X) :- fail, arg(X). outN(X) :- fail, arg(X). %% do the final spoil-thing ... :- not fail.