=Paper=
{{Paper
|id=Vol-3354/paper5
|storemode=property
|title=Generalizing Consistency and Reinstatement in Abstract Argumentation
|pdfUrl=https://ceur-ws.org/Vol-3354/paper5.pdf
|volume=Vol-3354
|authors=Pietro Baroni,Federico Cerutti,Massimiliano Giacomin
|dblpUrl=https://dblp.org/rec/conf/aiia/Baroni0G22
}}
==Generalizing Consistency and Reinstatement in Abstract Argumentation==
https://ceur-ws.org/Vol-3354/paper5.pdf
Generalizing Consistency and Reinstatement in
Abstract Argumentation
Pietro Baroni1 , Federico Cerutti1,2 and Massimiliano Giacomin1,∗
1
Department of Information Engineering (University of Brescia), Italy
2
Cardiff University, UK
Abstract
We introduce two generic notions related to consistency and reinstatement in an abstract labelling
setting, based on a relation of intolerance between the labelled elements and two specific relations,
called incompatibility and reinstatement violation, between the labels assigned to them. This way, the
approach allows a spectrum of consistency and reinstatement requirements depending on the actual
choice of these relations. As a first application to formal argumentation, we show that traditional Dung’s
semantics can be expressed as combinations of different consistency and reinstatement requirements in
this context.
Keywords
Consistency, Reinstatement, Argumentation semantics, Argument justification
1. Introduction
In formal argumentation, the presence of conflicts between arguments is a key aspect that calls
for mechanisms able to produce sensible reasoning outcomes. In particular, these outcomes are
typically required to satisfy two somewhat dual properties, i.e. those that have intuitively to do
with the notion of consistency and those reflecting a requirement of completeness. For instance,
in abstract argumentation semantics [1, 2] either extensions or labellings are typically required
to satisfy the property of conflict-freeness, and it is also desired that arguments are accepted
when all of their attackers are definitely outright, as indicated by the definition of complete
extensions in [1] and the various notions of reinstatement introduced in [3].
In order to provide a common reference framework to bridge together the consistency
notions considered in different formalisms and possibly investigate variations and developments
thereof, a general formal treatment of consistency has been investigated in [4]. In this paper
we complement this investigation by integrating a generalized notion of reinstatement.
The paper is organized as follows. Section 2 introduces the generalized notions of consistency
and reinstatement, applicable in any context where a labelling approach is adopted. In particular,
an intolerance relation indicates pairs of labelled elements that cannot stand each other, while
AI3 2022: 6th Workshop on Advances in Argumentation in Artificial Intelligence
∗
Corresponding author.
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)
© 2022 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)
an incompatibility relation and a reinstatement violation relation between the labels are at the
basis of the proposed notions of consistency and reinstatement. To show the application of
the proposed concepts in the context of abstract argumentation, we prove in Section 3 that
Dung’s traditional semantics can be expressed as combinations of different consistency and
reinstatement requirements, particularly with different incompatibility and reinstatement viola-
tion relations. The relationships of this work with previous literature and various perspectives
of future development are finally discussed in Section 4.
2. Generalizing Consistency and Reinstatement for
Labelling-based Systems
In a variety of contexts, the assessments of entities of various kind are expressed by assigning
them a label. In order to provide a common ground to characterize such different contexts, in
[4] we have introduced a three-layer model including the following levels:
• At the top level, the notion of assessment classes is introduced to provide a reference
point to characterize different assessment labels, and to relate and compare them. These
classes have an underlying order, intuitively reflecting a notion of positivity (whatever a
positive assessment means in a given context).
• At an intermediate level, assessment labels are taken from a predefined set and classified
on the basis of assessment classes, thus inheriting the relevant positivity degree.
• At the bottom level, a generic set of entities is considered that can be assessed by assigning
each entity a label.
In the following, we introduce the notions of the model from the top level to the bottom level.
Definition 1. A set of assessment classes is a set 𝐶 equipped with a total order ≤ (i.e. a reflexive,
transitive and antisymmetric relation such that any two elements are comparable) and including a
maximum and a minimum element (i.e. an element 𝑐 ∈ 𝐶 such that ∀𝑐 ′ ∈ 𝐶 it holds that 𝑐 ′ ≤ 𝑐 or
𝑐 ≤ 𝑐 ′ , respectively) which are assumed to be distinct.
In the following we will abbreviate the term ‘set(s) of assessment classes’ as sac(s). Intuitively,
the order is meant to capture an abstract distinction between different levels of positivity of the
assessment, with 𝑐1 ≤ 𝑐2 meaning that 𝑐2 corresponds to an at least as positive assessment as 𝑐1 .
In the following we will mostly use a tripolar sac 𝐶 3 = {pos, mid, neg} with neg ≤ mid ≤ pos
and the intuitive meaning that pos corresponds to a definitely positive assessment, neg to a
definitely negative assessment, and mid to an intermediate situation. The basic idea, expressed
by the following definition, is that a sac is used to classify the elements of a set of labels according
to their level of positivity. Note that the elements of a sac are called classes because in general
more than one label can be mapped to the same class.
Definition 2. Given a set of assessment classes 𝐶, a 𝐶-classified set of assessment labels is a set Λ
equipped with a total function 𝐶Λ ∶ Λ → 𝐶. The total preorder induced on Λ by 𝐶Λ will be denoted
by ⪯ where 𝜆1 ⪯ 𝜆2 iff 𝐶Λ (𝜆1 ) ≤ 𝐶Λ (𝜆2 ). As usual, 𝜆1 ≺ 𝜆2 will denote 𝜆1 ⪯ 𝜆2 and 𝜆2 ⪯̸ 𝜆1
The fact that ⪯ is a total preorder is shown in the following proposition.
Proposition 1. Given a set of assessment classes 𝐶 and a 𝐶-classified set of assessment labels
Λ, the relation ⪯ as introduced in Definition 2 is reflexive and transitive, and for any 𝜆1 , 𝜆2 ∈ Λ,
𝜆1 ⪯ 𝜆2 or 𝜆2 ⪯ 𝜆1 .
Proof: Consider 𝜆1 , 𝜆2 , 𝜆3 ∈ Λ. By reflexivity of ≤ it holds that 𝐶Λ (𝜆1 ) ≤ 𝐶Λ (𝜆1 ), i.e. 𝜆1 ⪯ 𝜆1 .
Similarly, if 𝜆1 ⪯ 𝜆2 and 𝜆2 ⪯ 𝜆3 , by transitivity of ≤ it holds that 𝐶Λ (𝜆1 ) ≤ 𝐶Λ (𝜆3 ), i.e. 𝜆1 ⪯ 𝜆3 .
Finally, since ≤ is total it holds that 𝐶Λ (𝜆1 ) ≤ 𝐶Λ (𝜆2 ) or 𝐶Λ (𝜆2 ) ≤ 𝐶Λ (𝜆1 ), i.e. 𝜆1 ⪯ 𝜆2 or 𝜆2 ⪯ 𝜆1 .
□
It is easy to see that ⪯ is not necessarily an order, since different labels can be classified with
the same assessment class, thus antisymmetry does not hold.
We will abbreviate the term ‘set(s) of assessment labels’ as sal(s) and omit ‘𝐶-classified’, when
𝐶 is not ambiguous. Also, to distinguish preorders referring to different sals, given a sal Λ we
will denote the relevant preorder as ⪯Λ .
The notion of labelling based on a sal is the usual one.
Definition 3. Given a sal Λ and a set 𝑆, a Λ-labelling of 𝑆 is a function 𝐿 ∶ 𝑆 → Λ.
Different sals can be used to express assessments in distinct, but possibly related, evalua-
tion contexts. For instance, in the context of argument acceptance evaluation based on the
labelling-based version of Dung’s semantics [1, 2], the sal ΛIOU = {in, out, und} is used, while
in Defeasible Logic Programming (𝐷𝑒𝐿𝑃) arguments are marked as D(efeated) or U(ndefeated)
corresponding to the use of the sal ΛDe = {D, U}, and in [5] an approach using the set of
four labels ΛJV = {+, −, ±, ∅} is proposed. We assume that the sals mentioned above are 𝐶 3 -
classified as follows: 𝐶Λ3 IOU = {(in, pos), (out, neg), (und, mid)}; 𝐶Λ3 De = {(D, neg), (U, pos)};
𝐶Λ3 JV = {(−, neg), (+, pos), (±, mid), (∅, mid)}.
We are now ready to introduce the generalized notions of consistency and reinstatement in
this formal context. Intuitively, they correspond to dual notions aimed at satisfying somehow
conflicting goals:
• An inconsistency arises when two elements of a set which cannot stand each other
are assigned labels which are ‘too positive’ altogether. Correspondingly, consistency is
satisfied whenever this situation does not hold for any couple of elements.
• Reinstatement is violated when an element of a set is assigned a label which is ‘too
negative’, i.e. a negative label is assigned without a sufficient reason. A sufficient reason
holds if another element which cannot stand together is assigned a sufficiently positive
label. Correspondingly, reinstatement holds whenever a sufficiently positive label is
assigned to any element such that all of its conflicting elements are negatively assessed.
It can be seen that consistency and reinstatement are dual properties. In particular, a skeptical
assessment which assigns the most negative label to all elements trivially satisfies consistency,
but violates reinstatement. Conversely, assigning the most positive label to all elements trivially
satisfies reinstatement, but violates consistency whenever two elements cannot stand each
other.
According to this informal introduction, both inconsistency and reinstatement violation
can be understood as arising from two components: an intolerance relation at the level of the
assessed elements, indicating who cannot stand whom, and a relation at the level of the labels
indicating which pairs of assessments correspond to a violation if ascribed to a pair of elements
connected by the intolerance relation.
Definition 4. Given a set 𝑆, an intolerance relation on 𝑆 is a binary relation int ⊆ 𝑆 × 𝑆, where
(𝑠1 , 𝑠2 ) ∈ int indicates that 𝑠1 is intolerant of 𝑠2 and will be denoted as 𝑠1 ⊙ 𝑠2 , while (𝑠1 , 𝑠2 ) ∉ int
will be denoted as 𝑠1 ⊖ 𝑠2 .
Note that we do not make any assumption on the intolerance relation, in particular it needs
not to be symmetric.
To exemplify, in languages equipped with negation, typically intolerance between language
elements coincides with negation (a symmetric relation where each element has exactly one
opposite), however more general forms of contrariness have been considered in argumentation
contexts, where the corresponding intolerance relation may not be symmetric and allows the
existence of multiple contraries for an element [6, 7]. At the argument level, the attack relation
in Dung’s frameworks can be regarded as an example of intolerance relation.
Due to the dual nature of consistency w.r.t. reinstatement, violations at the level of the
labellings are modelled by distinct relations, namely an incompatibility relation and a reinstate-
ment violation relation on assessment labels, respectively. In the following we will assume that
each of these relations on assessment labels is always induced by a corresponding relation on
assessment classes.
Definition 5. Given a sac 𝐶, an incompatibility relation on 𝐶 is a relation inc ⊆ 𝐶 × 𝐶, where
(𝑐1 , 𝑐2 ) ∈ inc indicates that 𝑐1 is incompatible with 𝑐2 and will be denoted as 𝑐1 ⊡𝑐2 , while (𝑐1 , 𝑐2 ) ∉ inc
will be denoted as 𝑐1 ⊟𝑐2 . Given a 𝐶-classified sal Λ, we define the induced incompatibility relation
inc′ ⊆ Λ × Λ as follows: for every 𝜆1 , 𝜆2 ∈ Λ, (𝜆1 , 𝜆2 ) ∈ inc′ iff (𝐶Λ (𝜆1 ), 𝐶Λ (𝜆2 )) ∈ inc. With a little
abuse of notation we will also denote (𝜆1 , 𝜆2 ) ∈ inc′ as 𝜆1 ⊡𝜆2 , and analogously for 𝜆1 ⊟𝜆2 .
Definition 6. Given a sac 𝐶, a reinstatement violation relation on 𝐶 is a relation rv ⊆ 𝐶 × 𝐶,
where (𝑐1 , 𝑐2 ) ∈ rv indicates that 𝑐1 is not sufficiently positive to justify 𝑐2 and will be denoted as
𝑐1 ⊡𝑐2 , while (𝑐1 , 𝑐2 ) ∉ rv will be denoted as 𝑐1 ⊟𝑐2 . Given a 𝐶-classified sal Λ, we define the induced
reinstatement violation relation rv′ ⊆ Λ × Λ as follows: for every 𝜆1 , 𝜆2 ∈ Λ, (𝜆1 , 𝜆2 ) ∈ rv′ iff
(𝐶Λ (𝜆1 ), 𝐶Λ (𝜆2 )) ∈ rv. With a little abuse of notation we will also denote (𝜆1 , 𝜆2 ) ∈ rv′ as 𝜆1 ⊡𝜆2 ,
and analogously for 𝜆1 ⊟𝜆2 .
From the intuitions underlying the concepts of consistency and reinstatement, some rather
natural properties can be identified for incompatibility and, in a dual manner, for reinstatement
violation relations on 𝐶. The following definition introduces these properties for incompatibility
relations.
Definition 7. Given a sac 𝐶, let inc be an incompatibility relation on 𝐶. We say that inc is
well-founded if it satisfies the following properties:
c1
AAAB9XicbVC7TsNAEDyHVwivBCqU5kSERBXZCAEFRSQaykSQh5RY0fmyCaecz9bdGhRZ+QRaqOgQLX9CDxL/gu1QQMJUo5ld7ex4oRQGbfvDyi0tr6yu5dcLG5tb2zvF0m7LBJHm0OSBDHTHYwakUNBEgRI6oQbmexLa3vgy9dt3oI0I1A1OQnB9NlJiKDjDRLrmfadfrNhVOwNdJM4PqdRKvfJnY/+93i9+9QYBj3xQyCUzpuvYIbox0yi4hGmhFxkIGR+zEXQTqpgPxo2zqFN6GBmGAQ1BUyFpJsLvjZj5xkx8L5n0Gd6aeS8V//O6EQ7P3VioMEJQPD2EQkJ2yHAtkg6ADoQGRJYmByoU5UwzRNCCMs4TMUpKKSR9OPPfL5LWcdU5rZ40kmIuyAx5UiYH5Ig45IzUyBWpkybhZEQeyCN5su6tZ+vFep2N5qyfnT3yB9bbN4TVlOk=
c2
AAAB9XicbVC7TgJBFJ3FF+ILtDI0E4mJFdklRi0sSGwsIcojgQ2ZHS44YXZ2M3NXQwifYKuVnbH1T+w18V/cXSgUPNXJOffmnnu8UAqDtv1pZVZW19Y3spu5re2d3b18Yb9pgkhzaPBABrrtMQNSKGigQAntUAPzPQktb3SV+K170EYE6hbHIbg+GyoxEJxhLN3wXqWXL9llOwVdJs6clKqFbvGrfvhR6+W/u/2ARz4o5JIZ03HsEN0J0yi4hGmuGxkIGR+xIXRiqpgPxp2kUaf0ODIMAxqCpkLSVITfGxPmGzP2vXjSZ3hnFr1E/M/rRDi4cCdChRGC4skhFBLSQ4ZrEXcAtC80ILIkOVChKGeaIYIWlHEei1FcSi7uw1n8fpk0K2XnrHxaj4u5JDNkSZEckRPikHNSJdekRhqEkyF5JE/k2XqwXqxX6202mrHmOwfkD6z3H4ZklOo=
AAAB+3icbVC7SkNBEN0bXzG+Eq0kzWIQrMK9ImphEbCxTMA8JAlh7mYSl+x9sDtXCCFfYauVndj6G/YK/oubR6GJpzqcc4aZOX6spCHX/XRSK6tr6xvpzczW9s7uXja3XzNRogVWRaQi3fDBoJIhVkmSwkasEQJfYd0fXE/8+gNqI6PwloYxtgPoh7InBZCV7lrKRrvQ8TrZglt0p+DLxJuTQinXyn9VDj/Knex3qxuJJMCQhAJjmp4bU3sEmqRQOM60EoMxiAH0sWlpCAGa9mh68JgfJwYo4jFqLhWfivh7YgSBMcPAt8kA6N4sehPxP6+ZUO+yPZJhnBCGYrKIpMLpIiO0tE0g70qNRDC5HLkMuQANRKglByGsmNhqMrYPb/H7ZVI7LXrnxbOKLeaKzZBmeXbETpjHLliJ3bAyqzLBAvbIntizM3ZenFfnbRZNOfOZA/YHzvsPGiGXfw== AAAB+3icbVC7SkNBEN3rM8ZXopWkWQyCVbg3iFpYBGwsEzAPSUKYu5nEJXsf7M4VQshX2GplJ7b+hr2C/+LmUWjiqQ7nnGFmjh8rach1P52V1bX1jc3UVnp7Z3dvP5M9qJko0QKrIlKRbvhgUMkQqyRJYSPWCIGvsO4Prid+/QG1kVF4S8MY2wH0Q9mTAshKdy1lo13oFDuZvFtwp+DLxJuTfCnbyn1Vjj7Kncx3qxuJJMCQhAJjmp4bU3sEmqRQOE63EoMxiAH0sWlpCAGa9mh68JifJAYo4jFqLhWfivh7YgSBMcPAt8kA6N4sehPxP6+ZUO+yPZJhnBCGYrKIpMLpIiO0tE0g70qNRDC5HLkMuQANRKglByGsmNhq0rYPb/H7ZVIrFrzzwlnFFnPFZkixHDtmp8xjF6zEbliZVZlgAXtkT+zZGTsvzqvzNouuOPOZQ/YHzvsPG7CXgA==
1 2
s1 AAAB9XicbVC7TsNAEDyHVwivBCqU5kSERBXZCAEFRSQaykSQh5RY0fmyCaecz9bdGhRZ+QRaqOgQLX9CDxL/gu1QQMJUo5ld7ex4oRQGbfvDyi0tr6yu5dcLG5tb2zvF0m7LBJHm0OSBDHTHYwakUNBEgRI6oQbmexLa3vgy9dt3oI0I1A1OQnB9NlJiKDjDRLo2fadfrNhVOwNdJM4PqdRKvfJnY/+93i9+9QYBj3xQyCUzpuvYIbox0yi4hGmhFxkIGR+zEXQTqpgPxo2zqFN6GBmGAQ1BUyFpJsLvjZj5xkx8L5n0Gd6aeS8V//O6EQ7P3VioMEJQPD2EQkJ2yHAtkg6ADoQGRJYmByoU5UwzRNCCMs4TMUpKKSR9OPPfL5LWcdU5rZ40kmIuyAx5UiYH5Ig45IzUyBWpkybhZEQeyCN5su6tZ+vFep2N5qyfnT3yB9bbN53llPk=
s2
AAAB9XicbVC7TgJBFJ3FF+ILtDI0E4mJFdklRi0sSGwsIcojgQ2ZHS44YXZ2M3NXQwifYKuVnbH1T+w18V/cXSgUPNXJOffmnnu8UAqDtv1pZVZW19Y3spu5re2d3b18Yb9pgkhzaPBABrrtMQNSKGigQAntUAPzPQktb3SV+K170EYE6hbHIbg+GyoxEJxhLN2YXqWXL9llOwVdJs6clKqFbvGrfvhR6+W/u/2ARz4o5JIZ03HsEN0J0yi4hGmuGxkIGR+xIXRiqpgPxp2kUaf0ODIMAxqCpkLSVITfGxPmGzP2vXjSZ3hnFr1E/M/rRDi4cCdChRGC4skhFBLSQ4ZrEXcAtC80ILIkOVChKGeaIYIWlHEei1FcSi7uw1n8fpk0K2XnrHxaj4u5JDNkSZEckRPikHNSJdekRhqEkyF5JE/k2XqwXqxX6202mrHmOwfkD6z3H590lPo=
Figure 1: Two elements 𝑠1 , 𝑠2 ∶ 𝑠1 ⊙ 𝑠2 . The intolerance relation is graphically represented by an arrow.
• inc is monotonic, i.e. given 𝑐1 , 𝑐2 ∈ 𝐶 such that 𝑐1 ⊡𝑐2 , for every pair 𝑐1′ , 𝑐2′ ∈ 𝐶 such that
𝑐1 ≤ 𝑐1′ and 𝑐2 ≤ 𝑐2′ it holds that 𝑐1′ ⊡𝑐2′
• inc is non empty, i.e. inc ≠ ∅
• ∀𝑐1 ∈ 𝐶, ∃𝑐2 ∈ 𝐶 such that 𝑐1 ⊟𝑐2 and ∃𝑐3 ∈ 𝐶 such that 𝑐3 ⊟𝑐1
In order to discuss these properties, let us remark again that incompatibility refers to the situation
where labels are assigned to entities which are linked by intolerance. For instance, in a context
where statements are assessed and intolerance between them corresponds to contradiction, two
(not necessarily distinct) positive labels expressing belief should be incompatible: they cannot
be assigned to two contradictory statements, since you cannot believe both of them.
Let us then consider the simple case, depicted in Figure 1, involving two elements 𝑠1 , 𝑠2 ∈ 𝑆
such that 𝑠1 ⊙𝑠2 , and a Λ-labelling 𝐿 such that 𝐿(𝑠1 ) = 𝜆1 , 𝐿(𝑠2 ) = 𝜆2 , 𝐶Λ (𝜆1 ) = 𝑐1 and 𝐶Λ (𝜆2 ) = 𝑐2 .
The first property of Definition 7 relies on the idea that inconsistency arises from a sort of
‘excess of simultaneous positiveness’ in the assessment of some elements linked by intolerance.
In particular, 𝑐1 ⊡𝑐2 indicates that the simultaneous positiveness of the labels 𝜆1 and 𝜆2 is not
tolerated for two incompatible elements 𝑠1 and 𝑠2 . Since the simultaneous positiveness expressed
by 𝑐1′ and 𝑐2′ is not lesser that the one expressed by 𝑐1 and 𝑐2 , then it must hold 𝑐1′ ⊡𝑐2′ .
The second property requires at least a labelling to yield inconsistency for two elements
related by intolerance. Otherwise, an empty relation would completely neglect the intolerance
relation between elements of 𝑆.
The third property requires each label to be attainable for 𝑠1 and 𝑠2 without necessarily
generating inconsistencies, otherwise the role of the label would be too much weak.
Two additional intuitive properties of well-founded incompatibility relations can be derived.
First, two maximally positive labels cannot be ascribed together to conflicting elements. Second,
the maximally negative label is compatible with any other label, in particular min(𝐶)⊟ min(𝐶),
max(𝐶)⊟ min(𝐶) and min(𝐶)⊟ max(𝐶).
Proposition 2. Given a sac 𝐶, let inc be a well-founded incompatibility relation on 𝐶. It then
holds that:
• max(𝐶)⊡ max(𝐶)
• ∄𝑐 ∈ 𝐶 such that 𝑐⊡ min(𝐶) or min(𝐶)⊡𝑐
Proof: As to the first property, since inc ≠ ∅ there are 𝑐1 , 𝑐2 ∈ 𝐶 such that 𝑐1 ⊡𝑐2 . Taking into
account that inc is monotonic, it obviously holds that max(𝐶)⊡ max(𝐶).
As to the second property, assume by contradiction that ∃𝑐 ∈ 𝐶 such that 𝑐⊡ min(𝐶). By the
monotonicity property and the definition of min(𝐶), ∀𝑐 ′ ∈ 𝐶 it holds that 𝑐⊡𝑐 ′ , violating the
third condition of Definition 7. The other condition can be proved in the same way. □
According to the above proposition, we can identify for any sac 𝐶 the minimal well-founded
incompatibility relation as inc𝐶 = {(max(𝐶), max(𝐶))}.
Let us turn now to well-founded reinstatement violation relations.
Definition 8. Given a sac 𝐶, let rv be a reinstatement violation relation on 𝐶. We say that rv is
well-founded iff it satisfies the following properties:
• rv is dually monotonic, i.e. given 𝑐1 , 𝑐2 ∈ 𝐶 such that 𝑐1 ⊡𝑐2 , for every pair 𝑐1′ , 𝑐2′ ∈ 𝐶 such
that 𝑐1′ ≤ 𝑐1 and 𝑐2′ ≤ 𝑐2 it holds that 𝑐1′ ⊡𝑐2′
• rv is non empty, i.e. rv ≠ ∅
• ∀𝑐1 ∈ 𝐶, ∃𝑐2 ∈ 𝐶 such that 𝑐1 ⊟𝑐2 and ∃𝑐2 ∈ 𝐶 such that 𝑐2 ⊟𝑐1
In order to provide an explanation of these requirements, let us refer again to the simple case
depicted in Figure 1.
As to the first condition, we remark that reinstatement violation arises from a sort of ‘excess
of cautiousness’ in assigning positive labels, i.e. a too much negative label is assigned to an
element even in the absence of a positively assessed element linked by intolerance. Let us then
consider the case where, in Figure 1, 𝑐1 ⊡𝑐2 . This situation can be interpreted in two equivalent
ways:
1. The label 𝜆1 assigned to 𝑠1 is too much negative to justify the label 𝜆2 assigned to 𝑠2
2. The label 𝜆2 assigned to 𝑠2 is too much negative w.r.t. the ‘not so positive’ label 𝜆1 assigned
to 𝑠1
Accordingly, if 𝑐1′ ≤ 𝑐1 (i.e. positiveness of 𝜆1 does not increase) and 𝑐2′ ≤ 𝑐2 (i.e. positiveness of
𝜆2 does not increase), then it must also hold 𝑐1′ ⊡𝑐2′ .
The second condition, i.e. that rv is non empty, is required to avoid an overly skeptical
assessment attitude such that assigning the most negative label to all elements is always
allowed, independently of the labels of incompatible elements.
The third condition has an analogous rationale w.r.t. the same condition appearing in
Definition 7.
Also in this case two additional intuitive properties of well-founded reinstatement violation
relations can be derived. First, two minimally positive labels cannot be ascribed together to
conflicting elements1 . Second, the maximally positive label is compatible with any other label,
in particular max(𝐶)⊟ max(𝐶), max(𝐶)⊟ min(𝐶) and min(𝐶)⊟ max(𝐶).
Proposition 3. Given a sac 𝐶, let rv be a well-founded reinstatement violation relation on 𝐶. It
then holds that:
• min(𝐶)⊡ min(𝐶)
• ∄𝑐 ∈ 𝐶 such that 𝑐⊡ max(𝐶) or max(𝐶)⊡𝑐
1
This refers to the simple case of Figure 1, while the general case is handled according to Definition 10.
Proof: As to the first property, since rv ≠ ∅ there are 𝑐1 , 𝑐2 ∈ 𝐶 such that 𝑐1 ⊡𝑐2 . Taking into
account that inc is dually monotonic, it obviously holds that min(𝐶)⊡ min(𝐶).
As to the second property, assume by contradiction that ∃𝑐 ∈ 𝐶 such that 𝑐⊡ max(𝐶). By the
dual monotonicity property and the definition of max(𝐶), ∀𝑐 ′ ∈ 𝐶 it holds that 𝑐⊡𝑐 ′ , violating
the third condition of Definition 8. The other condition can be proved in the same way. □
According to the above proposition, we can identify for any sac 𝐶 the minimal nonempty
reinstatement violation relation as rv𝐶 = {(min(𝐶), min(𝐶))}.
While we have considered above the particular case involving only a couple of elements of 𝑆,
in order to introduce our generalized notions of inconsistency and reinstatement violation we
have to consider the general case of labellings of generic sets.
Let us start from our generalized notion of inconsistency of a labelling.
Definition 9. Given a set 𝑆 equipped with an intolerance relation int, a sac 𝐶 equipped with an
incompatibility relation inc, and a 𝐶-classified sal Λ, a Λ-labelling 𝐿 of 𝑆 is int-inc-inconsistent iff
∃𝑠1 , 𝑠2 ∈ 𝑆 such that 𝑠1 ⊙ 𝑠2 and 𝐿(𝑠1 )⊡𝐿(𝑠2 ) (1)
Conversely, we say that a labelling is int-inc-consistent if it is not int-inc-inconsistent, i.e.
∀𝑠1 , 𝑠2 ∈ 𝑆 such that 𝑠1 ⊙ 𝑠2 , it holds that 𝐿(𝑠1 )⊟𝐿(𝑠2 ) (2)
The above definition corresponds to the idea that consistency violation arises from an excess
of simultaneous positivity between any couple of incompatible elements, i.e. given 𝑠1 ∈ 𝑆 a
single 𝑠2 satisfying the inc relation is sufficient to yield inconsistency.
The following proposition is obvious and will not be proved.
Proposition 4. Given a set 𝑆 equipped with an intolerance relation int, a sac 𝐶 and a 𝐶-classified
sal Λ, consider two incompatibility relations inc and inc’ such that inc ⊆ inc′ . Then, an int-inc-
inconsistent Λ-labelling 𝐿 of 𝑆 is also int-inc’-inconsistent, and an int-inc’-consistent Λ-labelling 𝐿
of 𝑆 is also int-inc-consistent.
Turning to reinstatement violation, duality w.r.t. inconsistency is reflected also in the coun-
terpart of Definition 9. In particular, given 𝑠2 ∈ 𝑆, reinstatement is violated if all the elements 𝑠1
that are intolerant w.r.t. 𝑠2 do not provide a sufficient reason (i.e. are not positive enough) to
justify the ‘not so positive’ label assigned to 𝑠2 . Accordingly, a Λ-labelling 𝐿 of 𝑆 should violate
reinstatement iff
∃𝑠2 ∶ ∀𝑠1 ∈ 𝑆 such that 𝑠1 ⊙ 𝑠2 it holds that 𝐿(𝑠1 )⊡𝐿(𝑠2 ) (3)
while it should satisfy reinstatement iff
∀𝑠2 ∈ 𝑆, ∃𝑠1 ∈ 𝑆 such that 𝑠1 ⊙ 𝑠2 and 𝐿(𝑠1 )⊟𝐿(𝑠2 ) (4)
However, both conditions (3) and (4) are unsatisfactory for initial 2 elements of 𝑆, i.e. elements
𝑠2 of 𝑆 such that there are no elements 𝑠1 with 𝑠1 ⊙ 𝑠2 . Such elements 𝑠2 trivially satisfy condition
2
We borrow the terminology from abstract argumentation, where initial nodes are those without attackers.
(3) and never satisfy condition (4), entailing that no labelling is able to satisfy reinstatement
whenever there are initial elements in 𝑆.
A special condition for initial elements is thus needed.
In this regard, a first option is to impose max(𝐶) as the unique possible label for initial
elements, on the grounds that there are no reasons against the acceptance of initial elements.
However, this option looks somehow rigid, since a unique label is prescribed for initial nodes,
and from a conceptual point of view it looks strange that initial elements receive a special
treatment which completely neglects the reinstatement violation relation.
Another option is to introduce a special relation for initial elements which defines the set of
their possible labels, so that such a set can be tuned in the same way as for the reinstatement
violation relation. While this solution would achieve the maximum flexibility, it is still character-
ized by the same conceptual problem concerning a special treatment for initial elements, which
would be completely independent from the way labels are selected for non initial elements.
We are thus lead to explore solutions where the set of possible labels for initial nodes is
derived from the reinstatement violation relation. In this regard, the following two options for
initial elements can be considered:
1. {𝜆 ∈ Λ ∣ min(𝐶)⊟𝐶Λ (𝜆)}
2. {𝜆 ∈ Λ ∣ ∀𝑐 ∈ 𝐶, 𝑐⊟𝐶Λ (𝜆)}
Intuitively, according to the first option initial elements are equated to non initial elements
where intolerant elements w.r.t. them are all labelled with minimally positive labels. Accordingly,
the labels that the reinstatement violation relation allows for initial elements are the same
that are allowed for an element 𝑠2 such that there is a unique element 𝑠1 such that 𝑠1 ⊙ 𝑠2 , and
the label assigned to 𝑠1 is associated to min(𝐶). In a sense, the absence of reasons against the
acceptance of 𝑠2 is equivalent to a contrary reason with minimal acceptance degree.
The second option allows for initial nodes all those labels that would be allowed whatever
the labels of intolerant nodes. The underlying idea is that the absence of reasons against the
acceptance of a node 𝑠2 , i.e. in case 𝑠2 is an initial element, must prevent only the labels that
would be prevented by the reinstatement violation relation whatever the reason against their
acceptance, i.e. when there are intolerant elements whatever their labels.
Interestingly enough, the two options turn out to be equivalent if one adopts a well-founded
reinstatement violation relation, as the following proposition shows.
Proposition 5. Given a set 𝑆 equipped with an intolerance relation int, a sac 𝐶 equipped with a
well-founded reinstatement violation relation rv, and a 𝐶-classified sal Λ, it turns out that
{𝜆 ∈ Λ ∣ min(𝐶)⊟𝐶Λ (𝜆)} = {𝜆 ∈ Λ ∣ ∀𝑐 ∈ 𝐶, 𝑐⊟𝐶Λ (𝜆)}
Proof: Let us first prove the ⊆ relation. Let 𝜆 ∈ Λ be a label such that min(𝐶)⊟𝐶Λ (𝜆). By
the definition of minimum, ∀𝑐 ∈ 𝐶, min(𝐶) ≤ 𝑐. If by contradiction 𝑐⊡𝐶Λ (𝜆) then by dual
monotonicity of rv it would be the case that min(𝐶)⊡𝐶Λ (𝜆), contradicting the hypothesis that
min(𝐶)⊟𝐶Λ (𝜆).
As to the ⊇ relation, obviously any 𝜆 such that ∀𝑐 ∈ 𝐶, 𝑐⊟𝐶Λ (𝜆) satisfies as a particular case
min(𝐶)⊟𝐶Λ (𝜆). □
According to this result, we introduce our generalized notion of reinstatement violation of a
labelling as follows.
Definition 10. Given a set 𝑆 equipped with an intolerance relation int, a sac 𝐶 equipped with
a reinstatement violation relation rv, and a 𝐶-classified sal Λ, a Λ-labelling 𝐿 of 𝑆 is int-rv-
uncompliant iff
min(𝐶)⊡𝐶Λ (𝐿(𝑠2 )) if 𝑠2 is initial
∃𝑠2 ∈ 𝑆 ∶ { (5)
∀𝑠1 ∈ 𝑆 such that 𝑠1 ⊙ 𝑠2 it holds that 𝐿(𝑠1 )⊡𝐿(𝑠2 ) otherwise
Conversely, we say that a labelling is int-rv-compliant if it is not int-rv-uncompliant, i.e.
min(𝐶)⊟𝐶Λ (𝐿(𝑠2 )) if 𝑠2 is initial
∀𝑠2 ∈ 𝑆 { (6)
∃𝑠1 ∈ 𝑆 such that 𝑠1 ⊙ 𝑠2 and 𝐿(𝑠1 )⊟𝐿(𝑠2 ) otherwise
A corresponding result w.r.t. Proposition 4 holds.
Proposition 6. Given a set 𝑆 equipped with an intolerance relation int, a sac 𝐶 and a 𝐶-classified
sal Λ, consider two reinstatement violation relations rv and rv’ such that rv ⊆ rv′ . Then, an int-rv-
uncompliant Λ-labelling 𝐿 of 𝑆 is also int-rv’-uncompliant, and an int-rv’-compliant Λ-labelling 𝐿
of 𝑆 is also int-rv-compliant.
Proof: If 𝐿 is int-rv-uncompliant, there is an argument 𝛼 which satisfies one of the two cases
for 𝑠2 of condition (5) w.r.t. rv. Since rv ⊆ rv′ , obviously this case would be satisfied also
adopting rv’. The result concerning compliant labellings follows from the fact that a labelling is
int-rv-compliant iff it is not int-rv-uncompliant. □
A final comment can be devoted to the constraints imposed by consistent labellings on
the possible labels for initial elements. In particular, according to Definition 9 a labelling is
int-inc-consistent if ∀𝑠2 ∈ 𝑆 the following condition holds:
∀𝑠1 ∶ 𝑠1 ⊙ 𝑠2 , 𝐿(𝑠1 )⊟𝐿(𝑠2 ) (7)
If 𝑠2 is initial, then condition (7) is trivially satisfied, i.e. the possible labels for 𝑠2 are un-
constrained. However, one may wonder whether a different outcome would be obtained by
modifying Definition 9 so as to enforce a specific treatment for initial elements, similarly to
int-rv-compliant labellings (see Definition 10). Taking into account the intuition behind consis-
tency, the following two options for the possible labels of initial elements can be considered:
1. {𝜆 ∈ Λ ∣ min(𝐶)⊟𝐶Λ (𝜆)}
2. {𝜆 ∈ Λ ∣ ∃𝑐 ∈ 𝐶 ∶ 𝑐⊟𝐶Λ (𝜆)}
Similarly to the counterpart condition in the case of reinstatement, the first option equates
initial elements to non initial elements where intolerant elements w.r.t. them are all labelled
with minimally positive labels. Again, the absence of intolerant elements (and thus of any
simultaneous positivity) is considered equivalent to intolerant elements with minimally positive
labels. The second option allows for initial nodes all those labels that would be allowed by at least
one label assigned to an intolerant node. The underlying idea is that the absence of simultaneous
positivity must leave the maximal freedom in choosing the labels for initial elements, thus
any label that is allowed in case there is an intolerant element, whatever its label, must also
be allowed for initial elements. It is easy to see that, adopting a well-founded incompatibility
relation, both options do not enforce any constraint on the possible labels of initial elements. As
to the first option, by Proposition 2 there is no 𝑐 ∈ 𝐶 such that min(𝐶)⊡𝑐, entailing that ∀𝜆 ∈ Λ
min(𝐶)⊟𝐶Λ (𝜆). Of course, the second option enforces a weaker constraints w.r.t. the first one,
as it is evident by considering 𝑐 = min(𝐶), thus it must allow as the first option all of the labels
in Λ. Summing up, explicitly considering initial elements would not bring any modification
to Definition 9, which thus conceptually corresponds to the dual counterpart of Definition
10. From a theoretical perspective, these considerations support the well-foundedness and
generality of both definitions.
The generic definitions of inconsistency and reinstatement violation we have introduced
are ‘tunable’ as their instances can be ‘adjusted’ varying the incompatibility and reinstatement
violation relations, and possibly also the underlying intolerance relation and 𝐶-classification,
giving rise to a family of alternative (in)consistency and reinstatement (violation) notions. In
particular, different combinations of (in)consistency and reinstatement (violation) notions are
able to capture different argumentation semantics in Dung’s framework, as discussed next.
3. Consistency and reinstatement properties in argumentation
semantics
As well-known, in abstract argumentation an argumentation semantics is a formal specification
of a criterion to determine the possible outcomes of a situation of conflict, represented by a
binary relation of attack (denoted as → in the following), between a set 𝒜 of arguments. A
set of arguments and the relevant attack relation are modelled by the traditional notion of
argumentation framework [1].
Definition 11. An argumentation framework is a pair 𝐴𝐹 = (𝒜 , →) where 𝒜 is a set of arguments
and →⊆ 𝒜 × 𝒜 is a binary relation of attack between them. Given an argument 𝛼 ∈ 𝒜, we denote
as 𝛼 − the set {𝛽 ∈ 𝒜 ∣ (𝛽, 𝛼) ∈→}. An argument 𝛼 such that 𝛼 − = ∅ is called initial.
In the extension-based approach to argumentation semantics the conflict outcomes are ex-
pressed as sets of arguments called extensions and, in this context, two somewhat dual notions
corresponding to those introduced in the paper have been exploited in the relevant definitions.
On the one hand, a basic consistency notion called conflict-freeness has been traditionally con-
sidered: a set of arguments is conflict-free if it does not include any pair of arguments 𝛼, 𝛽 such
that 𝛼 ∈ 𝛽 − . On the other hand, the reinstatement criterion, as well as some of its variants, has
been made explicit in [3]: a semantics satisfies this criterion if any extension includes all those
arguments whose attackers are in turn attacked by the extension.
In this paper we consider the labelling-based approach to argumentation semantics. In
particular, the outcomes are expressed as arguments labellings instead of extensions, i.e. as
assignments of labels, taken from a given set, to the set of arguments 𝒜. Using the set of three
labels ΛIOU a correspondence can be drawn between extensions and labellings, while in general
the labelling-based approach is more expressive than the extension-based approach.
Combining the generalized notions of consistency and reinstatement with three-valued
labellings enables to identify correspondences between different instances of our generalized
notions and different semantics. In particular, given an abstract argumentation framework, we
assume that the intolerance relation coincides with the attack relation, i.e. 𝛼 ⊙ 𝛽 iff 𝛼 ∈ 𝛽 − , and
use the classification 𝐶Λ3 IOU introduced above. Then, an analysis of labelling-based semantics in
this perspective can be developed, as we do in the following, where we review the definitions
of some fundamental labelling-based semantics [2] showing that they can be expressed as
combinations of specific instances of generalized consistency and reinstatement properties.
The simplest semantics notion is the one of conflict-freeness, recalled in Definition 12.
Definition 12. Let 𝐿 be a labelling of an argumentation framework 𝐴𝐹 = (𝒜 , →). 𝐿 is conflict-
free iff for each 𝛼 ∈ 𝒜 it holds that:
1. if 𝐿(𝛼) = in then ∄𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in
2. if 𝐿(𝛼) = out then ∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in
Item 1 in Definition 12 corresponds exactly to the weakest form of consistency, i.e. to the
incompatibility relation inc𝐶 3 = {(pos, pos)}. The second item represents a requirement for
assigning to an argument the least positive label, and corresponds to reinstatement when the
𝑐𝑓
following reinstatement violation relation is adopted: rv𝐶 3 = {(neg, neg), (mid, neg)}.
Proposition 7. Let 𝐿 be a labelling of an argumentation framework 𝐴𝐹 = (𝒜 , →). Then, 𝐿 is
𝑐𝑓
→-rv𝐶 3 -compliant iff for each 𝛼 ∈ 𝒜 it holds that if 𝐿(𝛼) = out then ∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in .
𝑐𝑓
Proof: Let 𝐿 be →-rv𝐶 3 -compliant and assume by contradiction that there is an argument
𝛼 ∈ 𝒜 such that 𝐿(𝛼) = out and ∀𝛽 ∈ 𝛼 − 𝐿(𝛽) ≠ in . If 𝛼 is initial, according to Definition
𝑐𝑓
10 it must be the case that min(𝐶)⊟𝐶Λ (𝐿(𝛼)), i.e. taking into account the definition of rv𝐶 3 it
holds that 𝐶Λ (𝐿(𝛼)) ∈ {mid, pos}, which contradicts 𝐿(𝛼) = out . If 𝛼 is not initial, according to
Definition 10 it holds that ∃𝛽 ∈ 𝑆 ∶ 𝛽 ⊙ 𝛼 (i.e. 𝛽 ∈ 𝛼 − ) and 𝐿(𝛽)⊟𝐿(𝛼), i.e. taking again into
𝑐𝑓
account the definition of rv𝐶 3 and the fact that 𝐿(𝛼) = out we have that ∃𝛽 ∈ 𝑆 ∶ 𝛽 ∈ 𝛼 − and
𝐿(𝛽) ∈ {in }, contradicting the initial assumption that ∀𝛽 ∈ 𝛼 − 𝐿(𝛽) ≠ in .
As to the reverse direction, assume that for each 𝛼 ∈ 𝒜 if 𝐿(𝛼) = out then ∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in ,
𝑐𝑓
and assume by contradiction that 𝐿 is →-rv𝐶 3 -uncompliant. According to Definition 10, at least
one of the following two cases holds.
1. There is 𝛼 ∈ 𝒜 such that 𝛼 is initial and min(𝐶)⊡𝐶Λ (𝐿(𝛼)). Taking into account the
𝑐𝑓
definition of rv𝐶 3 , this entails 𝐿(𝛼) = out . By the initial assumption ∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in ,
contradicting the fact that 𝛼 is initial.
2. There is a non initial argument 𝛼 ∈ 𝒜 such that ∀𝛽 ∈ 𝑆 such that 𝑠1 ∈ 𝛼 − it holds that
𝑐𝑓
𝐿(𝛽)⊡𝐿(𝛼). Taking into account the definition of rv𝐶 3 , it must be the case that 𝐿(𝛼) = out
and ∀𝛽 ∈ 𝑆 such that 𝛽 ∈ 𝛼 − , 𝐿(𝛽) ∈ {out , und }. This contradicts the assumption that
∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in .
□
It is then immediate to characterize conflict-free labellings in terms of our generalized notions.
Proposition 8. The set of conflict-free labellings coincides with the set of labellings which are
𝑐𝑓
→-inc𝐶 3 -consistent and →-rv𝐶 3 -compliant.
Proof: The proof is immediate taking into account the correspondence between Item 1 in
Definition 12 and consistency under inc𝐶 3 , as well as correspondence between Item 2 and
𝑐𝑓
reinstatement compliance under rv𝐶 3 ensured by Proposition 7. □
Admissibility of a set of arguments was introduced in [1] with reference to the notion of
defense, i.e. the ability of a conflict-free set to defend its members by counterattacking their
attackers. The labelling-based counterpart of this idea is given in Definition 13.
Definition 13. Let 𝐿 be a labelling of an argumentation framework 𝐴𝐹 = (𝒜 , →). 𝐿 is admissible
iff for each 𝛼 ∈ 𝒜 it holds that:
1. if 𝐿(𝛼) = in then ∀𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = out
2. if 𝐿(𝛼) = out then ∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in
Item 1 in Definition 13 is a strengthening of item 1 of Definition 12, while item 2 is the
same in both Definition 12 and 13. Interestingly, this strengthening corresponds to the
choice of a stronger form of consistency: having an attacker labelled und is forbidden for
an argument labelled in, while having an attacker labelled in is allowed for an argument la-
belled und. This coincides with adopting the following asymmetric incompatibility relation
inc𝑎𝐶 3 = {(pos, pos), (mid, pos)}.
Proposition 9. The set of admissible labellings coincides with the set of labellings which are
𝑐𝑓
→-inc𝑎𝐶 3 -consistent and →-rv𝐶 3 -compliant.
Proof: It has been shown in [4] that admissible labellings correspond to the set of conflict-free
labellings that are →-inc𝑎𝐶 3 -consistent. Then the conclusion easily follows from Proposition 8. □
Completeness of a set of arguments was introduced in [1] and is based on the idea that if an
argument is defended by an admissible set of arguments, it should be accepted together with its
defenders. The labelling-based counterpart of this idea is given in Definition 14.
Definition 14. Let 𝐿 be a labelling of an argumentation framework 𝐴𝐹 = (𝒜 , →). 𝐿 is complete
if it is admissible and for each 𝛼 ∈ 𝒜 it holds that if 𝐿(𝛼) = und then ∄𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in and
∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = und
In words a complete labelling is an admissible labelling with the additional requirement
that an argument which is labelled und must have an und -labelled attacker and no in -labelled
attackers. In particular, the last condition amounts to further strengthening the notion of
consistency by adopting the incompatibility relation inc𝑐𝐶 3 = {(pos, pos), (pos, mid), (mid, pos)},
while the first condition is verified if the following reinstatement property is enforced.
Definition 15. A labelling 𝐿 satisfies the reinstatement property if ∀𝛼 ∈ 𝒜 it holds that if ∀𝛽 ∈ 𝛼 −
𝐿(𝛽) = out then 𝐿(𝛼) = in .
The following proposition shows that the reinstatement property can be captured by the
reinstatement violation relation rv𝑐𝐶 3 = {(neg, neg), (neg, mid), (mid, neg)}.
Proposition 10. Let 𝐿 be a labelling of an argumentation framework 𝐴𝐹 = (𝒜 , →). Then, 𝐿 is
→-rv𝑐𝐶 3 -compliant iff it satisfies the reinstatement property and for each 𝛼 ∈ 𝒜 it holds that if
𝐿(𝛼) = out then ∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in .
𝑐𝑓
Proof: Assume that 𝐿 is →-rv𝑐𝐶 3 -compliant. By Proposition 6, 𝐿 is →-rv𝐶 3 -compliant, and by
Proposition 7 the second condition of the thesis holds. To prove the reinstatement property, let
us consider an argument 𝛼 ∈ 𝒜 such that ∀𝛽 ∈ 𝛼 − , 𝐿(𝛽) = out , and let us show that 𝐿(𝛼) = in .
If 𝛼 is initial, by Definition 10 it must be the case that min(𝐶)⊟𝐶Λ (𝐿(𝛼)), i.e. taking into account
the definition of rv𝑐𝐶 3 we have that 𝐶Λ (𝐿(𝛼)) = pos, which holds iff 𝐿(𝛼) = in . If 𝛼 is non initial,
by Definition 10 there is an argument 𝛽 ∈ 𝛼 − such that 𝐿(𝛽)⊟𝐿(𝛼). Since by the hypothesis
𝐿(𝛽) = out , according to the definition of rv𝑐𝐶 3 it must be the case that 𝐿(𝛼) = in .
As to the reverse direction of the proof, assume that 𝐿 satisfies the reinstatement property and
the second condition of the hypothesis, and let us prove that 𝐿 is →-rv𝑐𝐶 3 -compliant. According
to Definition 10, we can consider an argument 𝛼 and distinguish two cases for it. If 𝛼 is
initial, by the reinstatement property 𝐿(𝛼) = in , thus 𝐶Λ (𝐿(𝛼)) = pos which satisfies the
required condition min(𝐶)⊟𝐶Λ (𝐿(𝛼)). If 𝛼 is not initial, referring to Definition 10 assume by
contradiction that there is no 𝛽 ∈ 𝛼 − such that 𝐿(𝛽)⊟𝐿(𝛼). This means that ∀𝛽 ∈ 𝛼 − , 𝐿(𝛽)⊡𝐿(𝛼),
i.e. (𝐿(𝛽), 𝐿(𝛼)) ∈ {(out , out ), (out , und ), (und , out )}. According to the second condition of the
hypothesis if 𝐿(𝛼) = out then ∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in , which entails that 𝐿(𝛼) ≠ out . Then
𝐿(𝛼) = und and ∀𝛽 ∈ 𝛼 − 𝐿(𝛽) = out , contradicting the reinstatement property. □
We can now characterize complete labellings in terms of generalized consistency and rein-
statement.
Proposition 11. The set of complete labellings coincides with the set of labellings which are
→-inc𝑐𝐶 3 -consistent and →-rv𝑐𝐶 3 -compliant.
Proof: It is shown in [4] that complete labellings coincide with admissible labellings that are
→-inc𝑐𝐶 3 -consistent and satisfy the reinstatement property. Then, according to the definition of
admissible labellings if a labelling is complete it satisfies the condition that if 𝐿(𝛼) = out then
∃𝛽 ∈ 𝛼 − ∶ 𝐿(𝛽) = in , entailing by Proposition 10 that it is →-rv𝑐𝐶 3 -compliant. Conversely, if a
labelling is →-inc𝑐𝐶 3 -consistent and →-rv𝑐𝐶 3 -compliant then by Proposition 4 and Proposition
𝑐𝑓
6 it is also →-inc𝑎𝐶 3 -consistent and →-rv𝐶 3 -compliant, and thus admissible by Proposition 9.
Moreover, by Proposition 10 it satisfies the reinstatement property. As a consequence, taking
into account the aforementioned result from [4], the labelling is complete. □
Stability of a set of arguments can be characterized in several ways, its key feature being that
no room is left for undecidedness (an argument is either accepted or attacked by an accepted
argument) as indicated by Definition 16.
Definition 16. Let 𝐿 be a labelling of an argumentation framework 𝐴𝐹 = (𝒜 , →). 𝐿 is stable if
it is complete and ∄𝛼 ∈ 𝒜 ∶ 𝐿(𝛼) = und .
This constraint can be put in correspondence with the adoption of the strongest no-
tion of consistency, namely with the choice of the incompatibility relation inc𝐶 3 =
{(pos, pos), (pos, mid), (mid, pos), (mid, mid)}.
Proposition 12. The set of stable labellings coincides with the set of labellings which are →-inc𝐶 3 -
consistent and →-rv𝑐𝐶 3 -compliant.
Proof: It is shown in [4] that stable labellings coincide with complete labellings which are
→-inc𝐶 3 -consistent. Then the conclusion follows from Proposition 11. □
To summarize, conflict-free labellings can be characterized in terms of generalized consis-
tency and reinstatement, admissible labellings can be characterized in terms of strengthening
consistency with respect to conflict-freeness without resorting to the traditional notion of
defense, while further strengthenings of generalized consistency and reinstatement characterize
complete and stable labellings.
4. Discussion and conclusions
In this paper, we have introduced the generalized notions of consistency and reinstatement
encompassing Dung’s traditional semantics. To our knowledge, providing a generalized form
of the notion of consistency has only been considered in [4], whereof this paper represents an
extension which integrates the notion of reinstatement. Some complementary research direction
has been previously pursued concerning the notion of consistency, e.g. encompassing some
inconsistency tolerance in the semantics of weighted argumentation systems [8], introducing the
notion of conflict-tolerant semantics [9], measuring inconsistency in (abstract and structured)
argumentation formalisms [10]. On the one hand, drawing correspondences between our
approach and these proposals is an interesting future work. On the other hand, in the light of
our general model it seems reasonable to apply these research directions also to reinstatement.
Several other research work can be envisaged. First of all, in [4] we have considered the issue
of consistency preservation when a labelling is obtained as a synthesis of a set of labellings.
Extending the relevant results to reinstatement preservation is a first step of future research.
Extending the analysis beyond tripolar classifications is another important future develop-
ment. For example, more articulated notions of argument justification have been considered in
the literature [11, 12, 13]. Dealing with consistency and reinstatement in such a context might
require considering different sets of assessment classes and defining a notion of refinement
between them. Addressing the evaluation of argument conclusions and their consistency is
a further key step. In particular, it would be interesting to extend the notions presented in
this paper to the formalism of multi-labelling systems [14], which can capture a variety of
approaches to derive the assessment of conclusions from the assessment of arguments.
Acknowledgments
This work has been partially supported by the research project GNCS-INdAM CUP
E55F22000270001, “Verifica Formale di Dibattiti nella Teoria dell’Argomentazione’’.
References
[1] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic
reasoning, logic programming, and n-person games, Artif. Intell. 77 (1995) 321–357.
[2] P. Baroni, M. Caminada, M. Giacomin, An introduction to argumentation semantics,
Knowledge Engineering Review 26 (2011) 365–410.
[3] P. Baroni, M. Giacomin, On principle-based evaluation of extension-based argumentation
semantics, Artif. Intell. 171 (2007) 675–700.
[4] P. Baroni, F. Cerutti, M. Giacomin, A generalized notion of consistency with applications
to formal argumentation, in: Proc. of the 9th Int. Conf. on Computational Models of
Argument (COMMA 2022), 2022, pp. 56–67.
[5] H. Jakobovits, D. Vermeir, Robust semantics for argumentation frameworks, J. of Logic
and Computation 9 (1999) 215–261.
[6] S. Modgil, H. Prakken, A general account of argumentation with preferences, Artif. Intell.
195 (2013) 361 – 397.
[7] P. Baroni, M. Giacomin, B. Liao, Dealing with generic contrariness in structured argumen-
tation, in: Proc. of the 24th Int. Joint Conf. on Artificial Intelligence, IJCAI 2015, 2015, pp.
2727–2733.
[8] P. E. Dunne, A. Hunter, P. McBurney, S. Parsons, M. J. Wooldridge, Weighted argument
systems: Basic definitions, algorithms, and complexity results, Artif. Intell. 175 (2011)
457–486.
[9] O. Arieli, Conflict-free and conflict-tolerant semantics for constrained argumentation
frameworks, J. Appl. Log. 13 (2015) 582–604.
[10] A. Hunter, Measuring inconsistency in argument graphs, CoRR abs/1708.02851 (2017).
URL: http://arxiv.org/abs/1708.02851. arXiv:1708.02851 .
[11] Y. Wu, M. W. A. Caminada, A labelling-based justification status of arguments, Studies in
Logic 3 (2010) 12–29.
[12] W. Dvořák, On the complexity of computing the justification status of an argument, in:
S. Modgil, N. Oren, F. Toni (Eds.), Proc. of the 1st Int. Workshop on Theory and Applications
of Formal Argumentation (TAFA 2011), number 7132 in Lecture Notes in Computer Science,
Springer, 2012, pp. 32–49.
[13] P. Baroni, M. Giacomin, G. Guida, Towards a formalization of skepticism in extension-
based argumentation semantics, in: Proc. of the 4th Workshop on Computational Models
of Natural Argument (CMNA 2004), 2004, pp. 47–52.
[14] P. Baroni, R. Riveret, Enhancing statement evaluation in argumentation via multi-labelling
systems, J. Artif. Intell. Res. 66 (2019) 793–860.