RAFDivider: a distributed algorithm for computing semantics in higher-order abstract argumentation frameworks

ABSTRACTThis work is related to a computational issue concerning an enriched abstract argumentation framework called RAF (‘Recursive Argumentation Framework’). A RAF is composed of a set of arguments and of a binary relation which models the attacks as in Dung's seminal argumentation framework. The main difference between Dung's framework and a RAF is the fact that a RAF is able to take into account higher-order interactions (i.e. an attack can target an attack and not only an argument). This kind of framework is recent enough for an efficient computation of its main semantics to remain an open question. In this paper, we propose one of the first algorithms dedicated to this issue, RAFDivider. We prove its soundness and its completeness.KEYWORDS: Abstract argumentationhigher-order interactionsalgorithms AcknowledgmentsThe authors wish to thank Mickaël Lafages, the work of this article being mostly based on his PhD Thesis.Disclosure statementNo potential conflict of interest was reported by the author(s).Notes1 The International Competition on Computational Models of Argumentation: http://argumentationcompetition.org.2 Even if some works had been done for some limited versions of higher-order frameworks, see for instance Dvorák et al. (Citation2015).3 Whereas an extension assigns an accepted or a rejected status to its elements, a labelling considers a third status, undecided, which applies to arguments which are neither accepted, nor rejected. This enrichment has proven useful for the computation of acceptance statuses in AFs (see Charwat et al., Citation2015 for a survey).4 An interesting result given by Doutre et al. (Citation2020), Doutre et al. (Citation2022) is: even if the expressive power of the frameworks with higher-order attacks is higher, the complexity of their decision problems keeps the same as in AFs.5 This extended version explains several technical details of the approach and gives the complete proofs of each result. Moreover, some additional examples are provided for a better illustration of this approach.6 We write ⊆-maximal.7 Note that, in a reinstatement labelling, for any argument a∈{und}(ℓ), a is also legally {und} (this is obviously implied by Definition 2.8).8 This notion of largeness of an AF is not so simple to define. It is related to the fact that the computation of the solutions is complex either because of the number of arguments, or of the number of interactions, or because of the structure of the AF.9 Notice that in the literature it is the decision problem versions of this problem that are mainly studied, but approaches also concern the enumeration problem in AFs, e.g. Kr&orrddquote;oll et al. (Citation2017). Nevertheless, the complexity of their decision versions is sufficient to give a good idea of their hardness. See Dvorak and Dunne (Citation2018) for an overview.10 A graph is said to be sparse when its density is low.11 Relations between labelling-based semantics and structure-based semantics have been exhibited in Doutre et al. (Citation2020).12 Note that, following this definition, a stable structure is also conflict-free.13 The original definition for the RAF labelling given by Doutre et al. (Citation2020) is a pair of a labelling over arguments and of a labelling over attacks. Here we give an equivalent definition that does not make a difference between arguments and attacks. Moreover, we also simplify the terminology using ‘labelling’ instead of ‘structure labelling’.14 So the following property holds for Ω: ∀(i,j)∈{1,…,n} s.t. i≠j,ωi∩ωj=∅ and ⋃i=1nωi=A∪K.15 ↓ is the classical generic operator of restriction that allows the selection of a sub-part of a given ‘object’ wrt to a given set of ‘elements’. Here, for instance, it produces the sub-part of the labellings concerning only the elements belonging to A~∪K~.16 See in Lafages (Citation2021) the details about the method for defining the SCC of a RAF.17 The definition for the non-directed case implies additional constraints given between brackets.18 This is not a directed RAF-path since we do not ‘follow the arrows’.19 The enumeration problem consists in computing all the solutions under a given semantics of a given framework.20 Indeed, let us consider α being an attack in Qtriv s.t. its target is in RAF~hard; either α is labelled with {out} or α is labelled with {in} and its source is either labelled with {in} or {out}: in any case, the fact that its target is in RAF~hard shows that α is useless for determining the label of its target.21 This is a difference with AFDivider that has been designed originally for using a specific clustering method, see Doutre et al. (Citation2019).22 raf~2↓ω1 produces a partial RAF built from raf~2 keeping only the elements of ω1.23 Obviously, each context of a partial RAF will induce a specific set of labellings of this partial RAF.24 The third optimisation allows to decrease the number of contexts to consider (see Appendix 1 for more details).25 A CSP (Constraint Satisfaction Problem) is a problem defined by a set of variables, a set of domains (one domain per variable giving the values that are authorised for this variable) and a set of constraints expressing the fact that some values for some variables are incompatible with some values of other variables. The main aim of a CSP is to find an assignment in which each variable is assigned with a value of its domain and this assignment must satisfy all the constraints. The interested reader can find more details in the seminal work (Montanari, Citation1974).26 Note that this CSP contains two types of variables: one variable for each cluster and one variable for each input of these clusters. The domains of these variables correspond to their possible labellings. The constraints express the links between the labellings of the clusters and the labellings of their inputs.27 See in Lafages (Citation2021) the details about the definition of the SCCs for a RAF.28 Among the methods proposed in Lafages (Citation2021), there is also a method that does not satisfy the fact that the SCCs are not split into several clusters (that is the method inspired from the spectral clustering); so this method is not considered here.29 As an example the set of labellings of the unique standard RAF of component raf~4 is the following: {{(g,out),(n,und),(o,und),(aζ,in),(aρ,in),(aυ,und),(τ,und),(υ,in),(ϕ,in),(χ,in),(αg,in),(αθ,in)}}30 L2.2.1 corresponds to μ2.2.2; L2.2.2 to L2.2.4 correspond to μ2.2.1; L2.2.5 to L2.2.6 correspond to μ2.2.3.31 The proof is given in Appendix 2.