A ConArg-based Library for Abstract Argumentation

Abstract

We present ConArgLib, a C++ library implemented to help programmers solve some of the most important problems related to extension-based Abstract Argumentation. The library is based on ConArg, which exploits Constraint Programming and, in particular, Gecode, a toolkit for developing constraint-based systems and applications. Given a semantics, such problems consist, for example, in enumerating all the extensions, and checking the credulous or sceptical acceptance of an argument passed as parameter. The goal is to let programmers use the library to quickly develop programs on top of it, as, for instance, implementing decision-making procedures based on the strongest arguments.

Introduction

We present ConArgLib, a C++ library implemented to help programmers solve some intractable problems related to extension-based Abstract Argumentation [ 12 ]. The library is based on a revised search engine developed for ConArg [ 3 ], a stand-alone solver submitted to ICCMA15 [ 19 ] and (in its revised version) to ICCMA17 1, that is the International Competition on Computational Models of Argumentation. The search engine exploits Gecode2, a toolkit for developing constraint-based systems and applications.

An Abstract Argumentation Framework (AAF ) is simply a pair xArgs; Ry consisting of a set Args whose elements are called arguments, and of a binary relation R on Args, called \attack" relation. For example, the framework xta; b; cu; tRpa; bq; Rpb; cquy has three arguments labelled as a, b, and c, and there is an attack between a and b, and b and c. A framework can be simply represented as a directed graph, where nodes are arguments, and edges model attacks. The sets of arguments (or extensions [ 12 ]) to be considered are then de ned under di erent semantics, which represent di erent degrees of scepticism. Most of them are based on both the notion of con ict-freedom (extensions must not contain attacks), and the notion of defence: in the previous AAF, b attacks c, but a defends c since it attacks b.

Recent years have seen researchers drawing their attention on computational aspects of Abstract Argumentation; in particular, on tools that are capable to solve classical problems, as, given a semantics, i) the enumeration of extensions satisfying it, ii) the veri cation whether a subset of arguments satis es it, iii) and iv) the sceptical and credulous acceptance of an argument (if an argument belongs to resp. all or at least one of the extensions), v) the existence of at least one extension, and nally vi) the non-emptiness of at least one extension, i.e., if di erent from H.

In addition to AAFs [ 12 ], ConArgLib also solves a weighted extension of them we present in [ 2, 6 ]: semiring-based Weighted Abstract Argumentation Frameworks (simply WAAFs in the following), where attacks are associated with a value (taken an algebraic structure, i.e., a c-semiring [ 5 ]) representing e.g., a strength score or an uncertainty degree. Then, in [ 2 ] we study two di erent relaxations of WAAFs: the rst one is related to the new weighted defence we propose in [ 6 ], by checking the di erence between the composition of inward and outward attack-weights. The second one is related to how much inconsistency we are willing to tolerate inside an extension; such an amount is computed by aggregating the weights of the attacks between any two arguments inside an extension. These relaxations are correlated: allowing a small con ict may lead to have more arguments into an extension, and consequently result in a stronger or weaker defence.

To code the library we take advantage of Constraint Programming (CP) [ 18 ] since the problems i-vi can be intractable [ 11 ], depending on the semantics. Despite the plethora of aforementioned solvers, as far as we know, ConArgLib represents the rst attempt to provide a fast implementation of a library to support the solution of problems in Abstract Argumentation. The end programmer can use it to directly develop her own applications, instead of interfacing to an external solver: as an example, solving the existence of a non-empty extension, and the credulous/sceptical acceptance of arguments can be used to set-up a decision-making procedure by ranking the arguments, and then to select the decision supported by the strongest ones.

The paper is organised as follows: in Sec. 2 we provide the necessary background on Dung's AAFs [ 12 ], and c-semirings [ 5 ], i.e., the general algebraic structure we use to parametrise weights in WAAFs in [ 2, 6 ], whose presentation concludes this section. In Sec. 3 we provide a description of ConArgLib. Then, in Sec. 4 we report some implementation details to explain the engine of the library. Finally, in Sec. 5 we wrap up the paper with general conclusions and ideas about future work. 2

Background

This section is structured in three parts: rst we collect the main background notions about AAFs [ 12 ] (Sec. 2.1), then we introduce c-semirings (Sec. 2.2), and nally semiring-based WAAFs (Sec. 2.3). 2.1 In his pioneering work [ 12 ], Dung proposed Abstract Frameworks for Argumentation, where an argument is an abstract entity whose role is solely determined by its relations to other arguments: De nition 1 (Argumentation Frameworks [ 12 ]). An Abstract Argumentation Framework (AAF) is a pair xArgs; Ry of a set Args of arguments and a binary relation R on Args, called attack relation. @ai; aj P Args, aiR aj (or Rpai; aj q) means that ai attacks aj (R is asymmetric).

