This paper builds on a general model for the investigation on decomposability in abstract argumentation, i.e. the possibility of determining the labellings prescribed by a semantics based on evaluations of local functions in subframeworks. A constructive procedure for identifying local functions is devised, able to enforce decomposability whenever the semantics is decomposable. In particular, two kinds of local functions are identified, and some of their properties are analyzed.
(M. Giacomin) under some mild constraints. On this basis, the property of decomposability of argumentation semantics has been introduced concerning the correspondences between semantics outcome at global and local level. A semantics is decomposable if, given a partition of an argumentation framework into a set of sub-frameworks, the outcomes produced by the semantics can be obtained as a combination of the outcomes produced by a local function applied separately on each sub-framework, and vice versa.
A central issue is therefore how to determine a local function for a given argumentation semantics, able to guarantee decomposability if the semantics and the local information exploited make it possible. In this regard, the paper aims at providing some general results that do not rely on specific semantics definitions. To this purpose, it introduces a constructive procedure based on the selection of argumentation frameworks, where the output of the local function can be determined by applying the semantics at hand. This model is shown general enough to encompass two kinds of local functions, both of them enforcing decomposability if possible.
After some background on Dung’s model provided in Section 2, Section 3 describes the general model for decomposability introduced in [16]. The constructive procedure is then introduced in Section 4. Section 5 exploits this procedure to devise the canonical local function for a semantics, which enforces decomposability whenever possible. Section 6 identifies an alternative ’light’ local function, which achieves the same result under some constraints concerning in particular the local information available. Section 7 concludes the paper. The proofs of the results already published in [16] are not reported, while all the proofs in this paper concern novel results.
We follow the traditional definition of argumentation framework [ 1] and define its restriction to a subset of arguments.
Definition 1. An argumentation framework is a pair = ( , att) in which is a finite 1 set of arguments and att ⊆ × . Given a set Args ⊆ , the restriction of to Args, denoted as ↓ Args, is the argumentation framework (Args, att ∩ (Args × Args)). The (infinite) set of all possible argumentation frameworks is denoted as SAF .
Given two argumentation frameworks 1 = ( 1, att1) and 2 = ( 2, att2): • 1 ⊆ 2 if 1 ⊆ 2 and att1 ⊆ att2 • 1 ⊑ 2 if 1 ⊆ 2 and 2↓ 1 = 1 • 1 ⊖ 2 ≜ 1 ⧵ 2 • 1 ⧵ 2 ≜ 1↓ 1⊖ 2
The relation ⊆ extends set inclusion to argumentation frameworks, while 1 ⊑ 2 holds if 1 is a subframework2 of 2. In this case, 2 ⊖ 1 returns the set of arguments of 2 outside 1, while 2 ⧵ 1 returns the corresponding argumentation framework. 1In the general definition, the set of arguments may be infinite.
2It is immediate to see that ⊑ is stricter than ⊆, i.e. 1 ⊑ 2 entails 1 ⊆ 2.
In this paper we adopt the labelling-based approach to the definition of argumentation semantics. A labelling assigns to each argument of an argumentation framework a label belonging to the set {in, out, undec}, where the label in means that the argument is accepted, the label out means that the argument is rejected, and the label undec means that the status of the argument is undecided. For technical reasons, we define labellings both for argumentation frameworks and for arbitrary sets of arguments.
Given a set of arguments Args, a labelling of Args is a total function Lab ∶ Args → {in, out, undec}. The set of all labellings of Args is denoted as Args. Given an argumentation framework = ( , denoted as ( ) att), a labelling of
is a labelling of . The set of all labellings of . For a labelling Lab of Args, the restriction of Lab to a set of arguments Args′ ⊆ is Args, denoted as Lab↓Args′, is defined as Lab ∩ (Args′ × {in, out, undec}). We extend this notation Moreover, if Lab ∈ ( ) to sets of labellings, i.e. given a set of a labellings ⊆ ′ = ( ′, att′), Lab↓ ′ will denote Lab↓ ′.
Args, ↓
Args′ ≜ {Lab↓Args′ ∣ Lab ∈ } .
A labelling-based semantics prescribes a set of labellings for each argumentation framework.
Given an argumentation framework = ( , att), a labelling-based semantics S a subset of ( ) , denoted as LS( ) .
associates with reader to [1, 17].
For ease of notation, in the following LI ( will be denoted as LI ∗( ) . 3. A General Model for Studying Decomposability The model proposed in [16] for the analysis of decomposability of argumentation semantics can be articulated in two layers. The first layer deals with the modelling of the information locally used for the computation of labellings in subframeworks, the second layer represents this computation through the notion of the local function. 3.1. Local Information Function and Argumentation Framework with Input Let us consider an argumentation framework ∗ and a subframework ∶ ⊑ ∗. The information needed for the local computation of the labellings in should include the topology of the subframework itself, but also some knowledge of the topology of the neighboring part of the graph, as well as the labelling assigned to this part by the local computations on external subframeworks. The notion of local information function is able to model diferent kinds of A local information function is a function LI ∶ {( ∗, ) ∣ ∗, ∈
SAF ∧ ⊑ available topological information.
Definition 5. ∗ } → SAF such that ∀ • ⊑ • if ∗
LI ( ∗ ⊆ ∗ , ∈ and LI (
In the first item of the above definition, ⊑ LI ( ∗, ) signifies that the local subframework must be known, while LI ( ∗, ) ⊆ ∗ expresses that the neighboring part of returned by the function is taken from ∗. For instance, only external attackers with the relevant attacks might be available (while the reverse attacks might be unknown), or we can have also information about the attacked external arguments and the relevant bidirectional attacks. The second item is meant to avoid implicit information hidden in the way the output of the function is selected depending on ∗. To avoid this possibility, the constraint requires that if ∗ is enlarged, then either the output of LI does not change, or the additional elements of the enlarged global framework play an explicit role, i.e. some appear in the novel output of the local information function. In [16] it is shown that Definition 5 is able to model many diferent kinds of local information available (see also Example 1 below).
The information available for a specific subframework of a given framework is represented by an argumentation framework with input.
SAF such that ⊑ ′, and Lab ∈ ′⊖ . ′, Lab) where , ′ ∈ ( , LI , ∗.
Intuitively, represents a subframework, ′ represents the portion of the global argumentation framework which is taken into account, including itself, while Lab is the labelling externally assigned to arguments in ′ ⊖ , i.e. belonging to the neighboring part of the subframework.
An argumentation framework with input can be derived by applying a local information function LI to a subframework of a global argumentation framework ∗. If there is an argumentation framework ∗ where this is possible, the argumentation framework with input is said to be derived from LI .
Definition 7. An argumentation framework with input ( , ′, Lab) is derived from a local information function LI in ∗, written ( , ′, Lab) ∈ LI , ∗, if ′ = LI ∗( ) . ′, Lab) is derived from LI , written ( , ′, Lab) ∈ LI , if ∃ ∗ such that ( ,
While in Definition 7 the labelling component of argumentation frameworks with input is not constrained, the notion of realizability introduced in the following definition requires the labelling component to be enforced by a labelling prescribed by the semantics. Definition 8. An argumentation framework with input ( , ′, Lab) is realized from a local information function LI in an argumentation framework ∗ under a semantics S, written ( , ′, Lab) ∈ LI , ∗,S, if ( , ′, Lab) ∈ LI , ∗ and ∃Lab∗ ∈ LS( ∗) such that Lab∗↓ ′⊖ = Lab. ( , ′, Lab) is realized from a local information function LI under a semantics S, written ( , ′, Lab) ∈ LI ,S, if ∃ ∗ such that ( , ′, Lab) ∈ LI , ∗,S. Example 1. Suppose that the available external information for any subframework includes the outside attackers and the unidirectional attacks from them to . The relevant local information function LI can be defined as follows. First, given ∗ = ( ∗, att∗) ∈ SAF and Args ⊆ ∗, Args ∗ ≡ { ∈ ∗ ⧵ Args ∣ ∃ ∈ Args, (, ) ∈ att∗} and Args − ∗ = att∗ ∩ (Args ∗ × Args). Then, for any ( ∗
SAF ∧ ⊑ ∗, with = ( , att), LI ∗
∗( ) ≡ ( ∪
Now, consider is derived from holds ( , ∗, att ∪ − ∗
). ∗ = ({, , , 1, 2}, {(, ), (, ), (, ′ = ({, , 1), ( , 1), ( 1, 2), ( 2, 1)}) and = 1, 2}, {(, 1), ( , 1), ( 1, 2), ( 2, 1)}). ↓{ 1, 2}. We have that The example also shows that e.g. the argumentation framework with input ( , ′, {(, in), ( , in)}) to include also attack between external attackers, this would not hold since most semantics prohibit conflicting arguments ( and in this case) from being all labelled in.
LI . Under most semantics S (e.g. the grounded or preferred semantics [1]) it also ′, {(, in), ( , in)}) ∈
LI ,S. However, if we change the definition of
LI so as 3.2. Local Function and Decomposability
LI a (possibly empty) set of labellings of , i.e. ( , ′, Lab) ∈ 2( ) .
A local function represents a local counterpart of the notion of semantics. It takes as input an argumentation framework with input (rather than a standard argumentation framework) and produces as output a set of labellings for the inner local argumentation framework. Definition 9. A local function for a local information function LI assigns to any ( ,
correspond to the possible combinations of compatible labellings obtained by applying a local function in the subframeworks that partition the global framework.
A local function for a local information function LI enforces decomposability of a semantics S under LI if for every argumentation framework = ( , every partition = { 1, … , } of , the following condition holds: LS( ) = { att) and for 1 ∪ … ∪ ∣ ∈ (↓ )}. A semantics S is decomposable (or equivalently fully decomposable) under LI if there is a local function which enforces decomposability of S under LI .
In Definition 10, (↓ is the labelling assigned to the locally known arguments outside the subframework ↓ those included in the set LI (↓ ) ⊖ ↓
. Compatibility refers to the fact that any labelling of a subframework is used by to compute other labellings in other subframeworks. More specifically, each local labelling depends on the other ones since the labelling component taken as input by is obtained from the labellings (with ≠ ) computed in external subframeworks. , i.e.
A local function for a local information function LI enforces top-down decomposability of a semantics S under LI if for every argumentation framework = ( , att) and for every partition = { 1, … , }, it holds that LS( ) ⊆ { 1 ∪ … ∪ ∣ ∈ (↓ tion function LI enforces bottom-up decomposability of a semantics S under LI if for every )}. A local function for a local informaargumentation framework = ( , LS( ) ⊇ { att) and for every partition = { 1, … , }, it holds that means of is complete, i.e. all labellings prescribed by S for are obtained by applying to the subframeworks corresponding to the partition and combining the relevant labellings. On the other hand, enforces bottom-up decomposability if the procedure is sound, i.e. all combinations of local labellings obtained by give rise to global labellings that are valid according to S. It is easy to see that a semantics is decomposable under LI if there is a local function for LI which enforces both top-down and bottom-up decomposability of S under LI . 4. A Constructive Procedure for Local Functions Once the general model has been designed, the next issue is to identify a local function for any argumentation semantics S and local information function LI .
investigate its decomposability properties under LI . Then, if the semantics turns out to be decomposable, one may determine a local function which enforces full decomposability under LI , while in the other case one may identify a local function satisfying some desired properties, e.g. achieving full decomposability under LI w.r.t. specific kinds of partitions. In order to provide a sort of guidance to this activity which is valid independently of the specific semantics definitions, we aim at identifying an expression of the local function which is parametric w.r.t. the semantics, and thus does not rely on the properties of a specific semantics.
The expression of the local function is based on the following considerations. First, given an argumentation framework with input ( , set of labellings returned as output by the local function on the basis of the semantics S (given as a parameter) is to apply S to a set of argumentation frameworks. Since the set of labellings ∗ from LI ,
= Lab)
LI , the only way to determine the , each of these argumentation frameworks ∗, and the returned labellings are obtained ∗) to . Moreover, taking into account the role
′, Lab) has to be realized in ∗) compatible with Lab (i.e. such that Lab∗↓ ′⊖ of returned by the local function is contained in ( ) ∗ must have
as a subframework, i.e. ⊑ and only the labellings Lab∗ ∈ LS( should be taken into account. by restricting (some of) the labellings in LS(
′ and Lab, the argumentation with input ( ,
LI , we introduce the notion of standard argumentation framework function, which associates to any argumentation framework with input derived from LI a (possibly empty) set of argumentation frameworks in which this argumentation framework with input is realized.
Given a local information function LI , a standard argumentation framework function for LI is a (possibly partial) function which associates to any pair including a semantics S and an argumentation framework with input ( , mentation frameworks, denoted as
S,LI ( , ′, Lab), such that ′, Lab) ∈ LI , a set of argu ,S,LI ( , functions and generated local functions holds.
2 ,S,LI ( , function.
′, Lab) includes a single framework or it is empty. LI , ∗,S}. A standard argumentation framework function for LI is finite if, ′, Lab) ∉ LI ,S then ′, Lab) is not defined, i.e. returns Intuitively, the aim of
′, Lab) is to provide a set of argumentation frameworks ’representing’ all argumentation frameworks where the argumentation framework with input
′, Lab) can be realized, meaning that such a set is suficient to construct the output of a local function . In particular, given a standard argumentation framework function for LI , for any semantics S a corresponding local function for LI can be generated as in the following
Given a standard argumentation framework function for a local information function LI and a semantics S, the local function generated by for S and LI , denoted as ,S,LI , is the local function for LI such that for any ( ,
It is easy to see that a monotonic relation between standard argumentation framework either
S,LI ( ,
Note that if ( , the empty set. definition.
Definition 13.
⋃ ∗∈ 1 S,LI ( , ′,Lab) {Lab∗↓ ∣ Lab∗ ∈ LS( given a semantics S, if 1 S,LI ′, Lab) ⊆ 2 S,LI Proposition 1. Given two standard argumentation framework functions 1 and 2 for LI and ′, Lab) then 1 ,S,LI ( ,
Let us now turn on two possible requirements for a standard argumentation framework First, constructing a local function on the basis of a standard argumentation framework function is easier if the latter is finite. Luckily, since we deal with finite argumentation frameworks, for any generated local function there is always a finite standard argumentation framework function which generates it.
Proposition 2. Given a standard argumentation framework function 1 for a local information function LI and a semantics S, there exists a finite standard argumentation framework function 2 for LI which generates 1 ,S,LI . the output of 1 ,S,LI ( , Proof. We construct 2 as follows. According to Definition 13, for any ( , ′, Lab) can be expressed as Since the number of possible labellings of , i.e. the cardinality of ( ) , is 3 where is the number of arguments in , obviously the number of distinct labellings Lab∗↓ in the set above is finite as well. Thus there is a finite set of argumentation frameworks, that we let as 2 S,LI This corresponds to our desired 2 (see Definition 13).
Let us now turn to the second requirement. Since by definition a decomposable semantics S under a local information function LI admits a (possibly singleton) set of local functions that enforce decomposability of S under LI , failing to capture all of them would not be acceptable for the above construction mechanism. This is expressed by the following definition.
A standard argumentation framework function for LI is adequate if, for every decomposable semantics S under LI , ,S,LI enforces decomposability of S under LI .
An adequate standard argumentation framework function is pivotal for investigating the decomposability property of a semantics S, since it allows one to select without loss of generality the local function in the condition of Definition 10. In particular, since by Definition enforces decomposability of S if the latter is fully decomposable under a local information function LI , the proof that S is fully decomposable under LI can focus on this condition with = ,S,LI . Conversely, in order to show that a semantics is not decomposable it is suficient to identify an argumentation framework and a partition where the same condition is not satisfied 14 ,S,LI by ,S,LI .
12 and 13 or, more generally, the underlying assumptions introduced above, are general enough to capture useful local functions, i.e. whether there is (at least) one adequate standard argumentation framework function. In the next sections we provide a positive answer to this question.
In this section we consider a particular choice of a standard argumentation framework function, motivated by the fact that any local function enforcing decomposability must include as output, for any the subframework . This is shown in the following proposition.
LI , ∗,S, the restriction of the labellings of framework such that Lab∗↓ Lab∗↓
′, Lab).
Proposition 3. Let S be a fully decomposable semantics under LI , and let ( , be an argumentation framework with input derived from LI . Let = Lab. Then, for any local function which enforces decomposability of S under LI , LI
We should note that the reverse of the above proposition does not hold, i.e. may require additional labellings w.r.t. those mentioned in the proposition. A labelling included in ( , ′, Lab) may not play a role in forming the labellings of ∗ due to the compatibility conditions, but it may be required in a diferent argumentation framework. This suggests adopting the following definition of the canonical local function, which includes all possible labellings that play a role in some argumentation framework.
Given a semantics S and a local information function LI , the canonical local function SLI of S associated to LI is defined as follows. For any ( , SLI ( , LI, ∗,S
It is easy to see that the canonical local function of a semantics S associated to LI is the local function generated by the maximal standard argumentation framework function for S and LI , i.e. returning as output all of the argumentation frameworks enforces top-down decomposability of S under LI , as shown in the following proposition. LI , ∗,S (see Definition 12 and Definition
13). SLI (↓ Lab↓LI (↓ )⊖↓ Proposition 4. For any semantics S and local information function LI , the canonical local function SLI enforces top-down decomposability of S under LI .
Proof. According to Definition 11, we have to prove that for every = ( , att), for every = Lab↓ . It holds that Lab = 1 ∪…∪ , thus, for any , (⋃=1…,≠ 1, … , } and for any labelling Lab ∈ LS( ) . As a consequence, we have to prove that for any ∈ {1, … }
). According to the definition of canonical local ∗ and a labelling Lab∗ ∈ LS( ∗) such that LI ∗(↓ ) = LI (↓ ), Lab∗↓↓ function (see Definition
15) this amount to prove that there is an argumentation framework and Lab∗↓LI (↓ are satisfied by selecting assumption, LI (↓ )⊖↓ = Lab↓LI (↓ ∗ = and Lab∗
) is trivially satisfied, the third condition holds since Lab↓↓ = Lab↓ , and finally the last condition trivially holds since Lab∗ = Lab.
While top-down decomposability holds for all semantics, i.e. the output of the canonical local function is suficient to cover all global labellings, the following proposition shows that the output of the canonical local function is necessary to enforce decomposability whenever this is possible, i.e. if the semantics is fully decomposable.
Proposition 5. Let S be a decomposable semantics under LI and let be a local function which ( ,
′, Lab). enforces decomposability of S under LI . Then, ∀( , ability of all decomposable semantics.
The reverse of this proposition does not hold, since a local function enforcing decomposability can prescribe for a subframework spurious labellings that are not compatible with those of the other subframeworks, and thus do not alter the set of labellings obtained by joining the results
The above results are suficient to show that the canonical local function enforces decomposProposition 6. If a semantics S is fully decomposable under a local information function LI , then SLI enforces decomposability of S under LI .
According to Proposition 5, the canonical local function of a decomposable semantics S associated to LI is the minimal (w.r.t. ⊆) local function enforcing decomposability. 6. Reduced Canonical Local Functions As mentioned in the previous section, Proposition 3 identifies an argumentation framework ∗ and a relevant set of labellings that are necessary to enforce decomposability. On the other hand, in general a single argumentation framework is not suficient, i.e. diferent argumentation frameworks may have to be identified in order to determine the whole set of labellings returned as output by the canonical local function for a given argumentation framework with input.
Let S be a semantics, LI a local information function and ( , an argumentation framework with input derived from LI . An argumentation framework LI ∗ , ∃Lab′1 ∈ LS( LI under S and LI , written
.
, which corresponds to a kind of unidirectional local information function, is influenced by (part of) and the relevant labelling, the reverse does not hold. Thus, the role of
The next proposition shows that the reverse of Proposition 3 holds if the conditions of
Proposition 7. Let S be a fully decomposable semantics under LI , and let ( , be an argumentation framework with input derived from LI . Let LI = ′, Lab). Then, for any local function which enforces ′, Lab) = {Lab∗↓ ∣ Lab∗ ∈ LS( As to the reverse direction of the proof, let us first consider the partition of ∗ identified by the subframeworks and . Since by the hypothesis enforces decomposability ∗⧵ ,
LI ∗(
∗⧵ ), )}. Since LI ∗( ∗ ⧵ ) = ∅ ∗ ↓
∗⊖ Lab2↓LI
= ∗( Let us then consider a labelling Lab′2 ∈ ( ,
= Lab and Lab′2 = Lab∗′↓ . in turn all the relevant arguments), from Lab′1 ∈ LS( = Lab. Moreover, since enforces decomposability of S under LI , considering and the partition including a single set (which includes
In order to exploit Proposition 7 to identify a local function generated by a unitary standard argumentation framework function, we need a number of preliminary definitions.
′, Lab) we need to focus on the pair ( ′ ⧵ ,
the role of the ‘input pair’ afecting the local computation of labellings in . Accordingly, we introduce the following definition of a pair derived from a local information function LI .
Given a local information function LI , a pair ( , Lab) (where ∈ SAF and )) is derived from LI , written ( , Lab) ∈ LI , if ∃( ,
A pair is representable if every relevant argumentation framework with input can be represented by an argumentation framework.
Given a semantics S and a local information function LI , a pair ( , Lab) ∈ LI is representable under S and LI , written ( such that ′ ⧵ = , ∃ ∗ ∈ , Lab) ∈ S ,LI , if for every ( ,
Similarly to the case of a realized argumentation framework with input (see Definition 8), we introduce the notion of realizability of a pair under a semantics. S , if ∃ ∗ ∈ SAF such that ⊆ ∗ and ∃Lab∗ ∈ LS( ∗) such that Lab∗↓ Definition 19. Given a semantics S, a pair ( , Lab) is realized under S, written ( , Lab) ∈ = Lab.
In words, there must be an argumentation framework where appears as a potential external information for a subframework, and the semantics enforces the labelling Lab in .
Proposition 8. Given a semantics S, a local information function LI and a pair ( , Lab) ∈ LI , if ( , Lab) ∈ S ,LI , then ( , Lab) ∈ S .
Proof. By Definition 17, ∃( , ′, Lab) ∈ LI such that ′ ⧵ = . Since ( , Lab) ∈ S ,LI , by Definition 18 ∃ ∗∗ ∈ SLI ( , ′, Lab). Taking into account Definitions 16 and 5, we have in particular ⊑ ∗∗, ′ ⊆ ∗∗, and ∃Lab′1 ∈ LS( ∗∗ ⧵ ) with Lab′1↓ ′⊖ = Lab. Letting ∗ = ∗∗ ⧵ and Lab∗ = Lab′1, it must be the case that ′ ⧵ ⊆ ∗, i.e. ⊆ ∗, and ∃Lab∗ ∈ LS( ∗) with Lab∗↓ ′⊖ = Lab∗↓ = Lab. According to Definition 19, ( , Lab) ∈ S .
On the basis of Proposition 7, if all pairs are representable (and thus realized) then it is possible to construct a local function by means of a unitary standard argumentation framework function. However, this requirement may be impossible to achieve just because of pairs that are not realized under the semantics (and thus cannot be representable). Then, a weaker requirement is that realized pairs are representable. We introduce accordingly the following definition. Definition 20. A semantics S is representable w.r.t. a local information function LI if for every ( , Lab) ∈ LI , it holds that ( , Lab) ∈ S ,LI , i.e. every pair is representable. A semantics S is weakly representable w.r.t. LI if for every ( , Lab) ∈ LI such that ( , Lab) ∈ S , it holds that ( , Lab) ∈ S ,LI , i.e. every realized pair is representable.
Example 2. Consider the local information function LI as defined in Example 1. By definition of LI , any pair ( , Lab) ∈ LI involves only initial nodes, i.e. not receiving attacks. Under most semantics S (e.g. admissible, complete, grounded and preferred semantics [1]) ( , Lab) ∈ S ,LI , thus S is representable. In particular, given ( , ′, Lab) ∈ LI such that ′ ⧵ = , we can construct ∗ as required by Definition 18 by modifying ′ as follows. For any labelled out by Lab, we add an unattacked argument ′ attacking , and for any labelled undec we add an argument ′ which attacks itself and (and ′ is not attacked by other arguments). As required by Definition 16, most semantics return a labelling of ∗ ⧵ coinciding with Lab for the relevant arguments.
For the stable semantics [1] the above construction is possible for all pairs where the labelling does not assign undec to any argument, i.e. for all realizable pairs. Thus, the stable semantics is weakly representable.
We are now in a position to introduce the notion of reduced canonical local function. Basically, for any argumentation framework with input ( , ′, Lab) with a corresponding pair ( ′ ⧵ , Lab) which is realizable, an argumentation framework ∗ is selected that represents ( , ′, Lab), and the output labellings are identified as in Proposition 7. If instead the pair is not realizable, the function returns an empty set of labellings.
Definition 21. Given a local information function LI and a weakly representable semantics S w.r.t. LI , a reduced canonical local function of S w.r.t. LI is a local function SLI such that for any ′, Lab) ∈ LI SLI ( , ′, Lab) = { where ∗ is an argumentation framework such that represent ( , ′, Lab) ∈ LI .
Proposition 9. Let LI be a local information function and S a weakly representable semantics w.r.t. LI . For any ( , ′, Lab) ∈ LI , if ( ′ ⧵ , Lab) ∈ S then ∃ ∗ ∈ SLI ( , ′, Lab), i.e. the selection of an argumentation framework ∗ is possible.
Proof. Since S is weakly representable, if ( ′ ⧵ , and the conclusion follows from Definition 18.
Lab) ∈
S then ( ′ ⧵ ,
Lab) ∈ S ,LI ,
The suitability of a reduced canonical local function is confirmed by the following propositions.
Proposition 10. Let LI be a local information function and S a weakly representable semantics w.r.t. LI . If S is fully decomposable under LI , a reduced canonical local function SLI of S w.r.t. LI enforces decomposability of S under LI .
Proof. Since S is fully decomposable under LI , there is a local function for LI such that for every argumentation framework = ( , att) and for every partition = { 1, … , } LS( ) = { and we have to prove that for every = ( ,
att) and for every partition = { 1, … , } LS( ) = { 1 ∪ … ∪ ∣ ∈ SLI (↓ , LI (↓ ), ( ⋃ =1…,≠ )↓LI (↓ )⊖↓ )} ∗) ∧ Lab∗↓LI (↓ )⊖↓ = (⋃=1…,≠ inition 21, this is equal to SLI (↓
, LI (↓ ), (⋃=1…,≠ up, Lab = 1 ∪ … ∪ where ∈ SLI (↓ , LI (↓ for every .
Let us first consider Lab ∈ LS( ) . By condition (2), we have that Lab = 1 ∪ … ∪ with ∈ (↓ , LI (↓ ), (⋃=1…,≠ )↓LI (↓ )⊖↓ ). Taking into account that Lab ∈ LS( ) , obviously for any the pair (LI (↓ ) ⧵ ↓ , (⋃=1…,≠ )↓LI (↓ )⊖↓ ) is realized under S, thus by Proposition 9 there is an argumentation framework ∗ selected for SLI to represent (↓ , LI (↓ ), (⋃=1…,≠ Proposition 7, obtaining (↓ , LI (↓ ), (⋃=1…,≠ Lab∗ ∈ LS( )↓LI (↓ )⊖↓ ). We can then apply
)↓LI (↓ )⊖↓ ) = {Lab∗↓↓ ∣ )↓LI (↓ )⊖↓ }. According to Def
Turning to the reverse direction of the proof, consider a labellings 1 ∪ … ∪ such that, for any , ∈ SLI (↓ )↓LI (↓ )⊖↓ ). According to Definition )↓LI (↓ )⊖↓ ). Thus, for every it holds that ∈ )↓LI (↓ )⊖↓ ), and by (2) 1 ∪ … ∪ ∈ LS( ) .
Proposition 11. Let LI be a local information function and S a representable semantics w.r.t. LI . If S is fully decomposable under LI , there is only a local function which enforces decomposability of S under LI , coinciding with any reduced canonical local function SLI of S w.r.t. LI . Proof. Consider a reduced canonical local function SLI of S w.r.t. LI . If S is representable w.r.t. LI , for any ( , ′, Lab) ∈ LI it holds that ( ′ ⧵ , Lab) ∈ S ,LI , thus, by Proposition 8, ( ′ ⧵ , Lab) ∈ S . As a consequence, SLI ( , ′, Lab) is defined by the first item in Definition 21, and according to Proposition 7 its output is the same as that returned by any local function which enforces decomposability of S under LI .
Example 3. According to the considerations in Example 2, Proposition 11 applies to most common semantics (including admissible, complete, grounded, and preferred), while Proposition 10 applies to stable semantics.
In this paper, we have investigated the construction of local functions to locally compute labellings, adopting the general model introduced in [18] for studying the decomposability of argumentation semantics. Among the many future directions of this work, a first issue is to identify for the semantics available in the literature the canonical local function, or a reduced canonical local function, in an explicit form. This will be useful for studying decomposability under diferent local information functions and, possibly, determining the minimal local information suficient to guarantee decomposability. This may in turn provide a solid basis for mixing diferent argumentation semantics adopted in diferent subframeworks. More specifically, decomposability may be a necessary requirement in the specific case where all semantics coincide. In this regard, using less information relaxes the tie between local computations and gives more flexibility in the mixing strategy. [1] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and -person games, Artificial Intelligence 77 (1995) 321–357. [2] P. Baroni, M. Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171 (2007) 675–700. [3] B. Liao, H. Huang, Partial semantics of argumentation: basic properties and empirical results, J. of Logic and Computation 23 (2013) 541–562. [4] R. Baumann, Splitting an argumentation framework, in: Proc. of LPNMR 2011 11th Int.
[5] R. Baumann, G. Brewka, R. Wong, Splitting argumentation frameworks: An empirical evaluation, in: Theory and Applications of Formal Argumentation - First Int. Workshop (TAFA 2011). Revised Selected Papers, volume 7132 of Lecture Notes in Computer Science, Springer, 2011, pp. 17–31. [6] F. Cerutti, M. Giacomin, M. Vallati, M. Zanella, A SCC recursive meta-algorithm for computing preferred labellings in abstract argumentation, in: Proc. of the 14th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2014), 2014. [7] F. Cerutti, I. Tachmazidis, M. Vallati, S. Batsakis, M. Giacomin, G. Antoniou, Exploiting parallelism for hard problems in abstract argumentation, in: Proceedings of the 29th AAAI
[8] B. Liao, L. Jin, R. C. Koons, Dynamics of argumentation systems: A division-based method,
Artificial Intelligence 175 (2011) 1790–1814. [9] R. Baumann, G. Brewka, Analyzing the equivalence zoo in abstract argumentation, in:
XIV), 2013, pp. 18–33. [10] D. M. Gabbay, Fibring argumentation frames, Studia Logica 93 (2009) 231–295. [11] S. Villata, G. Boella, L. van Der Torre, Argumentation patterns, in: Proc. of ARGMAS 2011
[12] P. Baroni, G. Boella, F. Cerutti, M. Giacomin, L. W. N. van der Torre, S. Villata, On the input/output behavior of argumentation frameworks, Artificial Intelligence 217 (2014) 144–197. [13] T. Rienstra, A. Perotti, S. Villata, D. Gabbay, L. van Der Torre, G. Boella, Multi-sorted argumentation frameworks, in: Theory and Applications of Formal Argumentation - First
[14] M. Giacomin, Handling heterogeneous disagreements through abstract argumentation (extended abstract), in: Proc. of PRIMA 2017, 2017, pp. 3–11. [15] P. Baroni, M. Giacomin, Some considerations on epistemic and practical reasoning in abstract argumentation, in: Proc. of the 2nd Workshop on Advances In Argumentation In
[16] M. Giacomin, P. Baroni, F. Cerutti, Towards a general theory of decomposability in abstract argumentation, in: Proc. of 4th International Conference on Logic and Argumentation (CLAR 2021), 2021, p. To appear. [17] P. Baroni, M. Caminada, M. Giacomin, An introduction to argumentation semantics, The
[18] C. Cayrol, F. Dupin de Saint-Cyr, M. Lagasquie-Schiex, Change in abstract argumentation frameworks: adding an argument, Journal of Artificial Intelligence Research 38 (2010) 49–84.