=Paper=
{{Paper
|id=Vol-3086/paper10
|storemode=property
|title=Constructing Local Functions to Decompose Argumentation Semantics: Preliminary Results
|pdfUrl=https://ceur-ws.org/Vol-3086/paper10.pdf
|volume=Vol-3086
|authors=Pietro Baroni,Federico Cerutti,Massimiliano Giacomin
|dblpUrl=https://dblp.org/rec/conf/aiia/BaroniCG21
}}
==Constructing Local Functions to Decompose Argumentation Semantics: Preliminary Results==
https://ceur-ws.org/Vol-3086/paper10.pdf
Constructing Local Functions to Decompose
Argumentation Semantics: Preliminary Results
Pietro Baroni1 , Federico Cerutti1,2 and Massimiliano Giacomin1
1
Department of Information Engineering (University of Brescia), Italy
2
Cardiff University, UK
Abstract
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.
Keywords
Dung framework, Argumentation Semantics, Decomposability
1. Introduction
Dung’s model provides an abstract account of argumentation where arguments are simply
represented as nodes of a directed graph, called argumentation framework, and where the graph’s
edges represent binary attacks between them [1]. This formalism is able to capture several
approaches in nonmonotonic reasoning and structured argumentation. Its importance lies in
the formal methods, called argumentation semantics, to determine the justification status of
a set of (typically conflicting) arguments, and thus the status of the relevant conclusions in
structured instances of the abstract model.
While the original definitions of argumentation semantics evaluate arguments at a global
level, referring to the whole argumentation framework, in recent years attention has been
devoted to semantics definition in a modular fashion, i.e. determining the semantics outcome
based on local evaluations in subframeworks [2, 3, 4]. This is motivated by the possibility of
saving computation time [5, 6, 7, 8], and by investigations concerning various equivalence
relations [9, 10, 11], summarizing argumentation frameworks [12], and combining different
argumentation semantics [13, 14, 15].
In a previous paper [16] a general model has been devised for studying the decomposability of
argumentation semantics in Dung’s abstract argumentation setting. This model does not assume
any constraint on the way an argumentation framework is partitioned into subframeworks,
and encompasses all possible kinds of local information available for the local computations,
AI3 2021: 5th Workshop on Advances in Argumentation in Artificial Intelligence
Envelope-Open pietro.baroni@unibs.it (P. Baroni); federico.cerutti@unibs.it (F. Cerutti); massimiliano.giacomin@unibs.it
(M. Giacomin)
Orcid 0000-0001-5439-9561 (P. Baroni); 0000-0003-0755-0358 (F. Cerutti); 0000-0003-4771-4265 (M. Giacomin)
© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
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.
2. Background
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 finite1
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 .
We will also need two relations and two operators between argumentation frameworks.
Definition 2. Given two argumentation frameworks 𝐴𝐹1 = (𝒜1 , att 1 ) and 𝐴𝐹2 = (𝒜2 , att 2 ):
• 𝐴𝐹1 ⊆ 𝐴𝐹2 iff 𝒜1 ⊆ 𝒜2 and att 1 ⊆ att 2
• 𝐴𝐹1 ⊑ 𝐴𝐹2 iff 𝒜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.
1
In the general definition, the set of arguments may be infinite.
2
It 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.
Definition 3. 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 𝐴𝐹 = (𝒜 , att), a labelling of 𝐴𝐹 is a labelling of 𝒜. The set of all labellings of 𝐴𝐹 is
denoted as 𝔏(𝐴𝐹 ). For a labelling Lab of Args, the restriction of Lab to a set of arguments Args ′ ⊆
Args, denoted as Lab↓Args ′ , is defined as Lab ∩ (Args ′ × {in , out , undec }). We extend this notation
to sets of labellings, i.e. given a set of a labellings 𝔏 ⊆ 𝔏Args , 𝔏↓Args ′ ≜ {Lab↓Args ′ ∣ Lab ∈ 𝔏}.
Moreover, if Lab ∈ 𝔏(𝐴𝐹 ) and 𝐴𝐹′ ⊆ 𝐴𝐹, where 𝐴𝐹′ = (𝒜 ′ , att ′ ), Lab↓𝐴𝐹′ will denote Lab↓𝒜 ′ .
A labelling-based semantics prescribes a set of labellings for each argumentation framework.
Definition 4. Given an argumentation framework 𝐴𝐹 = (𝒜 , att), a labelling-based semantics S
associates with 𝐴𝐹 a subset of 𝔏(𝐴𝐹 ), denoted as LS (𝐴𝐹 ).
Many semantics exist, but since we are not concerned with specific definitions we refer the
reader to [1, 17].
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 different kinds of
available topological information.
Definition 5. A local information function is a function LI ∶ {(𝐴𝐹∗ , 𝐴𝐹 ) ∣ 𝐴𝐹∗ , 𝐴𝐹 ∈ SAF ∧ 𝐴𝐹 ⊑
𝐴𝐹∗ } → SAF such that ∀𝐴𝐹∗ , 𝐴𝐹 ∈ SAF ∶ 𝐴𝐹 ⊑ 𝐴𝐹∗
• 𝐴𝐹 ⊑ LI (𝐴𝐹∗ , 𝐴𝐹 ) and LI (𝐴𝐹∗ , 𝐴𝐹 ) ⊆ 𝐴𝐹∗
• if 𝐴𝐹∗ ⊆ 𝐴𝐹∗∗ then either LI (𝐴𝐹∗∗ , 𝐴𝐹 ) = LI (𝐴𝐹∗ , 𝐴𝐹 ) or it is not the case that LI (𝐴𝐹∗∗ , 𝐴𝐹 ) ⊆
𝐴𝐹∗
For ease of notation, in the following LI (𝐴𝐹∗ , 𝐴𝐹 ) will be denoted as LI 𝐴𝐹∗ (𝐴𝐹 ).
In the first item of the above definition, 𝐴𝐹 ⊑ LI (𝐴𝐹∗ , 𝐴𝐹 ) signifies that the local subframe-
work 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 different
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.
Definition 6. An argumentation framework with input is a tuple (𝐴𝐹 , 𝐴𝐹′ , Lab) where 𝐴𝐹 , 𝐴𝐹′ ∈
SAF such that 𝐴𝐹 ⊑ 𝐴𝐹′ , and Lab ∈ 𝔏𝐴𝐹′ ⊖𝐴𝐹 .
Intuitively, 𝐴𝐹 represents a subframework, 𝐴𝐹′ represents the portion of the global argumen-
tation 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 lo-
𝑖𝑛𝑝
cal information function LI in 𝐴𝐹∗ , written (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI ,𝐴𝐹∗ , if 𝐴𝐹′ = LI 𝐴𝐹∗ (𝐴𝐹 ).
𝑖𝑛𝑝
(𝐴𝐹 , 𝐴𝐹′ , Lab) is derived from LI , written (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI , if ∃𝐴𝐹∗ such that (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈
𝑖𝑛𝑝
𝐴𝐹LI ,𝐴𝐹∗ .
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 lo-
cal information function LI in an argumentation framework 𝐴𝐹∗ under a semantics S, writ-
𝑖𝑛𝑝 𝑖𝑛𝑝
ten (𝐴𝐹 , 𝐴𝐹′ , 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 (𝐴𝐹∗ , 𝐴𝐹 ) such that 𝐴𝐹∗ , 𝐴𝐹 ∈ SAF ∧ 𝐴𝐹 ⊑ 𝐴𝐹∗ , with 𝐴𝐹 = (𝒜 , att),
𝑖𝑛𝑝 𝑎𝑡𝑡−𝑖𝑛𝑝
𝑖𝑛𝑝LI 𝐴𝐹∗ (𝐴𝐹 ) ≡ (𝒜 ∪ 𝒜𝐴𝐹∗ , att ∪ 𝒜𝐴𝐹∗ ).
∗
Now, consider 𝐴𝐹 = ({𝛼, 𝛽, 𝛾 , 𝛿1 , 𝛿2 }, {(𝛼, 𝛽), (𝛽, 𝛾 ), (𝛽, 𝛿1 ), (𝛾 , 𝛿1 ), (𝛿1 , 𝛿2 ), (𝛿2 , 𝛿1 )}) and 𝐴𝐹 =
𝐴𝐹∗ ↓{𝛿1 ,𝛿2 } . We have that 𝑖𝑛𝑝LI 𝐴𝐹∗ (𝐴𝐹 ) = 𝐴𝐹′ = ({𝛽, 𝛾 , 𝛿1 , 𝛿2 }, {(𝛽, 𝛿1 ), (𝛾 , 𝛿1 ), (𝛿1 , 𝛿2 ), (𝛿2 , 𝛿1 )}).
The example also shows that e.g. the argumentation framework with input (𝐴𝐹 , 𝐴𝐹′ , {(𝛽, in ), (𝛾 , in )})
is derived from 𝑖𝑛𝑝LI . Under most semantics S (e.g. the grounded or preferred semantics [1]) it also
𝑖𝑛𝑝
holds (𝐴𝐹 , 𝐴𝐹′ , {(𝛽, in ), (𝛾 , in )}) ∈ 𝑅𝐴𝐹𝑖𝑛𝑝LI ,S . However, if we change the definition of 𝑖𝑛𝑝LI so as
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 .
3.2. Local Function and Decomposability
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 (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈
𝑖𝑛𝑝
𝐴𝐹LI a (possibly empty) set of labellings of 𝐴𝐹, i.e. 𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 2𝔏(𝐴𝐹 ) .
A semantics S is decomposable (also called fully decomposable) if the labellings prescribed
on an argumentation framework 𝐴𝐹 correspond to the possible combinations of compatible
labellings obtained by applying a local function 𝐹 in the subframeworks that partition the global
framework.
Definition 10. A local function 𝐹 for a local information function LI enforces decomposabil-
ity of a semantics S under LI iff for every argumentation framework 𝐴𝐹 = (𝒜 , att) and for
every partition 𝒫 = {𝑃1 , … , 𝑃𝑛 } of 𝒜, the following condition holds: LS (𝐴𝐹 ) = {𝐿𝑃 1 ∪ … ∪ 𝐿𝑃 𝑛 ∣
𝐿𝑃 𝑖 ∈ 𝐹 (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 )}. A semantics S is decomposable
𝑖 𝑖
(or equivalently fully decomposable) under LI iff there is a local function 𝐹 which enforces decom-
posability of S under LI .
In Definition 10, (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 ) is an argumentation
𝑖 𝑖
framework with input representing the subframework of 𝐴𝐹 on the partition element 𝑃𝑖 (first
component) enriched with the available external information. In particular, the second compo-
nent is the available topological information on the neighboring part. The third component
is the labelling assigned to the locally known arguments outside the subframework 𝐴𝐹↓𝑃𝑖 , i.e.
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 specif-
ically, 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.
Decomposability can be split into two partial decomposability properties.
Definition 11. A local function 𝐹 for a local information function LI enforces top-down decom-
posability of a semantics S under LI iff for every argumentation framework 𝐴𝐹 = (𝒜 , att)
and for every partition 𝒫 = {𝑃1 , … , 𝑃𝑛 }, it holds that LS (𝐴𝐹 ) ⊆ {𝐿𝑃 1 ∪ … ∪ 𝐿𝑃 𝑛 ∣ 𝐿𝑃 𝑖 ∈
𝐹 (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 )}. A local function 𝐹 for a local informa-
𝑖 𝑖
tion function LI enforces bottom-up decomposability of a semantics S under LI iff for every
argumentation framework 𝐴𝐹 = (𝒜 , att) and for every partition 𝒫 = {𝑃1 , … , 𝑃𝑛 }, it holds that
LS (𝐴𝐹 ) ⊇ {𝐿𝑃 1 ∪ … ∪ 𝐿𝑃 𝑛 ∣ 𝐿𝑃 𝑖 ∈ 𝐹 (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 )}.
𝑖 𝑖
In words, 𝐹 enforces top-down decomposability if the procedure to compute labellings by
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 iff 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 .
Given a specific argumentation semantics S, one may rely on the relevant definition to
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 (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI , the only way to determine the
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
returned by the local function is contained in 𝔏(𝐴𝐹 ), each of these argumentation frameworks
𝐴𝐹∗ must have 𝐴𝐹 as a subframework, i.e. 𝐴𝐹 ⊑ 𝐴𝐹∗ , and the returned labellings are obtained
by restricting (some of) the labellings in LS (𝐴𝐹∗ ) to 𝐴𝐹. Moreover, taking into account the role
of 𝐴𝐹′ and Lab, the argumentation with input (𝐴𝐹 , 𝐴𝐹′ , Lab) has to be realized in 𝐴𝐹∗ from LI ,
and only the labellings Lab ∗ ∈ LS (𝐴𝐹∗ ) compatible with Lab (i.e. such that Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab)
should be taken into account.
In order to model all possible selections of argumentation frameworks for any (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈
𝑖𝑛𝑝
𝐴𝐹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 argu-
mentation frameworks in which this argumentation framework with input is realized.
Definition 12. 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 se-
𝑖𝑛𝑝
mantics S and an argumentation framework with input (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI , a set of argu-
mentation frameworks, denoted as 𝑓𝑆𝑇 S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab), such that 𝑓𝑆𝑇 S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab) ⊆ {𝐴𝐹∗ ∣
𝑖𝑛𝑝
(𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝑅𝐴𝐹LI ,𝐴𝐹∗ ,S }. A standard argumentation framework function for LI is finite if,
𝑖𝑛𝑝 𝑖𝑛𝑝
∀ (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI , 𝑓𝑆𝑇 S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab) is finite. It is unitary if, ∀ (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI ,
either 𝑓𝑆𝑇 S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab) includes a single framework or it is empty.
𝑖𝑛𝑝
Note that if (𝐴𝐹 , 𝐴𝐹′ , Lab) ∉ 𝑅𝐴𝐹LI ,S then 𝑓𝑆𝑇 S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab) is not defined, i.e. returns
the empty set.
Intuitively, the aim of 𝑓𝑆𝑇 S,LI (𝐴𝐹 , 𝐴𝐹′ , 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 sufficient 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
definition.
Definition 13. 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 (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI
𝐹𝑓𝑆𝑇 ,S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab) = ⋃ {Lab ∗ ↓𝐴𝐹 ∣ Lab ∗ ∈ LS (𝐴𝐹∗ ), Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab}
𝐴𝐹∗ ∈𝑓𝑆𝑇 S,LI (𝐴𝐹 ,𝐴𝐹′ ,Lab)
It is easy to see that a monotonic relation between standard argumentation framework
functions and generated local functions holds.
1 and 𝑓 2 for LI and
Proposition 1. Given two standard argumentation framework functions 𝑓𝑆𝑇 𝑆𝑇
S,LI S,LI
given a semantics S, if 𝑓𝑆𝑇 1 (𝐴𝐹 , 𝐴𝐹′ , Lab) ⊆ 𝑓𝑆𝑇
2 (𝐴𝐹 , 𝐴𝐹′ , Lab) then 𝐹𝑓 1 ,S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab) ⊆
𝑆𝑇
𝐹𝑓 2 ,S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab).
𝑆𝑇
Proof. The result easily follows from Definitions 12 and 13.
Let us now turn on two possible requirements for a standard argumentation framework
function.
First, constructing a local function on the basis of a standard argumentation framework func-
tion 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 . 𝑆𝑇
2 as follows. According to Definition 13, for any (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹 𝑖𝑛𝑝
Proof. We construct 𝑓𝑆𝑇 LI
the output of 𝐹𝑓 1 ,S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab) can be expressed as
𝑆𝑇
⋃ {Lab ∗ ↓𝐴𝐹 ∣ Lab ∗ ∈ LS (𝐴𝐹∗ ) ∧ Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab}
S,LI
𝐴𝐹∗ ∈𝑓𝑆𝑇
1
(𝐴𝐹 ,𝐴𝐹′ ,Lab)
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 (𝐴𝐹 , 𝐴𝐹′ , Lab), such that
𝑓𝑆𝑇
𝐹𝑓 1 ,S,LI (𝐴𝐹 , 𝐴𝐹′ , Lab) = ⋃ {Lab ∗ ↓𝐴𝐹 ∣ Lab ∗ ∈ LS (𝐴𝐹∗ ) ∧ Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab}
𝑆𝑇
S,LI
𝐴𝐹∗ ∈𝑓𝑆𝑇
2
(𝐴𝐹 ,𝐴𝐹′ ,Lab)
2 (see Definition 13).
This corresponds to our desired 𝑓𝑆𝑇
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.
Definition 14. 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 14 𝐹𝑓𝑆𝑇 ,S,LI
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 sufficient to
identify an argumentation framework and a partition where the same condition is not satisfied
by 𝐹𝑓𝑆𝑇 ,S,LI .
A significant question is then whether Definitions 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.
5. The Canonical Local Function
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 𝐴𝐹∗ such that (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝑅𝐴𝐹LI ,𝐴𝐹∗ ,S , the restriction of the labellings of 𝐴𝐹∗ to
the subframework 𝐴𝐹. This is shown in the following proposition.
𝑖𝑛𝑝
Proposition 3. Let S be a fully decomposable semantics under LI , and let (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI
be an argumentation framework with input derived from LI . Let 𝐴𝐹∗ be an argumentation
framework such that 𝐴𝐹′ = LI 𝐴𝐹∗ (𝐴𝐹 ), and Lab ∗ ∈ LS (𝐴𝐹∗ ) be a labelling of 𝐴𝐹∗ such that
Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab. Then, for any local function 𝐹 which enforces decomposability of S under LI ,
Lab ∗ ↓𝐴𝐹 ∈ 𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab).
We should note that the reverse of the above proposition does not hold, i.e. 𝐹 may re-
quire 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 different 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.
Definition 15. 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 (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI ,
𝐹SLI (𝐴𝐹 , 𝐴𝐹′ , Lab) = ⋃ {Lab ∗ ↓𝐴𝐹 ∣ Lab ∗ ∈ LS (𝐴𝐹∗ ) ∧ Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab}
𝑖𝑛𝑝
𝐴𝐹∗ ∣(𝐴𝐹 ,𝐴𝐹′ ,Lab)∈𝑅𝐴𝐹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 𝐴𝐹∗ such that (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈
𝑖𝑛𝑝
𝑅𝐴𝐹LI ,𝐴𝐹∗ ,S (see Definition 12 and Definition 13).
Due to the choice of considering all possible labellings compliant with Definitions 12 and 13,
the canonical local function of any semantics S associated to a local information function LI
enforces top-down decomposability of S under LI , as shown in the following proposition.
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
partition 𝒫 = {𝑃1 , … , 𝑃𝑛 } and for any labelling Lab ∈ LS (𝐴𝐹 ), it holds that Lab = 𝐿𝑃 1 ∪ … ∪
𝐿𝑃 𝑛 ∣ 𝐿𝑃 𝑖 ∈ 𝐹SLI (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 ). For any 𝑖 ∈ {1, … 𝑛}, let
𝑖 𝑖
𝐿𝑃 𝑖 = Lab↓𝑃𝑖 . It holds that Lab = 𝐿𝑃 1 ∪…∪𝐿𝑃 𝑛 , thus, for any 𝑖, (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 =
𝑖 𝑖
Lab↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 . As a consequence, we have to prove that for any 𝑖 ∈ {1, … 𝑛} Lab↓𝑃𝑖 ∈
𝑖 𝑖
𝐹SLI (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), Lab↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 ). According to the definition of canonical local
𝑖 𝑖
function (see Definition 15) this amount to prove that there is an argumentation framework
𝐴𝐹∗ and a labelling Lab ∗ ∈ LS (𝐴𝐹∗ ) such that LI 𝐴𝐹∗ (𝐴𝐹↓𝑃𝑖 ) = LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), Lab ∗ ↓𝐴𝐹↓𝑃 = Lab↓𝑃𝑖
𝑖
and Lab ∗ ↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 = Lab↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 . It is easy to see that all these conditions
𝑖 𝑖 𝑖 𝑖
are satisfied by selecting 𝐴𝐹∗ = 𝐴𝐹 and Lab ∗ = Lab. In particular, Lab ∈ LS (𝐴𝐹 ) holds by
assumption, LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ) = LI 𝐴𝐹∗ (𝐴𝐹↓𝑃𝑖 ) 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 sufficient 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
𝑖𝑛𝑝
enforces decomposability of S under LI . Then, ∀(𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI , 𝐹SLI (𝐴𝐹 , 𝐴𝐹′ , Lab) ⊆
𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab).
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
of local computations.
The above results are sufficient to show that the canonical local function enforces decompos-
ability of all decomposable semantics.
Proposition 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 sufficient, i.e. different 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.
A single argumentation framework is sufficient, however, if some conditions are verified.
These conditions, expressed in the following definition, depend both on the semantics and the
local information function.
𝑖𝑛𝑝
Definition 16. Let S be a semantics, LI a local information function and (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI
an argumentation framework with input derived from LI . An argumentation framework 𝐴𝐹∗
𝑖𝑛𝑝
represents (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI under S and LI , written 𝐴𝐹∗ ∈ 𝑅𝐸𝑃LI ′ ′
S (𝐴𝐹 , 𝐴𝐹 , Lab), if 𝐴𝐹 =
LI 𝐴𝐹∗ (𝐴𝐹 ), ∃Lab ′1 ∈ LS (𝐴𝐹∗ ⧵ 𝐴𝐹 ) with Lab ′1 ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab, and LI 𝐴𝐹∗ (𝐴𝐹∗ ⧵ 𝐴𝐹 ) = ∅.
Some comments on the conditions of Definition 16 are in order. In particular, the key condition
is LI 𝐴𝐹∗ (𝐴𝐹∗ ⧵𝐴𝐹 ) = ∅, which corresponds to a kind of unidirectional local information function,
i.e. while 𝐴𝐹 is influenced by (part of) 𝐴𝐹∗ ⧵ 𝐴𝐹 and the relevant labelling, the reverse does not
hold. Thus, the role of 𝐴𝐹∗ ⧵ 𝐴𝐹 is to enforce the labelling Lab in 𝐴𝐹′ ⧵ 𝐴𝐹 independently of
𝐴𝐹. Enforcing such labelling is then possible if a labelling compatible with Lab is prescribed by
the semantics, i.e. 𝐴𝐹′ = LI 𝐴𝐹∗ (𝐴𝐹 ) and ∃Lab ′1 ∈ LS (𝐴𝐹∗ ⧵ 𝐴𝐹 ) with Lab ′1 ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab.
The next proposition shows that the reverse of Proposition 3 holds if the conditions of
Definition 16 are satisfied, i.e. a single argumentation framework is sufficient if it represents
the argumentation framework with input.
𝑖𝑛𝑝
Proposition 7. Let S be a fully decomposable semantics under LI , and let (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI
be an argumentation framework with input derived from LI . Let 𝐴𝐹∗ be an argumentation
framework such that 𝐴𝐹∗ ∈ 𝑅𝐸𝑃LI ′
S (𝐴𝐹 , 𝐴𝐹 , Lab). Then, for any local function 𝐹 which enforces
decomposability of S under LI , 𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab) = {Lab ∗ ↓𝐴𝐹 ∣ Lab ∗ ∈ LS (𝐴𝐹∗ ) ∧ Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 =
Lab}.
Proof. Let us first consider a labelling Lab ∗ ∈ LS (𝐴𝐹∗ ) such that Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab. It is easy
to see that all the hypotheses of Proposition 3 are satisfied, thus Lab ∗ ↓𝐴𝐹 ∈ 𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab).
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
of S under LI , by Definition 10 and taking into account that 𝐴𝐹∗ ↓𝐴𝐹∗ ⊖𝐴𝐹 = 𝐴𝐹∗ ⧵𝐴𝐹, we have that
LS (𝐴𝐹∗ ) = {Lab 1 ∪Lab 2 ∣ Lab 1 ∈ 𝐹 (𝐴𝐹∗ ⧵𝐴𝐹 , LI 𝐴𝐹∗ (𝐴𝐹∗ ⧵𝐴𝐹 ), Lab 2 ↓LI ∗ (𝐴𝐹∗ ⧵𝐴𝐹 )⊖(𝐴𝐹∗ ⧵𝐴𝐹 ) ), Lab 2 ∈
𝐴𝐹
𝐹 (𝐴𝐹 , LI 𝐴𝐹∗ (𝐴𝐹 ), Lab 1 ↓LI 𝐴𝐹∗ (𝐴𝐹 )⊖𝐴𝐹 )}. Since LI 𝐴𝐹∗ (𝐴𝐹∗ ⧵ 𝐴𝐹 ) = ∅ and 𝐴𝐹′ = LI 𝐴𝐹∗ (𝐴𝐹 ), it
holds that
LS (𝐴𝐹∗ ) = {Lab 1 ∪ Lab 2 ∣ Lab 1 ∈ 𝐹 (𝐴𝐹∗ ⧵ 𝐴𝐹 , ∅, ∅), Lab 2 ∈ 𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab 1 ↓𝐴𝐹′ ⊖𝐴𝐹 )} (1)
′
Let us then consider a labelling Lab ′2 ∈ 𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab). We have to prove that ∃Lab ∗ ∈
′ ′
LS (𝐴𝐹∗ ) such that Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab and Lab ′2 = Lab ∗ ↓𝐴𝐹 .
′ ′
By the hypothesis that 𝐴𝐹∗ ∈ 𝑅𝐸𝑃LI ′ ∗
S (𝐴𝐹 , 𝐴𝐹 , Lab), ∃Lab 1 ∈ LS (𝐴𝐹 ⧵𝐴𝐹 ) with Lab 1 ↓𝐴𝐹′ ⊖𝐴𝐹 =
′ ′
Lab. Let us now identify Lab ∗ as Lab ′1 ∪ Lab ′2 . It obviously holds that Lab ′2 = Lab ∗ ↓𝐴𝐹 and
∗′
Lab ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab. Moreover, since 𝐹 enforces decomposability of S under LI , considering
the argumentation framework 𝐴𝐹∗ ⧵ 𝐴𝐹 and the partition including a single set (which includes
in turn all the relevant arguments), from Lab ′1 ∈ LS (𝐴𝐹∗ ⧵ 𝐴𝐹 ) we get Lab ′1 ∈ 𝐹 (𝐴𝐹∗ ⧵ 𝐴𝐹 , ∅, ∅).
′
Since Lab ′2 ∈ 𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab) = 𝐹 (𝐴𝐹 , 𝐴𝐹′ , Lab ′1 ↓𝐴𝐹′ ⊖𝐴𝐹 ), by (1) we have Lab ∗ ∈ LS (𝐴𝐹∗ ).
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.
First, for a given argumentation framework with input (𝐴𝐹 , 𝐴𝐹′ , Lab) we need to focus on the
pair (𝐴𝐹′ ⧵ 𝐴𝐹 , Lab), playing for 𝐴𝐹 the role of the ‘input pair’ affecting the local computation
of labellings in 𝐴𝐹. Accordingly, we introduce the following definition of a pair derived from a
local information function LI .
Definition 17. Given a local information function LI , a pair (𝐴𝐹𝑖𝑛 , Lab) (where 𝐴𝐹𝑖𝑛 ∈ SAF and
𝑖𝑛𝑝
Lab ∈ 𝔏(𝐴𝐹𝑖𝑛 )) is derived from LI , written (𝐴𝐹𝑖𝑛 , Lab) ∈ 𝑃LI , if ∃(𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI such that
𝐴𝐹′ ⧵ 𝐴𝐹 = 𝐴𝐹𝑖𝑛 .
A pair is representable if every relevant argumentation framework with input can be repre-
sented by an argumentation framework.
Definition 18. Given a semantics S and a local information function LI , a pair (𝐴𝐹𝑖𝑛 , Lab) ∈ 𝑃LI
𝑟𝑒𝑝 𝑖𝑛𝑝
is representable under S and LI , written (𝐴𝐹𝑖𝑛 , Lab) ∈ 𝑃S,LI , if for every (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI
such that 𝐴𝐹′ ⧵ 𝐴𝐹 = 𝐴𝐹𝑖𝑛 , ∃𝐴𝐹∗ ∈ 𝑅𝐸𝑃LI ′
S (𝐴𝐹 , 𝐴𝐹 , Lab).
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.
Definition 19. Given a semantics S, a pair (𝐴𝐹𝑖𝑛 , Lab) is realized under S, written (𝐴𝐹𝑖𝑛 , Lab) ∈
𝑃S𝑟𝑒𝑎𝑙 , if ∃𝐴𝐹∗ ∈ SAF such that 𝐴𝐹𝑖𝑛 ⊆ 𝐴𝐹∗ and ∃Lab ∗ ∈ LS (𝐴𝐹∗ ) such that 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 𝐴𝐹𝑖𝑛 .
As shown below, if a pair is representable under S and LI then it is also realized under S.
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 ∃𝐴𝐹∗∗ ∈ 𝑅𝐸𝑃LI ′
S (𝐴𝐹 , 𝐴𝐹 , 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.
It is immediate to see that a representable semantics is also weakly 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 𝑅𝐹LI
S such that for any
𝑖𝑛𝑝
(𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI
{Lab ∗ ↓𝐴𝐹 ∣ Lab ∗ ∈ LS (𝐴𝐹∗ ) ∧ Lab ∗ ↓𝐴𝐹′ ⊖𝐴𝐹 = Lab}
′
𝑅𝐹LI
S (𝐴𝐹 , 𝐴𝐹 , Lab) = { if (𝐴𝐹′ ⧵ 𝐴𝐹 , Lab) ∈ 𝑃S𝑟𝑒𝑎𝑙
∅ otherwise
where 𝐴𝐹∗ is an argumentation framework such that 𝐴𝐹∗ ∈ 𝑅𝐸𝑃LI ′
S (𝐴𝐹 , 𝐴𝐹 , Lab) selected to
𝑖𝑛𝑝
represent (𝐴𝐹 , 𝐴𝐹′ , Lab) ∈ 𝐴𝐹LI .
Definition 21 is well defined, as shown in the following proposition.
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 ∃𝐴𝐹∗ ∈ 𝑅𝐸𝑃LI ′
S (𝐴𝐹 , 𝐴𝐹 , Lab),
∗
i.e. the selection of an argumentation framework 𝐴𝐹 is possible.
𝑟𝑒𝑝
Proof. Since S is weakly representable, if (𝐴𝐹′ ⧵ 𝐴𝐹 , Lab) ∈ 𝑃S𝑟𝑒𝑎𝑙 then (𝐴𝐹′ ⧵ 𝐴𝐹 , Lab) ∈ 𝑃S,LI ,
and the conclusion follows from Definition 18.
The suitability of a reduced canonical local function is confirmed by the following proposi-
tions.
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 𝑅𝐹LI
S 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 (𝐴𝐹 ) = {𝐿𝑃 1 ∪ … ∪ 𝐿𝑃 𝑛 ∣ 𝐿𝑃 𝑖 ∈ 𝐹 (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), ( ⋃ 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 )} (2)
𝑖 𝑖
𝑗=1…𝑛,𝑗≠𝑖
and we have to prove that for every 𝐴𝐹 = (𝒜 , att) and for every partition 𝒫 = {𝑃1 , … , 𝑃𝑛 }
LS (𝐴𝐹 ) = {𝐿𝑃 1 ∪ … ∪ 𝐿𝑃 𝑛 ∣ 𝐿𝑃 𝑖 ∈ 𝑅𝐹LI
S (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), ( ⋃ 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 )}
𝑖 𝑖
𝑗=1…𝑛,𝑗≠𝑖
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 𝑅𝐹LI
S to represent (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 )⊖𝐴𝐹↓𝑃𝑖 ). We can then apply
Proposition 7, obtaining 𝐹 (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 ) = {Lab ∗ ↓𝐴𝐹↓𝑃 ∣
𝑖 𝑖 𝑖
Lab ∗ ∈ LS (𝐴𝐹∗ ) ∧ Lab ∗ ↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 = (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 }. According to Def-
𝑖 𝑖 𝑖 𝑖
inition 21, this is equal to 𝑅𝐹LI
S (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 ). Summing
𝑖 𝑖
up, Lab = 𝐿𝑃 1 ∪ … ∪ 𝐿𝑃 𝑛 where 𝐿𝑃 𝑖 ∈ 𝑅𝐹LI
S (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 )⊖𝐴𝐹↓𝑃𝑖 )
for every 𝑖.
Turning to the reverse direction of the proof, consider a labellings 𝐿𝑃 1 ∪ … ∪ 𝐿𝑃 𝑛 such that, for
any 𝑖, 𝐿𝑃 𝑖 ∈ 𝑅𝐹LI
S (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 ). According to Definition
𝑖 𝑖
21, 𝐴𝐹∗ is selected such that 𝐴𝐹∗ ∈ 𝑅𝐸𝑃LI S (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 )⊖𝐴𝐹↓𝑃𝑖 ).
Taking into account that 𝐹 enforces decomposability of S under LI , by Proposition 7 we have
that 𝐹 (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 ) = {Lab ∗ ↓𝐴𝐹↓𝑃 ∣ Lab ∗ ∈ LS (𝐴𝐹∗ ) ∧
𝑖 𝑖 𝑖
Lab ∗ ↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 = (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃 )⊖𝐴𝐹↓𝑃 }, which by Definition 21 is equal to
𝑖 𝑖 𝑖 𝑖
𝑅𝐹LI
S (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 )⊖𝐴𝐹↓𝑃𝑖 ). Thus, for every 𝑖 it holds that 𝐿𝑃 𝑖 ∈
𝐹 (𝐴𝐹↓𝑃𝑖 , LI 𝐴𝐹 (𝐴𝐹↓𝑃𝑖 ), (⋃𝑗=1…𝑛,𝑗≠𝑖 𝐿𝑃 𝑗 )↓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 𝑅𝐹LIS of S w.r.t. LI .
Proof. Consider a reduced canonical local function 𝑅𝐹LI S 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, 𝑅𝐹LI ′
S (𝐴𝐹 , 𝐴𝐹 , 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.
7. Discussion and Conclusion
In this paper, we have investigated the construction of local functions to locally compute la-
bellings, 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 decomposabil-
ity under different local information functions and, possibly, determining the minimal local
information sufficient to guarantee decomposability. This may in turn provide a solid basis for
mixing different argumentation semantics adopted in different subframeworks. More specifi-
cally, 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.
References
[1] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmono-
tonic 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.
Conf. on Logic Programming and Nonmonotonic Reasoning, 2011, pp. 40–53.
[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
Conference on Artificial Intelligence, volume 29, 2015.
[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:
Proc. of the 14th Int. Workshop on Computational Logic in Multi-Agent Systems (CLIMA
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
8th Int. Workshop on Argumentation in Multi-Agent Systems, 2011, pp. 133–150.
[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
Int. Workshop (TAFA 2011). Revised Selected Papers, volume 7132 of Lecture Notes in
Computer Science, Springer, 2011, pp. 231–245.
[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
Artificial Intelligence, 2018, pp. 1–5.
[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
Knowledge Engineering Review 26:4 (2011) 365–410.
[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.