An argumentation semantics is the formal de nition of a method (either declarative or procedural) ruling the argument evaluation process. In the extension-based approach, a semantics de nition speci es how to derive from an AAF a set of extensions, where an extension B of an AAF xArgs; Ry is simply a subset of Args. In Def. 2 we de ne the rst semantics, which is at the basis of all the others: De nition 2 (Con ict-free [ 12 ]). A set B „ Args is con ict-free i no two arguments a and b in B exist such that a attacks b.

All the other semantics presented in this section rely (explicitly or implicitly) upon the concept of defence: De nition 3 (Defence [ 12 ]). An argument c is defended by a set B „ Args (or B defends b) i for any argument a P Args, if Rpa; cq then Db P B s.t., Rpb; aq.

An admissible set of arguments according to Dung must be a con ict-free set which defends all its elements. Formally: De nition 4 (Admissible [ 12 ]). A con ict-free set B „ Args is an admissible set i each argument in B is defended by B.

The following four de nitions elaborate on con ict-freedom and admissibility: De nition 5 (Complete [ 12 ]). An admissible set B „ Args is a complete extension i each argument which is defended by B is in B.

De nition 6 (Preferred [ 12 ]). A preferred extension is a maximal (w.r.t. set inclusion) admissible set of Args.

The de nition of stage [ 20 ] and semi-stable [ 10 ] semantics is based on the idea of prescribing the maximisation not only of the arguments included in an extension (as for the preferred extension), but also of those attacked by it: De nition 7 (Stage [ 20 ] and semi-stable [ 10 ]). Given a set B „ Args , the range of B is de ned as B Y B , where B ta P Args : B attacks au. B is a stage extension i is a con ict-free set with maximal (wrt. set inclusion) range. B is semi-stable extension i B is a complete extension with maximal (w.r.t. set inclusion) range.

Finally, the stable semantics corresponds to the most stringent among all: De nition 8 (Stable [ 12 ]). A con ict-free set B „ Args is a stable extension i for each argument which is not in B, there exists an argument in B that attacks it.

The last three semantics, i.e., the grounded [ 12 ], ideal [ 13 ], and eager [ 9 ], enforce a sceptical approach: these semantics that always yields exactly one extension.

De nition 9 (Grounded [ 12 ]). The grounded extension is the minimal (w.r.t. set inclusion) complete extension [ 12 ].

De nition 10 (Ideal [ 13 ]). B „ Args is ideal i B is admissible and @B1 s.t. B1 is preferred, B „ B1. The ideal extension is the maximal (w.r.t. set inclusion) ideal set.

De nition 11 (Eager [ 9 ]). B „ Args is eager i B is admissible and @B1 s.t. B1 is semi-stable, B „ B1. The eager extension is the maximal (w.r.t. set inclusion) eager set.

If P tcf ; adm; com; prf ; sst ; stg ; stbu respectively stand for con ict-free and admissible sets, complete, preferred, semi-stable, stage, and stable semantics, and pF q is the set of all the extensions satisfying on a framework F , then we have stb pF q „ sst pF q „ prf pF q „ com pF q „ adm pF q „ cf pF q, and stb pF q „ stg pF q „ cf pF q. Moreover, if grd, ide, and eag are respectively the grounded, ideal, and eager extension, then we have that grd „ ide „ eag [ 9 ].

Consider the AAF F xA; Ry in Fig. 1, with A ta; b; c; d; eu and R tpa; bq; pc; bq; pc; dq; pd; cq; pd; eq; pe; equ. For example we have that adm pF q corresponds to tH; tau; tcu; tdu; ta; cu; ta; duu, com pF q ttau; ta; cu; ta; duu, stb pF q tta; cu; ta; duu, stb pF q tta; duu, and grd ttauu. 2.2

C-semirings C-semirings [ 5 ] are commutative (b is commutative) and idempotent semirings (i.e., ` is idempotent), where ` de nes a complete lattice: every subset of elements have a least upper bound, or lub, and a greatest lower bound, or glb. De nition 12 (C-semirings [ 5 ]). A commutative semiring is a tuple S xS; `; b; K; Jy such that S is a set, J; K P S, and `; b : S S ÝÑ S are binary operators making the triples xS; `; Ky and xS; b; Jy commutative monoids (semi-groups with identity), satisfying i) @s; t; u P S:s b pt ` uq ps b tq ` ps b uq (distributivity), and ii) @s P S:sbK K (annihilator). If @s; t P S:s`psbtq s, S is said to be absorptive, and consequently ` is idempotent. In short, c-semirings are de ned as commutative and absorptive semirings.

The idempotency of ` leads to the de nition of a partial ordering ¤S over the set S (S is a poset). Such partial order is de ned as s ¤S t if and only if s ` t t, and ` returns the lub of s and t. This intuitively means that t is \better" than s. Some more properties can be derived on c-semirings [ 5 ]: i) both ` and b are monotone over ¤S, ii) b is intensive (i.e., s b t ¤S s), and iii) xS; ¤Sy is a complete lattice. K and J are respectively the bottom and top elements of such lattice. When also b is idempotent, i) ` distributes over b, ii) b returns the glb of two values in S, and iii) xS; ¤Sy is a distributive lattice.

Some well-known instances of c-semirings in the literature are: Sboolean xtfalse; trueu; _; ^; false; truey3, Sfuzzy xr0; 1s; max; min; 0; 1y, Sbottleneck xR Y t 8u; max; min; 0; 8y, Sprobabilistic xr0; 1s; max; ; 0; 1y (or Viterbi semiring), Sweighted xR Y t 8u; min; ; 8; 0y.

Although c-semirings have been historically used as monotonic structures, the need of removing values has raised in local consistency algorithms [ 2 ]. A solution comes from residuation theory [ 8 ], which allows for obtaining a division operator that represents a \weak" inverse of b.

De nition 13 (Division). A c-semiring S is residuated if the set tx P S | t b x ¤ su admits a maximum for all elements s; t P S, denoted s m t.

Since a complete4 tropical-semiring is also residuated, we have that all the classical instances of c-semiring presented above are residuated, i.e., each element in S admits an \inverse", which can be also unique: De nition 14 (Unique invertibility). If S is absorptive and invertible, then it is uniquely invertible i it is cancellative, i.e., @s; t; u P S:ps b u t b uq ^ pu 0q ñ s t.

Since all the previously listed instances of c-semirings are cancellative, they are uniquely invertible as well. For instance, mintx | b

x ¥ au maxtx | minpb; xq ¤ au #0 a

if b ¥ a b if a ¡ b #1 if b ¤ a a if a   b weighted fuzzy 3 Boolean c-semirings can be used to model crisp problems and classical Argumentation [ 12 ]. 4 S is complete if it is closed with respect to in nite sums, and the distributivity law holds also for an in nite number of summands. 2.3

Semiring-based Weighted AAFs In the beginning of this section we rephrase some of the classical de nitions given in Sec. 2.1, with the purpose of parametrising them with the notion of weighted attack and c-semiring. The following de nition reshapes the notion of WAAF into semiring-based WAAF [ 2 ], called WAAF S: De nition 15 (Semiring-based WAAF). A semiring-based Weighted AAF (WAAF S) is a quadruple xArgs; R; W; Sy, where S is a c-semiring xS; `; b; K; Jy, Args is a set of arguments, R the attack binary-relation on Args, and W : Args Args ÝÑ S is a binary function. Given a; b P Args and Rpa; bq, then W pa; bq s means that a attacks b with a weight s P S. Moreover, we require that Rpa; bq i W pa; bq  S J.

In Fig. 2 we provide an example of a weighted interaction graph describing the WAAF S de ned by Args ta; b; c; d; eu, R tpa; bq; pc; bq; pc; dq; pd; cq; pd; eq; pe; equ, with W pa; bq 7; W pc; bq 8; W pc; dq 9; W pd; cq 8; W pd; eq 5; W pe; eq 6, and S xR Y t8u; min; ; 8; 0y (i.e., the weighted semiring).

Therefore, each attack is associated with a semiring value that represents the \strength" of an attack between two arguments. We can consider the weights in Fig. 2 as supports to the associated attack, as similarly suggested in [ 14 ]. A semiring value equal to the top element of the c-semiring J represents a no-attack relation between two arguments.

In Def. 16 we de ne the attack strength for a set of arguments that attacks an argument, a di erent set of arguments, or an argument that attacks a set of arguments; the former and the latter are what we need to de ne w-defence. We use  to indicate the set-wise version of b:

xArgs; R; W; Sy, De nition 16 (Attacks to/from sets of arguments). Given a WAAF S, WF

bPB;dPD { a set of arguments B attacks an argument a with a weight of k P S if W pB; aq â W pb; aq k.

bPB { an argument a attacks a set of arguments B with a weight of k P S if W pa; Bq â W pa; bq k.

bPB { a set of arguments B attacks a set of arguments D with a weight k P S if W pB; Dq â W pb; dq k.

8 9 a 7

8 b c d 5 e 6

For example, looking at Fig. 2 we have that W pta; cu; bq 15, W pc; tb; duq 17, and W pta; cu; tb; duq 24.

We are now ready to de ne our version of weighted defence, i.e., w-defence: De nition 17 (w-defence (Dw) [ 6 ]). Given a WAAF S, WF xArgs; R; W; Sy, B „ Args w-defends b P Args from a P Args s.t. Rpa; bq, i W pa; B Y tbuq ¥S W pB; aq; B w-defends b i it defends b from any a s.t. Rpa; bq.

De nition 17 can be relaxed to -defence, which is parametrised on a thresholdvalue : such is used to consider arguments that are not \fully" w-defended [ 6 ], i.e., for which W pa; B Y tbuq §S W pB; aq: De nition 18 ( -defence (D ) [ 2 ]). Given xArgs; R; W; S xS; `; b; K; Jyy and P S, B „ Args -defends b P Args i @a P Args such that Rpa; bq we have that W pB; aq J and

W pa; B Y tbuq m W pB; aq ¥S

Considering the example in Fig. 2, for instance tdu 1-defends d from c (i.e., 1):

W pc; tduq W ptdu; cq ¤ 1;

since 9 8 1 and 1 ¤ 1.

Having de ned D as a relaxation of Dw, we can rede ne all the classical semantics in Sec. 2.1 by exploiting both the notion of i) an inconsistency amount inside an extension (to be tolerated), and ii) D .

In Def. 19 we rede ne con ict-free sets: con icts can be now part of the solution up to a cost-threshold . They are now called -con ict-free sets: De nition 19. ( -con ict-free sets) Given a WAAF S, WF a set of arguments B „ Args is -con ict-free i W pB; Bq ¥S .

With respect to the WAAF S in Fig. 2, while the set ta; b; cu is not con ict-free in the crisp version of the problem (since it includes the attacks between a and b, and between c and b), ta; b; cu is instead 15-con ict-free because W pa; bq W pc; bq 15. For instance, ta; b; cu is also 16-con ict-free because it is a 15con ict-free (15 ¥S 16 in the weighted semiring).5 Therefore, in -con ict-free extensions we tolerate an internal inconsistency-amount better than .

D leads to the de nition of -admissible sets.

De nition 20. ( -admissible sets) Given WF xArgs; R; W; Sy, an con ict-free set B „ Args is -admissible i the arguments in B are -defended by B from the arguments in ArgszB. 5 In the weighted semiring, ¤S is equivalent to ¥ over Real numbers, while in the probabilistic and fuzzy semirings, ¥S corresponds to ¥ over Real numbers in the interval r0::1s.

For instance, the set td; eu in Fig. 2 is 111-admissible, since it is 11-con ictfree, and d defends itself (and the whole td; eu) from c by paying a penalty of 9 8 ¤ 1.

Four semantics that re ne -admissibility are introduced from Def. 21 to Def. 23: De nition 21 ( -complete). Given xArgs; R; W; Sy, an -admissible B „ Args is -complete i each argument b P Args that is -defended by B and s.t. W pB Y tbu; B Y tbuq ¥S is in B (i.e., b P B).

For instance, the set ta; du in Fig. 2 is complete according to [ 12 ] (i.e., not considering weights), but it is not 00-complete because d is not able to w-defend ta; du from c. However, ta; du is 01-complete by considering the weighted semiring and allowing 1. Note that ta; du also 1-defends argument e, but ta; d; eu is not 01-complete if we keep 0: bringing e inside would lead to an internal con ict of W pd; eq W pe; eq 11.

De nition 22 ( -preferred). An -preferred extension is a maximal (with respect to set inclusion) -admissible subset of Args.

Still considering Fig. 2, ta; cu and ta; du are the two preferred extensions according to [ 12 ] (i.e., not considering weights). However, ta; cu is the only 00preferred extension, while tta; cu; ta; duu is the set of 01-preferred extensions.

Finally, we de ne -stable semantics.

De nition 23. ( -stable semantics) Given xArgs; R; W; Sy, an -admissible set B is also an -stable extension i @a R B; Db P B:W pb; aq J, and B Y tau is not -admissible.

For example, considering the problem in Fig. 2 as unweighted (i.e., as a classical AAF), the set ta; du corresponds to the only stable extension. However, considering weights, this set is not 00-stable, because W pc; dq §S W pta; du; cq, i.e., 9 ¦ 8. However, it is 01-stable, since W pc; dq m W pta; du; cq 9 8 ¤ 1 satis es 1. Thus, in such example there is no 00-stable extension.

When J and J, JJ-semantics are equivalent to their classic counterpart in Sec. 2.1 [ 2 ]. 3

The Library

ConArgLib is available for Linux 64bit platform, and it has been compiled with gcc 4.9.2 and glibc 2.19 (using Debian 8). The pre-compiled package is freely available online.6 ConArgLib sits on the layer o ered by Gecode 5.1.0, which implements the search engine. Given a semantics , and the set of extensions pF q that satisfy over a framework F , the decision problems solved by ConArgLib are:

6 http://www.dmi.unipg.it/conarg/.

Enumeration. Given F xArgs; Ry and a semantics , this problem consists in enumerating all B P pF q.

Credulous Acceptance. Given F xArgs; Ry, a semantics , and an argument a P Args, a is credulously accepted if DB P pF q; a P B.

Sceptical Acceptance. Given F xArgs; Ry, a semantics , and an argument a P Args, a is sceptically accepted if @B P pF q; a P B.

Veri cation. Given F xArgs; Ry, a semantics , and a subset of arguments

B, the veri cation of B consists in checking if B P pF q.

Existence. Given F xArgs; Ry and a semantics , this problem corresponds to checking whether pF q H.

Non-emptiness. Given F xArgs; Ry and a semantics , this problem corresponds to checking whether there is any B P pF q for which B H.

The complexity of extension enumeration is reported in [ 17 ]. The complexity of the other previouslt presented problems, e.g., credulous/sceptical acceptance, can be instead found in [ 11 ], [ 16 ], and [ 15 ].

We now introduce the functions we can use to solve each of the six problems previously introduced. Besides \Admissible", each of the four following functions can also be called by replacing it with \Con ictFree", \Complete", \Preferred", \SemiStable", \Stable", \Grounded", \Ideal", \Stage", and \Eager"; hence the library implements all the classical semantics in Sec. 2.1: s e t <t S o l u t i o n > GetAdmissibleEnum ( ) ; s t r i n g GetAdmissibleCred ( s t r i n g &sArg ) ; s t r i n g G e t A d m i s s i b l e S c e p t ( s t r i n g &sArg ) ; b o o l I s A d m i s s i b l e ( v e c t o r <s t r i n g > &vecExtToCheck ) ; s e t <t S o l u t i o n > G e t A d m i s s i b l e E x i s t ( ) ; s e t <t S o l u t i o n > NonEmptinessAdmissible ( ) ;

In addition, other functions have been coded to solve the relaxed framework presented in [ 2, 6 ]. It is then possible to pass as input parameters the chosen semiring (see in the following for implemented ones), the amount of internal relaxation (dAlpha), and the amount of relaxation on the defence (dGamma). All the following functions are presented for the admissible semantics, but by replacing \Admissible" sub-strings with \Con ictFree", \Complete", \Preferred", \Stable", or \Grounded", it is possible to nd a solution for the corresponding semantics (all the semantics in Sec. 2.3): s e t <t S o l u t i o n > GetAdmissibleEnum ( double dAlpha , double dGamma) ; s e t <t S o l u t i o n > G e t A d m i s s i b l e E x i s t ( double dAlpha , double dGamma) ; s t r i n g GetAdmissibleCred ( s t r i n g &sArg , double dAlpha , double dGamma) ; s t r i n g G e t A d m i s s i b l e S c e p t ( s t r i n g &sArg , double dAlpha , double dGamma) ; bool I s A d m i s s i b l e ( v e c t o r <s t r i n g > &vecExtToCheck , double dAlpha , double dGamma) ; s e t <t S o l u t i o n > NonEmptinessAdmissible ( double dAlpha , double dGamma) ;

The following semirings are at the moment de ned and implemented in ConArgLib: xtfalse; trueu; _; ^; false; xr0; 1s; max; min; 0; 1y, and xR Y t 8u; min; ; 8; 0y. #define CL SRTYPE BOOLEAN 0 #define CL SRTYPE FUZZY 1 #define CL SRTYPE WEIGHTED 2

The following calls are instead used to manage the library: bool L o a d F i l e ( s t r i n g &sInputFileName ) ; void P r i n t S o l ( s e t <t S o l u t i o n > p s e t S o l ) ; void F r e e S o l ( s e t <t S o l u t i o n > p s e t S o l ) ; bool E n g i n e I s I n i t i a l i z e d ( ) ; int G e t So l u t i on s C o u nt ( s e t <t S o l u t i o n > double GetFuzzyBestValue ( ) ; double GetFuzzyWorstValue ( ) ; double GetWeightedBestValue ( ) ; double GetWeightedWorstValue ( ) ; p s e t S o l ) ;

LoadFile is used to load the description of an AAF by passing a le path. For classical AAFs we use ASPARTIX format (apx ), which corresponds to a text le with a list of arguments, expressed as \arg(argumentName).", and a list of attacks between them, e.g., \att(argument1Name, argumentName2).". To represent WAAFs as proposed in Sec. 2.3, we have modi ed the apx format into wapx : the list of arguments is expressed in the same way, while attacks are associated with a score, i.e., att(argumentName1, argumentName2):-score.

PrintSol is used to print all the solutions: hence, it is meaningful for the enumeration, existence, and non-emptiness problems.

FreeSol deallocates the passed set of solutions from dynamic memory.

EngineIsInitialized checks if the search engine has been correctly initialised; for instance, it checks whether a semiring type has been already selected.

GetSolutionsCount returns the number of solutions for the last solved problem (it is meaningful in case of enumeration).

GetFuzzyBestValue and GetFuzzyWorstValue can be used by the programmer to respectively retrieve the top and bottom elements in fuzzy semiring (see Sec. 2.2). The same holds for GetWeightedBestValue and GetWeightedWorstValue, w.r.t. the weighted semiring.

The following group of functions collects the functionalities to con gure how solutions are found and printed. SetShowSolutions sets if the set of solutions is printed on the screen or silenced, besides being saved in memory.

SetRequestedSolutions stops the search as soon as a given number (input parameter) of solutions is found, while SetRequestedAllSolutions returns all the found solutions (these functions are meaningful only for the enumeration problem).

SetStatistics prints the search statistics obtained from Gecode: speci cally, it returns the number of failed nodes in search tree, the number of nodes expanded, the maximum depth during search, the number of restarts, and, nally, the number of posted no-goods.

SetProboOutput sets the output of requested problems to be compliant with Probo7, which is the benchmark framework used for computational argumentation competitions (i.e., ICCMA15 and ICCMA17).

SetPercentOutput also prints the rate of appearance (as percentage) of each argument in the current solutions. It can be used in combination with solving the enumeration problem over any semantics, in order to understand the degree of acceptability of each argument.

SetSilentMode trims part of the output, e.g., removes messages concerning the kind of problem being solved.

All these function are also replicated with \Get" instead of \Set" in order to know how parameters are currently set. Finally, ResetDefaults restores them to the initial values (e.g., output is not silenced by default). void S e t S h o w S o l u t i o n s ( bool bFlag ) ; void S e t R e q u e s t e d S o l u t i o n s ( long lRS ) ; void S e t R e q u e s t e d A l l S o l u t i o n s ( ) ; void S e t S t a t i s t i c s ( bool bStat ) ; void SetProboOutput ( bool bProbo ) ; void SetPercentOutput ( bool bPercent ) ; void S e t S i l e n t M o d e ( bool bSilentMode ) ; void SetShowSolutionsCount ( bool bShowSolutionsCount ) ; bool GetShowSolutions ( ) ; long G e t R e q u e s t e d S o l u t i o n s ( ) ; bool G e t S t a t i s t i c s ( ) ; bool GetProboOutput ( ) ; bool GetPercentOutput ( ) ; bool GetSilentMode ( ) ; void R e s e t D e f a u l t s ( ) ;

An example of a program using ConArgLib is shown in Fig. 3: the code nds all the admissible sets and prints them on the screen. The example in Fig. 4 shows instead how to verify that the set ta; du is a 01-stable extension (see Def. 23) according to the weighted semiring.

4 Implementation Details

In this section we overview some technical details of the search engine, that is how we have implemented constraints and heuristics. Gecode supports the development of new constraints, branching strategies, and search engines. Constraints can be de ned over Integers, Booleans, Sets, and Floats. In the following, args[] is the array of Boolean variables (i.e., instances of the class BoolVar ) that represents the whole set of arguments Args ; Boolean variables can only take 0 or 1 values (i.e., two integer values). An array of Boolean variables can be created with BoolVarArray args[](space, |Args |, 0, 1), where space is the associated search-space.

7 https://sourceforge.net/projects/probo/.

#i n c l u d e "AFEngine . h" AFEngine a f = new AFEngine ( ) ; s t r i n g sFileName1 = " f i l e . apx " ; af >L o a d F i l e ( sFileName1 ) ; s e t <t S o l u t i o n > t s e t S o l = af >GetAdmissibleEnum ( ) ; af >P r i n t S o l ( t s e t S o l ) ; cout << af >G e tS o l u t i on s C o u nt ( t s e t S o l ) << " s o l u t i o n ( s ) found " << e n d l ; af >F r e e S o l ( t s e t S o l ) ;

Constraints for modelling con ict-free-sets are based on the rst order logic formula @a; b P Aarg s.t. Rpa; bq, then a ñ b (¡¡ is the implication operator in Gecode): r e l ( space , a r g s [ i ] >> ! a r g s [ j ] )

The procedure to enforce the constraints for modelling admissibility rst sets con ict-free constraints, and then checks if at least one defender (c) of each attacker (b) of a is true, i.e., taken in an extension together with a: @a; b; c P Aarg then a ñ ™ p š cq. In this case, we deal with two di erent cases: when pb;aqPR pc;bqPR an argument args[i] is attacked but has no defender, then it has not to be taken (IRT EQ imposes equality, with 0 in this case): r e l ( space , a r g s [ i ] , IRT EQ , 0 , IPL SPEED )

Otherwise, if an argument has at least one defender, then we use the clause constraint, where c is a Boolvar array that represents all the arguments ci that defend a from each attacker b, and such a clause constraints models a _ š ci ciPc c l a u s e ( s p a c e , BOT AND, a , c , 0 ) elled as

IPL SPEED is a Gecode ag set to optimise propagation for execution performance, at the expense of memory use.

Constraints for stable extensions are obtained by imposing admissible constraints and enforcing the formula @a P Args , then a ô ™ b. This is modpb;aqPR r e l ( s p a c e , m bvaArgs [ i ] , IRT EQ , 1 ) in case args[i] is never attacked (then it has to be taken). Otherwise, if args[i] has one or more attackers the constraint is l i n e a r ( s p a c e , a , x , IRT GR , 0 ) ;

Given a rargsris; b1; : : : ; bns, where bi; : : : bn are the n attackers of args[i], the previous constraint enforces argsris x1 b1 xn bn ¡ 0; in this case, x is a vector of weights all set to 1 (with size n 1). Hence, either an argument a or at least one of its attackers bi have to be true.

We now introduce how we enumerate and verify preferred extensions. First of all, we set the constraints to nd admissible sets, including constraints for con ict-freedom. Afterwards, we use the following branching strategy: branch ( s p a c e , a r g s , INT VAR DEGREE MAX( ) , INT VALUES MAX ( ) ) ;

During search, at each step such a strategy selects the variable with the highest degree (i.e., the number of dependant propagators) and tries to assign it to true. This last condition automatically leads to nding a preferred extension: Proposition 1 (Branching for preferred). By imposing only constraints to nd admissible sets, a branching strategy INT VALUES MAX always terminates with a preferred extension.

This approach incrementally builds an extension by adding as more (\admissible") arguments as possible: eventually, it is not possible to nd an admissible set that includes it.

In order to enumerate all preferred extensions, it is enough to i) launch the search using Prop. 1, ii) record the obtained solution, iii) remove it from the set of possible future solutions, and iv) restart search. The i-iv loop is terminated when no further solution is found. To verify if a given set B is a preferred extension, we set admissible constraints, and then we use Prop. 1 by rst assigning to true all the arguments in B. As soon as we nd a solution di erent from B, then we obtain that B is not a preferred extension. Constraints for WAAFs in Sec. 2.3 are similar to the ones proposed in this section for classical Abstract Argumentation [ 12 ]: in addition, we add some more constraints to limit the internal inconsistency and the di erence between attack and defence weights to be less than resp. and . In the following piece of code, the rst constraint binds extensionCost to the aggregation (parametric w.r.t. the chosen semiring) of the weights of all attacks \active" in the considered set of arguments. Then, still depending on the semiring, such a value is compared against : r e l ( space , e x t e n s i o n C o s t == s e m i r i n g T i m e s O p e r a t i o n ( a c t i v e A t t a c k s ) ) ; i f ( m s t r u c t >GetSemiringType ( ) == WEIGHTED) r e l ( space , e x t e n s i o n C o s t , FRT LQ, alpha ) ; i f ( m s t r u c t >GetSemiringType ( ) == FUZZY) r e l ( space , e x t e n s i o n C o s t , FRT GQ, alpha ) ;

Concerning -defence (see Def. 18), the of all the attackers (A) and defenders (B) of an argument is computed and compared against . Expr posts a Boolean expression and returns its value, which is then checked to be true: expr ( space , SemiringXAIsGammaWorseEqualThanXB (B, A) ) ; i f ( m s t r u c t >GetSemiringType ( ) == WEIGHTED) expr ( space , ( SemiringXOperation (B) SemiringXOperation (A) ) <= gamma) ; i f ( m s t r u c t >GetSemiringType ( ) == FUZZY) expr ( space , ( SemiringXOperation (B) SemiringXOperation (A) ) >= gamma) ; 5

Conclusion

We have presented ConArgLib, a C++ software library designed to o er to the end user functions to solve classical tasks in Abstract Argumentation: extension enumeration, existence, and veri cation, and credulous/sceptical acceptance of arguments. The engine at the core of the library o ers good performance, and is the rst attempt to provide such functionalities as a software library.

In the future, we plan to extend the library by providing higher-level functions, e.g., to check if two frameworks are equivalent on some given semantics. Moreover, we would like to implement a recent di erent de nition of grounded semantics for semiring-based WAAFs [ 7 ], which, contrarily to all the other proposals in the literature for Weighted Argumentation Frameworks, always returns one extension as result, as in the classical formulation [ 12 ]. Finally, we will implement coalition-based extensions [ 4 ] and voting systems as in [ 1 ].

References

1. Benedetti , I. , Bistarelli , S. : From argumentation frameworks to voting systems and back . Fundam. Inform . 150 ( 1 ), 25 { 48 ( 2017 )

2. Bistarelli , S. , Rossi , F. , Santini , F. : A relaxation of internal con ict and defence in weighted argumentation frameworks . In: European Conference on Logics in Articial Intelligence, JELIA. LNCS , vol. 10021 , pp. 127 { 143 . Springer ( 2016 )

3. Bistarelli , S. , Santini , F. : Conarg: A constraint-based computational framework for argumentation systems . In: International Conference on Tools with Arti cial Intelligence . pp. 605 { 612 . ICTAI '11, IEEE Computer Society ( 2011 )

4. Bistarelli , S. , Santini , F. : Coalitions of arguments: An approach with constraint programming . Fundamenta Informaticae 124 ( 4 ), 383 { 401 ( 2013 )

5. Bistarelli , S. , Montanari , U. , Rossi , F. : Semiring-based constraint satisfaction and optimization . Journal of the ACM 44 ( 2 ), 201 { 236 ( 1997 )

6. Bistarelli , S. , Rossi , F. , Santini , F. : A collective defence against grouped attacks for weighted abstract argumentation frameworks . In: Florida Arti cial Intelligence Research Society Conference, FLAIRS . pp. 638 { 643 . AAAI Press ( 2016 )

7. Bistarelli , S. , Santini , F. : A Hasse diagram for weighted sceptical semantics with a unique-status grounded semantics . In: Logic Programming and Nonmonotonic Reasoning , LPNMR. LNCS , vol. 10377 , pp. 49 { 56 . Springer ( 2017 )

8. Blyth , T.S. , Janowitz , M.F. : Residuation theory , vol. 102 . Pergamon press Oxford ( 1972 )

9. Caminada , M. : Comparing two unique extension semantics for formal argumentation: ideal and eager . In: Belgian-Dutch conference on arti cial intelligence (BNAIC) . pp. 81 { 87 ( 2007 )

10. Caminada , M. : Semi-stable semantics . In: Computational Models of Argument: Proceedings of COMMA 2006. Frontiers in Arti cial Intelligence and Applications , vol. 144 , pp. 121 { 130 . IOS Press ( 2006 )

11. Charwat , G. , Dvorak , W. , Gaggl , S.A. , Wallner , J.P. , Woltran , S. : Methods for solving reasoning problems in abstract argumentation: A survey . Arti cial Intelligence 220 ( 0 ), 28 { 63 ( 2015 )

12. Dung , P.M. : On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games . Arti cial Intelligence 77 ( 2 ), 321 { 357 ( 1995 )

13. Dung , P.M. , Mancarella , P. , Toni , F. : A dialectic procedure for sceptical, assumption-based argumentation . In: Proceedings of the 2006 conference on Computational Models of Argument (COMMA) . pp. 145 { 156 . IOS Press ( 2006 )

14. Dunne , P.E. , Hunter , A. , McBurney , P. , Parsons , S. , Wooldridge , M. : Weighted argument systems: Basic de nitions, algorithms, and complexity results . Artif. Intell . 175 ( 2 ), 457 { 486 ( 2011 )

15. Dunne , P.E. : The computational complexity of ideal semantics . Artif. Intell . 173 ( 18 ), 1559 { 1591 ( 2009 )

16. Dvorak , W.: Computational Aspects of Abstract Argumentation . Ph.D. thesis , Technische Universitat Wien ( 2012 ), http://permalink.obvsg.at/AC07812708

17. Kroll, M. , Pichler , R. , Woltran , S. : On the complexity of enumerating the extensions of abstract argumentation frameworks . In: International Joint Conference on Arti cial Intelligence , IJCAI . pp. 1145 { 1152 . ijcai. org ( 2017 )

18. Rossi , F., van Beek , P. , Walsh , T. : Handbook of Constraint Programming. Elsevier Science Inc ., New York, NY, USA ( 2006 )

19. Thimm , M. , Villata , S. , Cerutti , F. , Oren , N. , Strass , H. , Vallati , M. : Summary report of the rst international competition on computational models of argumentation . AI Magazine 37 ( 1 ), 102 ( 2016 )

20. Verheij , B. : Two approaches to dialectical argumentation: admissible sets and argumentation stages . Dutch Conference on Arti cial Intelligence 96 , 357 { 368 ( 1996 )