Weighted knowledge bases with typicality and defeasible reasoning in a gradual argumentation semantics

Abstract

Weighted knowledge bases for description logics with typicality provide a logical interpretation of MultiLayer Perceptrons, based on a “concept-wise” multi-preferential semantics. On the one hand, in the finitely many-valued case, Answer Set Programming (ASP) has been shown to be suitable for addressing defeasible reasoning from weighted knowledge bases for the boolean fragment of $\mathcal{ALC}$ . On the other hand, the semantics of weighted knowledge bases with typicality, in their different variants, have suggested some new gradual argumentation semantics, as well as an approach for defeasible reasoning over a weighted argumentation graph, building on the gradual semantics and, specifically on the φ-coherent semantics. In this paper, we explore the relationships between weighted knowledge bases and weighted argumentation graphs, to develop proof methods for defeasible reasoning over an argumentation graph under the φ-coherent semantics, in the finitely-valued case. We establish a mapping from a weighted argumentation graph to a weighted knowledge base as well as a lower bound on the complexity of the problem of verifying graded implications over an argumentation graph in the φ-coherent semantics. We also consider a mapping from weighted knowledge bases to weighted argumentation graphs, and provide an ASP implementation and some experimental results.

1 Introduction

Preferential description logics have been studied in the last decades to deal with inheritance with exceptions in ontologies, based on the idea of extending the language of Description Logics (DLs) [9, 53], allowing for non-strict forms of inclusions, called typicality or defeasible inclusions, of the form T (C) ⊑ D (meaning “the typical C-elements are D-elements” or “normally C’s are D’s”), with different preferential semantics [25, 47] and closure constructions [18, 49]. Defeasible inclusions correspond to KLM conditionals C ∣∼ D [56, 57], and defeasible DLs inherit and extend some of the preferential semantics and the closure constructions developed within preferential and conditional approaches to commonsense reasoning [14, 60].

A (conditional) knowledge base (KB) comprising typicality inclusions enables defeasible reasoning, as in fact the prototypical properties of concept C are not necessarily enforced on all individuals in C. For example, horses are normally tall, but atypical horses not being tall exist. Some control on the strength of the applicability of typicality inclusions (which, otherwise, may depend on specificity, as in the rational closure and in its refinements mentioned above) can be obtained by assigning them a rank, that is, a natural number as large as strong is the expressed property. The resulting ranked DL knowledge bases [44], which strongly relate to the ranked knowledge bases by Brewka (2004), are interpreted according to a concept-wise multi-preferential semantics, that is, by associating a preference relation to single concepts, so to identify the most typical instances of a concept. A finer control can be obtained by assigning weights to typicality inclusions, hence obtaining weighted DL knowledge bases [3, 45], where the weight w in a weighted typicality inclusion (T (Horse) ⊑ Tall, w) is intended to represent the plausibility of the inclusion (when positive) or its implausibility (when negative). Some different semantics have been considered for weighted KBs, namely, the coherent, faithful and φ-coherent [3, 45], both in the fuzzy and in the finitely-valued case.

Weighted knowledge bases, under a fuzzy φ-coherent semantics, have been used to provide a logical interpretation of MultiLayer Perceptrons (MLPs, [51]), which can be represented as weighted KBs, by encoding synaptic connections as weighted typicality inclusions [3, 45]. This approach allows for the verification of properties of the MultiLayer network in the form of graded typicality inclusions T (C) ⊑ D ≥ l through defeasible entailment. An alternative approach is based on the idea of building a preferential interpretation of the network starting from the input-output behavior of the network over a set of input stimuli, and then verifying the conditional properties of the network by model checking. Both approaches have been considered in [3].

The problem of deciding φ-coherent entailment from a weighted KB is decidable in the finitely-valued case, for the $\mathcal{LC}$ fragment of $\mathcal{ALC}$ , in which only boolean concepts are allowed [2]. More precisely, when the truth degree set is taken to be ${\mathcal{C}}_n=\{0,\frac{1}{n},\dots ,\frac{n-1}{n},\frac{n}{n}\}$ , for an integer n ≥ 1, the decision problem has been shown to be P ^NP[log] (for combination functions as in Gödel and Łukasiewicz logics), and some different encodings of the entailment in ASP have been considered, by taking advantage of custom propagators, weak constraints, weight constraints and order encoding.

The relationships between preferential and conditional approaches to non-monotonic reasoning and argumentation semantics are strong. Let us also mention, the work by Geffner and Pearl on Conditional Entailment, whose proof theory is defined in terms of “arguments” [40], and the work by Dung [34]. While for Dung-style argumentation semantics and for Abstract Dialectical Frameworks, the relationships with conditional reasoning have been deeply investigated [24, 67], this is not the case for gradual argumentation [5, 54]. Nevertheless, the strong similarities between a multilayer neural network and a weighted argumentation graph, have suggested that an argumentation graph can as well be regarded as a weighted KB (a set of weighted typicality inclusions), and that the semantics of weighted KBs with typicality, in their different variants, can give rise to new gradual argumentation semantics, called, respectively, coherent, faithful and φ-coherent semantics [42, 43]. This has suggested as well a conditional approach for defeasible reasoning over a weighted argumentation graph, which builds on a gradual semantics [1].

In this paper, we consider the argumentation semantics mentioned above in the finitely-valued case, with the aim of establishing a formal correspondence between weighted KBs in the boolean fragment of $\mathcal{ALC}$ with typicality and the above mentioned weighted argumentation semantics, to provide the basis for developing decision algorithms for verifying properties of a weighted argumentation graph under the φ-coherent semantics. In the approach we propose, a preferential interpretation I _G can be built from a weighted argumentation graph G, based on the argumentation semantics, and graded typicality inclusions can be verified over that interpretation.

Note that the relationships between weighted conditional KBs and MLPs easily extend to the proposed gradual semantics, which captures the stationary states of MLPs. This is in agreement with the previous results on the relationships between argumentation frameworks and neural networks by Garces, Gabbay and Lamb [33] and by Potyka [61].

In Section 2, we recall the definition of the boolean fragment of a many-valued DL with typicality and of weighted knowledge bases. In Section 3, we introduce the many-valued coherent, faithful and φ-coherent semantics for weighted argumentation graphs, and study their relationships. In Section 4 we relate the φ-coherent semantics to other gradual semantics in some well-known gradual argumentation frameworks. In Section 5 we develop a preferential interpretation of the gradual semantics introduced in Section 3. Section 6 aims to establish a mapping from a weighted argumentation graph G and a weighted KB with typicality. The mapping suggests an algorithm for defeasible reasoning over an argumentation graph under the φ-coherent semantics, in the finitely-valued case, and also provides a P||NP = PNP[log] upper bound on the complexity of the problem. Specifically, simplified versions of the ASP encodings proposed for weighted KBs [2] can be adopted for verifying the satisfiability of graded implications over an argumentation graph. We also prove a lower complexity bound in Section 7. This suggests that a mapping from a weighted KB (with a nonempty TBox, including strict graded inclusions) to a weighted argumentation graph, might as well be possible under the φ-coherent semantics. In Section 8, we provide a positive result under some conditions (that is, for a specific choice of function φ, for the combination functions as in Łukasiewicz logic, and empty ABox). Section 9 provides an ASP implementation and some experimental results.

2 Background: ${\mathcal{LC}}_n$ with typicality and weighted knowledge bases

This section summarizes the required background on the weighted many-valued description logic with typicality [2, 46] ${\mathcal{LC}}_n\text{T}$ . Fuzzy and many-valued DLs with typicality build on the definition of fuzzy and many-valued description logics which are well studied in description logics literature [21, 64]. In this paper, we restrict to finite t-norms [15, 38] and to the boolean fragment of $\mathcal{ALC}$ , without roles (more expressive DLs with typicality, including all $\mathcal{ALC}$ constructs, have been considered in [3]).

Let us consider the finitely-valued set of truth degrees ${\mathcal{C}}_n=\{0,\frac{1}{n},\dots ,\frac{n-1}{n},\frac{n}{n}\}$ , for an integer n ≥ 1, also called truth space. We consider the truth degree functions ⊗, ⊕, ⊖ and ⊳, as a t-norm, an s-norm, an implication and a negation function, which extend the classical Boolean conjunction, disjunction, implication, and negation, respectively, to the many-valued case [50]. Specifically, we will consider the minimum (Gödel) t-norm and Łukasiewicz t-norm, with their residua, and the dual t-conorms with respect to the standard involutive negation. Let us remember that, in Łukasiewicz logic, a ⊗ b = max {a + b - 1, 0}, a ⊕ b = min {a + b, 1}, a ⊳ b = min {1 - a + b, 1}. In Gödel logic a ⊗ b = min {a, b}, a ⊕ b = max {a, b}, a ⊳ b = 1 ifa ≤ bandbotherwise. In both cases, we will consider standard involutive negation ⊖a = 1 - a.

Let N _C be a set of concept names and N _I be a set of individual names. The set of ${\mathcal{LC}}_n$ concepts is defined inductively as follows:

(i) A ∈ N _C , ⊤ and ⊥ are concepts;

(ii) if C and D are concepts, then C ⊓ D,  C ⊔ D,   ¬ C are concepts.

Following the same notation as for fuzzy DLs in [58], an ${\mathcal{LC}}_n$ knowledge baseK is defined as a pair $(\mathcal{T},\mathcal{A})$ , where $\mathcal{T}$ (the TBox) is a set of concept inclusions of the form C ⊑ D θ l, and $\mathcal{A}$ (the ABox) is a set of assertions of the form C (a)  θ l, with C and D being concepts, a ∈ N _I , θ ∈ {≥ , ≤ , > , <} and l ∈ [0, 1]. Concept inclusions and assertions are collectively called axioms.

A finitely many-valued interpretation (for short, interpretation) is a pair I = 〈Δ ^I , ·  ^I 〉, where Δ ^I is a non-empty domain and · ^I is an interpretation function that assigns to each individual name a ∈ N _I a value a ^I  ∈ Δ ^I in the domain, and to each concept name A ∈ N _C a function $A^I:{\Delta }^I\to {\mathcal{C}}_n$ . Hence, a domain element x ∈ Δ ^I belongs to the extension of a concept name A ∈ N _C to some degreeA ^I  (x) in ${\mathcal{C}}_n$ . The interpretation of composed concepts is defined according to the following inductive definition: $\begin{array}{cc}\hfill \begin{array}{cc}\hfill {\top }^I\left(x\right)=1& \hfill (C\sqcap D{)}^I(x)=C^I(x)\otimes D^I(x)\\ \hfill {\perp }^I\left(x\right)=0& \hfill (C\bigsqcup D{)}^I(x)=C^I(x)\oplus D^I(x)\\ \hfill & \hfill (\neg C{)}^I(x)=\ominus C^I(x)\phantom{C^I\left(x\right)}\end{array}& \hfill \end{array}$

The interpretation function · ^I is also extended to axioms as follows: $\begin{array}{cc}\hfill & (C⊑D{)}^I=\underset{x\in {\Delta }^I}{\mathit{inf}}{C}^I(x)⊳D^I(x)\hfill \\ \hfill & \left(C\right(a){)}^I=C^I(a^I)\hfill \end{array}$ Note that, in this finitely-valued setting, the infimum truth degree in the expression above coincides with the minimum truth degree.

The definition of satisfiability of graded inclusions and assertions also follows [58].

Definition 1. Let $K=(\mathcal{T},\mathcal{A})$ be an ${\mathcal{LC}}_n$ knowledge base, and I be an interpretation. The satisfiability relation ⊨ is defined as follows:

I ⊨ C ⊑ D θl  if  (C ⊑ D)  ^I  θl;

I ⊨ C (a)  θl  if  C ^I  (a ^I )  θl;

for a set S of axioms, I ⊨ S if I ⊨ E for all E ∈ S;

I ⊨ K if $I\models \mathcal{T}$ and $I\models \mathcal{A}$ .

If I ⊨ Γ, we say that IsatisfiesΓ or that I is a model of Γ (for Γ being an axiom, a set of axioms, or a KB). An axiom E is entailed by K, written K ⊨ E, if I ⊨ E holds for all models I of K.

${\mathcal{LC}}_n$ is extended with typicality concepts of the form T (C) representing the set of typical instances of concept C. T (C) may occur in both TBox and ABox axioms and, as usual, the typicality operator cannot be nested. From the semantic side, the degree of membership of domain individuals in concept C induces a preference relation ≺ _C over the domain, which is used to define the typical C-elements. For an interpretation I = 〈Δ ^I , ·  ^I 〉, a preference relation ≺ _C on Δ ^I (where x ≺  _C y means that x is preferred to y) is obtained as follows: for all x, y ∈ Δ ^I , x ≺  _C y if and only if C ^I  (x) > C ^I  (y).

The typical elements of C are those belonging to C with the greatest positive truth degree. Formally, the interpretation of typicality concept T (C) in I is defined as follows:

Definition 2. ([2]) Given an interpretation I = 〈Δ ^I , ·  ^I 〉, for all x ∈ Δ ^I , (T (C))  ^I  (x) =0 if there is y ∈ Δ ^I such that y ≺  _C x, and (T (C))  ^I  (x) = C ^I  (x), otherwise.

When (T (C))  ^I  (x) >0, x is said to be a typical C-element in I. Note that each relation ≺ _C has the properties of a preference relation in KLM-style ranked interpretations by Lehmann and Magidor [57] (≺ _C is a modular and well-founded strict partial order). The extension of ${\mathcal{LC}}_n$ with the typicality operator is called ${\mathcal{LC}}_n\text{T}$ .

Weighted typicality inclusions for a concept C have the form (T (C) ⊑ D _i , w _i ), and describe the prototypical properties of C-elements (where D _i is a concept, and the weight w _i is a real number); the concepts C occurring on the l.h.s. of some weighted typicality inclusions are called a distinguished concepts. A weighted ${\mathcal{LC}}_n\text{T}$ knowledge base is a tuple $〈\mathcal{T},\mathcal{D},\mathcal{A}〉$ , where the (strict) TBox $\mathcal{T}$ is a set of concept inclusions, the defeasible TBox $\mathcal{D}$ is a set of weighted typicality inclusions, and $\mathcal{A}$ is a set of assertions.

Example 1. Consider the weighted ${\mathcal{LC}}_n\text{T}$ knowledge base $K=〈\mathcal{T},\mathcal{D},\mathcal{A}〉$ , over the set of distinguished concepts {Student, Employee, …}, with $\mathcal{T}$ containing, for instance, the strict inclusion Young ⊓ Old ⊑ ⊥ ≥1.

The defeasible TBox $\mathcal{D}$ may, e.g., contain the following of weighted typicality inclusions describing the prototypical properties of students:

 (T (Student) ⊑ Has _ Courses, +80),

 (T (Student) ⊑ Young, +60),

 (T (Student) ⊑ Has _ Boss, -50),

i.e., a student normally has courses and is young, but she usually does not have a boss (negative weight). Accordingly, a young student who has courses and does not have a boss is more prototypical than a young student having courses and a boss.

The idea is that the most typical instances of concept Student are the ones satisfying the properties with a positive weight and falsifying the properties with negative weight. In the two valued case, one can evaluate how typical are two domain individuals john and tom as Students, by considering the weight of these individuals with respect of concept Student, i.e., by summing the (positive or negative) weights of the defeasible inclusions satisfied, resp., by john and tom, and comparing them. The higher the weight the more prototypical is the individual.

In many-valued DLs, each domain individual belongs to a concept to some degree. For instance, in a given interpretation I, john may be young with degree 0.7, i.e., Young ^I  (john) =0.7. This is considered in defining the weight of a domain individual x with respect to a concept C.

Given an interpretation I = 〈Δ ^I , ·  ^I 〉, the weight of x ∈ Δ ^I wrt a distinguished concept C is given by ${\mathit{weight}}_C\left(x\right)={\sum }_{\left(\text{T}\left(C\right)⊑D,w\right)\in \mathcal{T}}w·D^I\left(x\right).$

The higher the value of weight _C  (x), the more typical is x relative to the defeasible properties of C. Such a weight is expected to be related to the degree of membership of x in C, and this can be enforced based on a monotonically non-decreasing function $\phi :ℝ\to {\mathcal{C}}_n$ .

Definition 3. (φ-coherent models [2, 46]). Let $K=〈\mathcal{T},\mathcal{D},\mathcal{A}〉$ be a weighted ${\mathcal{LC}}_n\text{T}$ knowledge base, and $\phi :ℝ\to {\mathcal{C}}_n$ be a monotonically non-decreasing function. An interpretation I = 〈Δ ^I , ·  ^I 〉 is φ-coherent if

$C^I\left(x\right)=\phi \left({\mathit{weight}}_C\right(x\left)\right)$(1) holds for all x ∈ Δ ^I and all distinguished concept C in $\mathcal{D}$ . I is a φ-coherent model of K if it is a φ-coherent interpretation satisfying $\mathcal{T}$ and $\mathcal{A}$ .

Besides the φ-coherent semantics, alternative, weaker semantics have been considered for weighted knowledge bases in the fuzzy case, namely, the coherent and the faithful semantics [3]. They require that the relative weights of domain individuals with respect to a concept C should agree with the preference ≺ _C on individuals, and they can be formulated by replacing the φ-coherence condition (1) in the definition of φ-coherent model (Definition 3), respectively, with the coherence condition: x ≺  _C yiff  weight _C  (x) > weight _C  (y),

or with the (weaker) faithfulness condition: x ≺  _C y ⇒ weight _C  (x) > weight _C  (y).

As usual in preferential semantics, one restricts to canonical models, which are large enough to contain all the relevant domain elements, i.e., a domain element for any possible valuation of concepts.

Definition 4. (Canonical φ-coherent models and φ-coherent entailment) Let $K=〈\mathcal{T},\mathcal{D},\mathcal{A}〉$ be a weighted ${\mathcal{LC}}_n\text{T}$ knowledge base, and $\phi :ℝ\to {\mathcal{C}}_n$ be a monotonically non-decreasing function. An interpretation I = 〈Δ ^I , ·  ^I 〉 is a canonical φ-coherent model of K if (i) I is a φ-coherent model of K, and (ii) for each φ-coherent model J = (Δ ^J , ·  ^J ) of K and each x ∈ Δ ^J , there is an element y ∈ Δ ^I such that, for all concept names A occurring in K, A ^I  (y) = A ^J  (x).

A query E of the form T (C) ⊑ D θ l (where C and D do not contain occurrences of the typicality operator) is φ-coherently entailed by K if I ⊨ E holds for all canonical φ-coherent models I of K.

According to the above definition, for every distinguished concept C, the degree of membership of typical C-elements is the same in all canonical φ-coherent models; it is the highest degree of membership among all φ-coherent models. Without loss of generality, we can as well restrict to a unique canonical model, as in defeasible $\mathcal{ALC}$ [26]. The complexity of conditional entailment from a weighted KB in the φ-coherent semantics has been studied in [2].

Theorem 1. (Complexity of φ-coherent entailment; Theorems 1–2 in [2]). Determining whether a typicality inclusion T (C) ⊑ D θl is φ-coherently entailed by a weighted ${\mathcal{LC}}_n\text{T}$ knowledge base $K=〈\mathcal{T},\mathcal{D},\mathcal{A}〉$ is PNP[log]-complete.

As MLPs are usually represented as a weighted graphs [51], whose nodes are units and whose edges are the synaptic connections between units with their weight, it is very tempting to extend the different semantics of weighted knowledge bases considered above, to weighted argumentation graphs.

3 Many-valued coherent, faithful and φ-coherent semantics for weighted argumentation graphs

Consider the simple case when only named concepts can occur in the defeasible TBox $\mathcal{D}$ of a weighted ${\mathcal{LC}}_n\text{T}$ knowledge base. In such a case, the defeasible TBox $\mathcal{D}$ can be represented as a weighted graph where the named concepts occurring in $\mathcal{D}$ are the nodes of the graph, while each weighted conditional (T (A _i ) ⊑ A _j , w _ji ) can be represented by an edge from node A _j to node A _i , with weight w _ji .

If we regard the named concepts A _i , A _j , … ∈ N _C occurring in the defeasible TBox $\mathcal{D}$ as arguments, then $\mathcal{D}$ can be regarded as a weighted argumentation graph. The many-valued semantics developed for ${\mathcal{LC}}_n\text{T}$ weighted knowledge bases in previous section can then be reformulated as gradual semantics for the weighted argumentation graphs. In the infinitely-valued case, this has led to the definition of a notion of coherent, faithful and φ-coherent labelling of a weighted argumentation graph [42, 43], by adopting the real unit interval [0, 1] as the domain $\mathcal{S}$ of argument valuation. Here, we will consider as well the case where $\mathcal{S}$ is the finite set ${\mathcal{C}}_n$ , for n > 1.

Let a weighted argumentation graph be a triple $G=〈\mathcal{A},\mathcal{R},\pi 〉$ , where $\mathcal{A}$ is a set of arguments, $\mathcal{R}\subseteq \mathcal{A}\times \mathcal{A}$ and $\pi :\mathcal{R}\to ℝ$ . An example is in Fig. 1.

Fig. 1

Example weighted argumentation graph G.

This definition of weighted argumentation graph is similar to that of weighted argument system in [35] where, however, only positive weights are allowed, representing the strength of attacks. Here, a pair $(B,A)\in \mathcal{R}$ is regarded as a support of argument B to argument A when the weight π (B, A) is positive and as an attack of B to A when π (B, A) is negative. This leads to bipolar argumentation, which is well-studied in the literature [4, 61]. The argumentation semantics described below deals with positive and negative weights in a uniform way.

Let $\mathcal{S}$ be the interval [0, 1] or the set ${\mathcal{C}}_n$ . Given a weighted argumentation graph $G=〈\mathcal{A},\mathcal{R},\pi 〉$ , a many-valued labelling of G is a function $\sigma :\mathcal{A}\to \mathcal{S}$ which assigns to each argument an acceptability degree in the domain of argument valuation. In the following, for simplicity, we will often refer to many-valued labellings simply as “labellings”.

Let R^- (A) = $\{B\mid (B,A)\in \mathcal{R}\}$ . When R^- (A) = ∅, argument A has no supports nor attacks. For $G=〈\mathcal{A},\mathcal{R},\pi 〉$ and a many-valued labelling σ, we introduce a weight $W_{\sigma }^G$ on $\mathcal{A}$ as a partial function $W_{\sigma }^G:\mathcal{A}\to ℝ$ , assigning a positive or negative support (relative to labelling σ) to all arguments $A_i\in \mathcal{A}$ such that R^- (A _i )≠ ∅, as follows: $W_{\sigma }^G\left(A_i\right)=\sum _{(A_j,A_i)\in \mathcal{R}}\pi (A_j,A_i)\sigma \left(A_j\right)$(2) $W_{\sigma }^G\left(A_i\right)$ is left undefined when R^- (A _i ) =∅,

We exploit such a notion of weight of an argument with respect to a labelling to define some argumentation semantics for a graph G, which adapts the semantics in [42, 43] to the domain of argument valuation ${\mathcal{C}}_n$ . The next definition and proposition hold for both $\mathcal{S}=[0,1]$ and $\mathcal{S}={\mathcal{C}}_n$ , for n > 1.

Definition 5. Given a weighted argumentation graph $G=〈\mathcal{A},\mathcal{R},\pi 〉$ and $\sigma :\mathcal{A}\to \mathcal{S}$ a many-valued labelling, we say that:

σ is a coherent many-valued labelling of G if, for all arguments $A,B\in \mathcal{A}$ s.t. R^- (A)≠ ∅ and R^- (B)≠ ∅: $\sigma \left(A\right)<\sigma \left(B\right)\iff W_{\sigma }^G\left(A\right)<W_{\sigma }^G\left(B\right);$

σ is a faithful many-valued labelling of G if, for all arguments $A,B\in \mathcal{A}$ s.t. R^- (A)≠ ∅ and R^- (B)≠ ∅: $\sigma \left(A\right)<\sigma \left(B\right)\Rightarrow W_{\sigma }^G\left(A\right)<W_{\sigma }^G\left(B\right);$

given a non-decreasing function $\phi :ℝ\to \mathcal{S}$ , σ is a φ-coherent many-valued labelling of G if, for all arguments $A\in \mathcal{A}$ , s.t. R^- (A)≠ ∅, $\sigma \left(A\right)=\phi \left(W_{\sigma }^G\right(A\left)\right)$(3)

Observe that the notion of φ-coherent many-valued labelling of G is defined through a set of equations, as in Gabbay’s equational approach to argumentation networks [37]. The notions of coherent, faithful and φ-coherent many-valued labelling of a weighted argumentation graph G do not put constraints on the labelling of arguments without incoming edges, provided the constraints on the labellings of all other arguments can be satisfied, depending on the semantics considered. In particular, our definition of weighted argumentation graph above, does not consider a base score, (i.e., an initial valuation of arguments) as usual in argumentation frameworks. In essence, we want to consider all the possible initial valuations for the arguments without incoming edges. We refer to Section 4 for a comparison between the φ-coherent semantics and the frameworks of gradual semantics studied by Amgoud and Doder [5] and by Potyka [61].

It can be proven that the relationships between the faithful, the coherent and the φ-coherent semantics, stated for the fuzzy case in [42], also extend to the finitely-valued case. Let $\mathcal{S}$ be either [0, 1] or ${\mathcal{C}}_n$ .

Proposition 1. Given $G=〈\mathcal{A},\mathcal{R},\pi 〉$ and $\phi :ℝ\to$ $\mathcal{S}$ , (1) a coherent many-valued labelling $\sigma :\mathcal{A}\to \mathcal{S}$ of G is a faithful many-valued labelling of G; (2) if φ is a monotonically non-decreasing function, a φ-coherent many-valued labelling σ of G is a faithful many-valued labelling of G; (3) if φ is monotonically increasing, a φ-coherent many-valued labelling σ of G is a coherent many-valued labelling of G.

Proof. The proof exploits the property of a φ-coherent many-valued labelling that $\sigma \left(A\right)=\phi \left(W_{\sigma }^G\right(A\left)\right)$ , for all arguments A with R^- (A)≠ ∅, as well as the properties of φ.

Item (1) is obvious from the definitions of coherent and faithful many-valued labellings. For item (2), let us assume that φ is monotonically non-decreasing and that σ is φ-coherent many-valued labelling of G. Then, for all $A\in \mathcal{A}$ such that R^- (A)≠ ∅, $\sigma \left(A\right)=\phi \left(W_{\sigma }^G\right(A\left)\right)$ . We have to prove that for all arguments $A,B\in \mathcal{A}$ s.t. R^- (A)≠ ∅ and R^- (B)≠ ∅, $\sigma \left(A\right)<\sigma \left(B\right)\Rightarrow W_{\sigma }^G\left(A\right)<W_{\sigma }^G\left(B\right).$ If σ (A) < σ (B) holds, from the hypothesis that R^- (A)≠ ∅ and R^- (B)≠ ∅, by condition (3), we have $\phi \left(W_{\sigma }^G\right(A\left)\right)<\phi \left(W_{\sigma }^G\right(B\left)\right)$ . By absurd, let us assume that the conclusion $W_{\sigma }^G\left(A\right)<W_{\sigma }^G\left(B\right)$ does not hold. Then $W_{\sigma }^G\left(A\right)\ge W_{\sigma }^G\left(B\right)$ . As φ is non-decreasing, $\phi \left(W_{\sigma }^G\right(A\left)\right)\ge \phi \left(W_{\sigma }^G\right(B\left)\right)$ holds, a contradiction.

For item (3), let us assume that φ is monotonically increasing and that σ is φ-coherent many-valued labelling of G. Then, for all $A\in \mathcal{A}$ sucht that R^- (A)≠ ∅, $\sigma \left(A\right)=\phi \left(W_{\sigma }^G\right(A\left)\right)$ . We have to prove that for all arguments $A,B\in \mathcal{A}$ s.t. R^- (A)≠ ∅ and R^- (B)≠ ∅, $\sigma \left(A\right)<\sigma \left(B\right)\iff W_{\sigma }^G\left(A\right)<W_{\sigma }^G\left(B\right).$

The “⇒” direction holds with the same proof as for item (2), as φ is monotonically non-decreasing. For the “⇐” direction, let $W_{\sigma }^G\left(A\right)<W_{\sigma }^G\left(B\right)$ . As φ is monotonically increasing, $\phi \left(W_{\sigma }^G\right(A\left)\right)<\phi \left(W_{\sigma }^G\right(B\left)\right)$ holds. As R^- (A)≠ ∅ and R^- (B)≠ ∅, since σ is a φ-coherent many-valued labelling of G, the equivalences $\sigma \left(A\right)=\phi \left(W_{\sigma }^G\right(A\left)\right)$ and $\sigma \left(B\right)=\phi \left(W_{\sigma }^G\right(B\left)\right)$ hold and, hence, σ (A) < σ (B) holds.□

In the following, for the φ-coherent semantics, we will make the assumption that $\phi :ℝ\to \mathcal{S}$ is a monotonically non-decreasing function.

Restricting the domain of argument valuation to the finite number of values in ${\mathcal{C}}_n$ , allows considering finitely-valued labellings which approximate the semantics considered in [42, 43] with domain of argument valuation in [0, 1]. In the following example, for $\mathcal{S}={\mathcal{C}}_n$ , we will assume function φ to be the pointwise approximation of the logistic function S (x) =1/(1 + e^-x) (i.e., S (x) is approximated to the closest value in ${\mathcal{C}}_n$ ).

Example 2. For $\mathcal{S}={\mathcal{C}}_n$ with n = 5, the graph G in Fig. 1 has 36 φ-coherent many-valued labellings, while, for n = 9, G has 100 φ-coherent many-valued labellings. For instance, σ = (0, 4/5, 3/5, 2/5, 2/5, 3/5) (meaning that σ (A₁) =0, σ (A₂) =4/5, and so on) is a labelling for n = 5. Consider, e.g., A₄; the φ-coherence condition indeed holds, i.e., $\sigma \left(A_4\right)=\phi \left(W_{\sigma }^G\right(A_4\left)\right)$ . In fact, $W_{\sigma }^G$ (A₄) =4/5 -1.5 * 3/5 = -0.1; $S\left(W_{\sigma }^G\right(A_4\left)\right)=S(-0.1)=0.475$ , and then $\phi \left(W_{\sigma }^G\right(A_4\left)\right)=2/5$ .

In [42, 43] it has been shown that, for labellings with values in [0, 1], the notion of φ-coherent labelling relates to the framework of gradual semantics studied by Amgoud and Doder [5], by considering a slight extension of their gradual argumentation framework so to deal with both positive and negative weights, to capture the strength of supports and attacks. The notion of bipolar argumentation has been widely studied in the literature [6, 61]. In particular, an extension of the bipolar argumentation framework QBAFs by Baroni et al. [10] which includes the strength of attacks and supports has been developed and studied by Potyka [61].

Let us observe that, since MultiLayer Perceptrons (MLPs) can be mapped to weighted conditional knowledge bases [3], they can as well be seen as weighted argumentation graphs, with positive and negative weights, under the proposed semantics. In this view, φ-coherent many-valued labellings of a weighted argumentation graph correspond to stationary states [51] of the network, where each unit in the network is associated to an argument, synaptic connections (with their weights) correspond to attacks/supports, and the activation of units correspond to the values of the corresponding arguments in a many-valued labelling. This is in agreement with previous work on the relationship between argumentation frameworks and neural networks investigated by d’Avila Garcez, Gabbay and Lamb [33] and more recently by Potyka [61]. Note that cycles are admitted both in weighted KBs and in weighted argumentation graphs, so that the φ-coherent many-valued labellings of a weighted argumentation graph represent the stationary states of a recurrent network.

4 φ-coherent labellings and the gradual semantics

To clarify the relationships between our semantic definition and the above mentioned frameworks, we exploit a reformulation (developed in [42, 43]) of the φ-coherent semantics in the framework of gradual semantics studied by Amgoud and Doder [5], accounting for varied-strength attacks. Then, we will compare with the framework studied by Potyka [61], which also deals with positive and negative weights.

First, let us consider an initial valuation of arguments by introducing, as in [5], a function ${\sigma }_0:\mathcal{A}\to [0,1]$ in the definition of a weighted graph, where σ₀ assigns to each argument $A\in \mathcal{A}$ its basic strength (also called base score). Hence, a graph G becomes a quadruple $G=〈\mathcal{A},{\sigma }_0,\mathcal{R},\pi 〉$ .

Then, let us consider a notion of evaluation method which deals with positive and negative (real valued) weights, as considered in [43]. An evaluation method for a graph $G=〈\mathcal{A},{\sigma }_0,\mathcal{R},\pi 〉$ is a triple M = 〈  h, g, f〉, where 1 :

  $h:ℝ\times [0,1]\to ℝ$

  $g:{\bigcup }_{n=0}^{+\infty }{ℝ}^n\to ℝ$

 f : [0, 1] × Range (g) → [0, 1]

Function h is intended to calculate the strength of an attack/support by aggregating the weight on the edge between two arguments with the strength of the attacker/supporter. Function g aggregates the strength of all attacks and supports to a given argument, and function f returns a value for an argument, given the strength of the argument and aggregated weight of its attacks and supports.

Following [5], a gradual semantics S is a function assigning to any graph $G=〈\mathcal{A},{\sigma }_0,\mathcal{R},\pi 〉$ a weighting ${\mathit{Deg}}_G^S$ on $\mathcal{A}$ , i.e., ${\mathit{Deg}}_G^S:\mathcal{A}\to [0,1]$ , where ${\mathit{Deg}}_G^S\left(A\right)$ represents the strength of an argument A (or its acceptability degree).

A gradual semantics S is based on an evaluation method M iff, $\forall G=〈\mathcal{A},{\sigma }_0,\mathcal{R},\pi 〉$ , $\forall A\in \mathcal{A}$ ,

${\mathit{Deg}}_G^S\left(A\right)=f\left({\sigma }_0\right(A),g(h\left(\pi \right(B_1,A),{\mathit{Deg}}_G^S(B_1\left)\right)$ ,

…,

$h\left(\pi \right(B_n,A),{\mathit{Deg}}_G^S(B_n\left)\right))$

where B₁, …, B _n are all arguments attacking or supporting A, i.e., R^- (A) = {B₁, …, B _n }  2

We can now consider a specific evaluation method M ^φ  = 〈  h _prod , g _sum , f _φ 〉 which is intended to capture the φ-coherent semantics (see [43]), where the functions h _prod and g _sum are defined as in [5], i.e., h _prod  (x, y) = x · y and $g_{\mathit{sum}}(x_1,\dots ,x_n)={\sum }_{i=1}^n{x}_i$ , for n > 0, but we let g _sum  () to be undefined. We further let: f _φ  (x, y) = x when y is undefined, and f _φ  (x, y) = φ (y) otherwise. That is, function f _φ returns a value which is independent from the first argument, when the second argument is not undefined (i.e., there is some support/attack for the argument). When A has neither attacks nor supports (R^- (A) =∅), f _φ returns the basic strength of A, σ₀ (A). Together with the fact that we allow for negative weights, this gives an intuition why our semantics differs from the semantics considered in Amgoud and Doder’s family of gradual semantics [5].

The evaluation method M ^φ  = 〈  h _prod , g _sum , f _φ 〉 provides a characterization of the φ-coherent many-valued labelling for an argumentation graph, in the following sense.

Proposition 2. [1] Let $G=〈\mathcal{A},\mathcal{R},\pi 〉$ be a weighted argumentation graph. If, for some ${\sigma }_0:\mathcal{A}\to [0,1]$ , S is a gradual semantics based on the evaluation method M ^φ  = 〈  h _prod , g _sum , f _φ 〉 for graph $G^{\prime }=〈\mathcal{A},{\sigma }_0,\mathcal{R},\pi 〉$ , then ${\mathit{Deg}}_{G^{\prime }}^S$ is a φ-coherent many-valued labelling for G.

Vice-versa, if σ is a φ-coherent many-valued labelling for G, then there are a function σ₀ and a gradual semantics S based on the evaluation method M ^φ  = 〈  h _prod , g _sum , f _φ 〉 for the graph $G^{\prime }=〈\mathcal{A},{\sigma }_0,\mathcal{R},\pi 〉$ , such that, ${\mathit{Deg}}_{G^{\prime }}^S\equiv \sigma$ .

Amgoud and Doder [5] study a large family of determinative and well-behaved evaluation models for weighted graphs in which attacks have positive weights in the interval [0, 1]. For weighted graph G with positive and negative weights, the evaluation method M ^φ cannot be guaranteed to be determinative (that is, we cannot guarantee that there is a unique semantics S of G based on M ^φ ), even under the conditions that φ is monotonically increasing and continuous. In general, there is not a unique semantics S based on M ^φ , as there is not a unique φ-coherent labelling for a weighted graph G, given a basic strength σ₀. This is not surprising, considering that φ-coherent labellings of a graph correspond to stationary states (or equilibrium states) of a deep neural network [51].

In particular, unless the network is feedforward (and the corresponding graph is acyclic), stationary states cannot be uniquely determined by an iterative process from an initial labelling σ₀. On the other hand, a semantics S based on M ^φ satisfies some of the properties considered in [5] and, specifically: Anonymity (the strength of an argument does not depend on its identity), Independence (the strength of an argument depends only on arguments that are related to it with a path), Directionality (the strength of an argument does not depend on argument’s outgoing arrows). Also Equivalence, Maximality and Reinforcement are satisfied, provided they are properly reformulated to deal with both positive and negative weights (i.e., by replacing Att (x) in the formulation in [5], with R^- (x) so to consider both attackers and supporters of an argument x). With this reformulation, Equivalence (the strength of an argument depends only on the argument’s basic strength, the weights of its direct attacks/supports and the strengths of its direct attackers/supporters), Maximality (the strength of an argument is equal to the argument’s basic weight if the argument is not attacked/supported), hold, Reinforcement (the strength of an argument is sensitive to the quality of attackers/supporters) hold. A reformulation of Attack-sensitivity, with the meaning that, the higher the (real) weight π (B, A) of a pair $(A,B)\in \mathcal{R}$ , the greater is the strength of argument A (provided the strength of argument B is different from 0), also holds.

However, a semantics S based on M ^φ cannot be expected to satisfy the properties of Neutrality Weakening, Proportionality, Resilience and Counting (even if properly reformulated to deal with both positive and negative weights). In fact, function f _φ completely disregards the initial score σ₀ (A), for those arguments A having incoming edges in a graph G (even if their strength is equal to 0 or their weight is 0). In particular, it is not the same for an argument to have a support with weight 0 or no support or attack at all: Neutrality does not hold.

The work by Potyka [61] considers a quantitative bipolar argumentation frameworks (QBAFs) similar to [10] and exploits an influence function based on the logistic function to define an MLP-based semantics σ _MLP for QBAFs. In particular, an edge-weighted QBAF is a quadruple $Q=(\mathcal{A},E,\beta ,w)$ , where $\mathcal{A}$ is a set of arguments, $E\subseteq \mathcal{A}\times \mathcal{A}$ is a set of edges between arguments, β is a function assigning a base score β (a) to each argument $a\in \mathcal{A}$ , and $w:E\to ℝ$ assigns a weight to every edge. For each argument $a\in \mathcal{A}$ , the interpretation of Q under MLP-based semantics is given by a function σ _MLP defined by: ${\sigma }_{\mathit{MLP}}\left(a\right)=\underset{k\to \infty }{lim}{s}_a^{\left(k\right)}$ , when the limit exists, and ⊥ (undefined) otherwise; where $s_a^{\left(k\right)}$ is a value in the interval [0, 1], and k represents the iteration. More precisely, for all arguments $a\in \mathcal{A}$ ,

  $s_a^{\left(0\right)}=\beta \left(a\right)$ (initial strength),

  $s_a^{(i+1)}={\phi }_l\left(\mathit{ln}\right(\frac{\beta \left(a\right)}{1+\beta \left(a\right)})+{\alpha }_a^{(i+1)})$ (influence),

where φ _l is the logistic function and ${\alpha }_a^{(i+1)}={\sum }_{(b,a)\in E}w(b,a)·s_b^{\left(i\right)}.$

Potyka in [61] studies convergence conditions both in the discrete and in the continuous case, as well as the semantic properties of MLP-based semantics, by analyzing the properties that hold at the fixed-point of u _MLP . It is proven that all properties proposed in [7] are satisfied. As we have seen above, our semantics based on φ-coherent models fails to satisfy some of the properties in [5] (which extend the properties in [7] to account for weights of attacks): the strength of an argument is insensitive to the argument’s base score, when the argument has at least an attacking or a supporting argument, while it coincides with the base score when the argument has no attacking or supporting arguments.

The next section introduces a notion of preferential interpretation of an argumentation graph G under an argumentation semantics. Section 6 establishes a mapping between the φ-coherent semantics of a weighted argumentation graph and the φ-coherent semantics of the corresponding weighted knowledge base.

5 A preferential interpretation of a weighted argumentation graph under the φ-coherent semantics

The strong relations between the notions of coherent, faithful and φ-coherent labellings of a gradual argumentation graph and the corresponding semantics of weighted conditional knowledge bases have suggested an approach for defeasible reasoning over a weighted argumentation graph [42, 43] which builds on the φ-coherent semantics of the argumentation graph.

This approach has been generalized in [1] to develop a preferential interpretation of an argumentation graph with respect to an arbitrary gradual semantics, provided the semantics satisfies the assumption that the domain of argument interpretation is equipped with a preorder relation (an assumption also considered by Baroni, Rago and Toni [10, 11] in their definition of a Quantitative Bipolar Argumentation Framework, QBAF). This provides a general approach for the verification of conditional properties of an argumentation graph, under a gradual semantics, based on the preferential interpretation that can be constructed from the labellings of the graph in that semantics.

Here we restrict to weighted graphs and to the φ-coherent semantics introduced in Section 3, with the aim of extending the proof methods for conditional reasoning from weighted KBs to the verification of graded conditionals over a weighted argumentation graph, as well as identifying the complexity of the problem and developing translations from weighted KBs to weighted argumentation graphs, and vice-versa.

In the following, we introduce a propositional language to represent boolean combination of arguments and a many-valued semantics for it over the domain $\mathcal{S}$ of argument valuation (again, we assume $\mathcal{S}$ to be either [0, 1] or ${\mathcal{C}}_n$ ). Then, we extend the language with a typicality operator, to introduce defeasible implications over boolean combinations of arguments and define a (multi-)preferential interpretation associated with the argumentation graph G and a set of many-valued labellings Σ.

The preferential semantics relies on the argumentation semantics of a graph G (as the ones introduced in Section 3), to provide an interpretation built from the many-valued labellings of G in that semantics. Such an interpretation is then used for the verification of properties concerning arguments in the graph G and, in particular, we will consider conditional properties.

Given an argumentation graph $G=〈\mathcal{A},\mathcal{R},\pi 〉$ , let $\mathcal{L}$ be a propositional language whose set of propositional variables Prop is the set of arguments $\mathcal{A}$ . We assume that the language $\mathcal{L}$ contains the connectives ∧, ∨, ¬ and →, and that the formulas are defined inductively, as usual. In the following we call the formulas built from the propositional variables in $\mathcal{A}$ using connectives ∧, ∨ and ¬ boolean combination of arguments (and denote them with α, β, γ).

Let ⊗, ⊕, ⊳ and ⊖ be the truth degree functions in the truth degree set $\mathcal{S}$ for the connectives ∧, ∨, ¬ and → (respectively). As $\mathcal{S}$ is either [0, 1] or the finite set ${\mathcal{C}}_n$ (with n > 1), ⊗, ⊕, ⊳ and ⊖ can be chosen as t-norm, s-norm, implication function, and negation function in some system of many-valued logic [50].

A many-valued labelling $\sigma :\mathcal{A}\to \mathcal{S}$ of graph G, assigning to each argument $A_i\in \mathcal{A}$ a truth degree in $\mathcal{S}$ , can be regarded as a many-valued valuation, which can be inductively extended to all propositional formulas of $\mathcal{L}$ as follows:

σ (α ∧ β) = σ (α) ⊗ σ (β), σ (α ∨ β) = σ (α) ⊕ σ (β), σ (α → β) = σ (α) ⊳ σ (β), and σ (¬ α) = ⊖ σ (α). Based on the choice of the combination functions, a labelling σ uniquely assigns a truth degree to any formula of $\mathcal{L}$ (and to any boolean combination of arguments α). We assume the false and true arguments, ⊥ and ⊤, are formulas of $\mathcal{L}$ and that σ (⊥) =0 and σ (⊤) =1, for all σ.

The semantics of an argumentation graph G is then (abstractly) identified by a pair $(\mathcal{S},\Sigma )$ , where Σ is a set of many-valued labellings with truth values in $\mathcal{S}$ .

5.1 Preferences with respect to arguments

Given a semantics $(\mathcal{S},\Sigma )$ , for any boolean combination of arguments α, we introduce a preference relation < _α on the set of labellings Σ.

Definition 6. Given a semantics $(\mathcal{S},\Sigma )$ , for each boolean combination of arguments α, the preference relation < _α on Σ, is defined as follows: for σ, σ′ ∈ Σ, σ <  _α σ′ iff σ′ (α) < σ (α) .

Relation σ <  _α σ′ means that labelling σ is preferred to labelling σ′ with respect to the boolean combination of arguments α; that is, σ represents a situation more plausible than σ′ for argument α to hold.

The preference relation < _α is a strict modular partial order relation on Σ.

Example 3. Let us continue Example 2, with $\mathcal{S}=$ ${\mathcal{C}}_n$ . Referring to graph G in Fig. 1, among the set Σ of 36 φ-coherent many-valued labellings of G for n = 5, there are two labellings σ and σ′ such that σ′ (A₁) =0 < σ (A₁) =1/5. and σ′ (A₃) =1 > σ (A₃) =4/5. Hence σ <  _{A 1} σ′ and σ′ <  _{A 3} σ.

For instance, σ = (1, 4/5, 0, 1, 1/5, 1) is preferred to all other labellings with respect to < _{A 6} , being the only one with σ (A₆) =1.

Under Gödel logic with standard involutive negation, for G in Fig. 1, with n = 5, the boolean combination of arguments A₁ ∧ A₂ ∧ ¬ A₃ has 4 maximally preferred labellings, with σ (A₁ ∧ A₂ ∧ ¬ A₃) =4/5.

When the truth value set is [0, 1], the set Σ of many-valued labellings of a graph in the faithful, coherent, φ-coherent argumentation semantics may be infinite, and the preference relations < _α are not guaranteed to be well-founded, as there may be infinitely-descending chains of labellings. This is not the case when $\mathcal{S}={\mathcal{C}}_n$ .

Let us define the preferential interpretation of a graph with respect to the set of many-valued labellings determined by its semantics.

Definition 7. Given an argumentation graph G, and a semantics $(\mathcal{S},\Sigma )$ , the preferential interpretation of G with respect to $(\mathcal{S},\Sigma$ ) is the triple $I=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ .

We have made explicit the preference relations < _α on the set of labellings Σ of the graph, for boolean combinations of arguments α, although such preferences are induced by the labellings in Σ.

Language ${\mathcal{L}}^{\text{T}}$ is obtained by extending language $\mathcal{L}$ with a unary typicality operator T. Intuitively, “a sentence of the form T (α) is understood to refer to the typical situations in which α holds” [20]. The typicality operator allows for the formulation of conditional implications (or defeasible implications) of the form T (α) → β whose meaning is that "normally, if α then β", or "in the typical situations when α holds, β also holds". They correspond to conditional implications α| ∼ β of KLM preferential logics [57]. As in [20] and in [48], the typicality operator cannot be nested. When α and β do not contain occurrences of the typicality operator, an implication α → β is called strict 3 .

The interpretation of a typicality formula T (α) is defined with respect to a preferential interpretation $I=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ . Informally, the preference relation < _α allows to identify the most typical situations in which α holds.

Definition 8. Given a preferential interpretation $I=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ , and a many-valued labelling σ ∈ Σ, the valuation of a propositional formula T (α) in σ is defined as follows: σ (T (α)) = σ (α) if there is no σ′ ∈ Σ such that σ′ <  _α σ; and σ (T (α)) =0, otherwise.

When σ (T (α)) >0, σ is a labelling assigning a maximal degree of acceptability to the boolean combination of arguments α in I, i.e., it maximizes the acceptability of the boolean combination of arguments α, among all the labellings in I.

Example 4. Let us consider the interpretation $I=({\mathcal{C}}_5,\Sigma ,\{{<}_{\alpha }\left\}\right)$ , where Σ is the set of labellings of graph G in Fig. 1 in the φ-coherent semantics with truth space ${\mathcal{C}}_5$ . For the (unique) labelling σ preferred for A₆ (see example 3), σ (T (A₆)) =1. For all other labellings σ′ ∈ Σ, σ′ (T (A₆)) =0. For the 4 labellings σ₁, …, σ₄ that are the preferred ones for A₁ ∧ A₂ ∧ ¬ A₃ (see Example 3), σ _i  (T (A₁ ∧ A₂ ∧ ¬ A₃)) =4/5.

5.2 Graded implications

Given a preferential interpretation I of a weighted argumentation graph, we can define the satisfiability in I of a graded implication, having form α → β ≥ l or α → β ≤ u, with l and u in $\mathcal{S}$ , and α and β boolean combination of arguments. We first define the truth degree of an implication α → β wrt a preferential interpretation I as follows:

Definition 9. Given a preferential interpretation $I=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ of an argumentation graph G, the truth degree of an implication α → β wrt. I is defined as:

  $(\alpha \to \beta {)}^I=\underset{\sigma \in \Sigma }{\mathit{inf}}(\sigma \left(\alpha \right)⊳\sigma \left(\beta \right))$ .

We can now define the satisfiability of a graded implication in an interpretation I.

Definition 10. Given a preferential interpretation $I=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ of an argumentation graph G, I satisfies a graded implication α → β ≥ l (written I ⊨ α → β ≥ l) iff (α → β)  ^I  ≥ l; I satisfies a graded implication α → β ≤ u (written I ⊨ α → β ≤ u) iff (α → β)  ^I  ≤ u.

Example 5. As mentioned before, for the weighted argumentation graph in Fig. 1, there are 36 labellings in case n = 5. The following graded conditionals are satisfied in I:

T (A₁ ∧ A₂ ∧ ¬ A₃) → A₆ ≥ 1 (with 4 preferred labellings);

T (A₁ ∧ A₂) → A₆ ≥ 4/5 (12 preferred labellings);

T (A₁ ∧ A₂) → A₆ ≥ 4/5;

T (A₆) → A₁ ∧ A₂ ≥ 4/5 (1 preferred labelling).

On the other hand, for instance, the strict implication A₆ → A₁ ∧ A₂ ≥ 1/5 does not hold in I.

Notice that the valuation of a graded implication (e.g., α → β ≥ l) in a preferential interpretation I is two-valued, that is, either the graded implication is satisfied in I (i.e., I ⊨ α → β ≥ l) or it is not (i.e., Inotmodelsα → β ≥ l). Hence, it is natural to consider boolean combinations of graded implications, such as

(T (A₁)→ A₂ ∧ A₃ ≥ 0.7) ∧

((T (A₃) → A₄) ≥0.6) ∨ (T (A₁) → A₄) ≥0.6))

by defining their satisfiability in an interpretation I in the obvious way, based on the semantics of classical propositional logic.

The preferential interpretation I of a graph G in a gradual semantics can be used to validate properties of interest of an argumentation graph, expressed by graded implications.

Next, we first define a mapping of argumentation graphs to weighted KBs under the φ-coherent semantics (Section 6). In Section 7, we use such a mapping to obtain an upper bound on the complexity of φ-coherent entailment (Definition 4) for $\mathcal{S}={\mathcal{C}}_n$ ; the complexity lower bound is given by a reduction from the max sat odd problem. The complexity result suggests that a mapping in the other direction does exist, and we define it in Section 8.

6 Mapping argumentation graphs to weighted KBs under the φ-coherent semantics

Let us establish a relationship between weighted argumentation graphs under the φ-coherent semantics for $\mathcal{S}={\mathcal{C}}_n$ and the weighted ${\mathcal{LC}}_n\mathcal{T}$ knowledge bases defined in Section 2, under the φ-coherent semantics.

Let us consider a weighted argumentation graph $G=〈\mathcal{A},\mathcal{R},\pi 〉$ , as in Section 3, and its φ-coherent semantics, for some monotonically non-decreasing function $\phi :ℝ\to \mathcal{S}$ . Let $I_G=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ be the preferential interpretation of the argumentation graph G under the φ-coherent semantics, for some choice of combination functions.

By interpreting arguments $A_i\in \mathcal{A}$ as a named concept in the logic ${\mathcal{LC}}_n\mathcal{T}$ , we can define a conditional knowledge base $K^G=(\mathcal{T},\mathcal{D},\mathcal{A})$ associated with G, as follows:

$\mathcal{T}=\mathcal{A}=\varnothing$ , and

$\mathcal{D}=\left\{\right(\mathcal{T}\left({\mathcal{A}}_i\right)⊑{\mathcal{A}}_j,{\mathcal{w}}_{\mathcal{ji}})\mid ({\mathcal{A}}_j,{\mathcal{A}}_i)\in \mathcal{R}\mathcal{and}$

      w ((A _j , A _i )) = w _ji }

Note that, for any boolean combination of arguments α (e.g., α = A₁ ∧ (A₂ ∨ ¬ A₃)) there is a correspondent boolean concept (e.g., C _α  = A₁ ⊓ (A₂ ⊔ ¬ A₃)), obtained by replacing the connectives ∧, ∨ and ¬ with the DL operators ⊓, ⊔ and ¬. Let us consider the semantics of logic ${\mathcal{LC}}_n\mathcal{T}$ with the same choice of combination functions adopted in the interpretation I _G of the graph G. It can be proven that:

Proposition 3. Given the preferential interpretation I _G of an argumentation graph G under the φ-coherent semantics, there is a canonical φ-coherent model I of the weighted knowledge base K ^G such that, for each graded conditional implication T (α) → β θ l: T (α) → β θ l satisfied in I _G if and only if the corresponding typicality inclusion T (C _α ) ⊑ C _β  θ l is satisfied in I.

Sketch. Given the interpretation $I_G=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ , the thesis can be proved by building a canonical interpretation of K ^G in ${\mathcal{LC}}_n\mathcal{T}$ , whose domain is the set Σ of all many-valued labelling of the weighted graph G.

Let $N_C=\mathcal{A}$ , and let N _I  = {x₁, x₂, …} contain one individual name x _j for each labelling σ _j  ∈ Σ. We can define an ${\mathcal{LC}}_n\mathcal{T}$ preferential interpretation I = 〈 Δ ^I , ·  ^I ) as follows:

Δ ^I  = Σ;

for all x _j  ∈ N _I , $x_j^I={\sigma }_j$ ;

for all A ∈ N _C , A ^I  (σ _j ) = σ _j  (A).

As usual in ${\mathcal{LC}}_n\mathcal{T}$ interpretations, the valuation function · ^I induces, for each concept A _i  ∈ N _C , a preference relation ${<}_{A_i}^{\prime }$ on Δ ^I such that:

${\sigma }_j{<}_{A_i}^{\prime }{\sigma }_k$   iff   $A_i^I\left({\sigma }_j\right)>A_i^I\left({\sigma }_k\right)$

Hence, by construction, ${\sigma }_j{<}_{A_i}^{\prime }{\sigma }_k$   iff   σ _j  (A _i ) > σ _k  (A _i )

so that the preference relations ${<}_{A_i}^{\prime }$ defined on the domain of the ${\mathcal{LC}}_n\mathcal{T}$ interpretation I correspond to the preference relations < _{A i} in the interpretation I _G .

This holds as well for preferences < _α with respect to boolean combinations of arguments α, as each boolean combination of arguments α corresponds to a boolean concept C _α , and it is easy to prove that $C_{\alpha }^I\left(\sigma \right)=\sigma \left(\alpha \right)$ , given that the same truth degree functions are used for interpreting boolean combination of arguments in I _G and complex concepts in I. For instance, $(A_1\sqcap A_2\sqcap \neg A_3{)}^I(\sigma )=A_1^I(\sigma )\otimes A_2^I(\sigma )\otimes \ominus A_3^I(\sigma )=\sigma (A_1)\otimes \sigma (A_2)\otimes \ominus \sigma (A_3)=\sigma (A_1\wedge A_2\wedge \neg A_3)$ , where A₁ ⊓ A₂ ⊓ ¬ A₃ is the boolean concept corresponding to the boolean combination of arguments A₁ ∧ A₂ ∧ ¬ A₃.

From the fact that each labelling σ _j  ∈ Σ is a φ-coherent labelling of G, one can prove that the φ-coherence condition (1) is satisfied for each domain element in Δ ^I and for each concept C occurring on the left hand side of a weighted inclusion. Hence, the model I is a φ-coherent model of K ^G .

To prove that I is a canonical φ-coherent model of K ^G , one has to prove that, for any φ-coherent model J = (Δ ^J , ·  ^J ) of K ^G and domain element z ∈ Δ ^J , there must be an element y ∈ Δ ^I such that, for all concept names A _i occurring in K ^G , $A_i^I\left(y\right)=A_i^J\left(z\right)$ . As J is a φ-coherent model of K ^B , for each A _i occurring on the l.h.s. of a weighted implication

$A_i^I\left(z\right)=\phi \left(\sum _{\left(\text{T}\left(A_i\right)⊑A_j,w_{\mathit{ji}}\right)\in \mathcal{T}}{w}_{\mathit{ji}}·A_j^I\left(z\right)\right)$(4) Then z determines a labelling σ _z of G, defined as ${\sigma }_z\left(A_j\right)=A_j^I\left(z\right)$ , for all arguments A _j . By equation (4), σ _z is a φ-coherent labelling of G. Hence it must be that σ _z  ∈ Σ. Therefore, σ _z  ∈ Δ ^I .

Thus, I is a canonical φ-coherent model of K ^S . It is easy to prove that, for each graded implication T (α) → β θ l (with θ in {≤ , ≥}), T (α) → β θ l is satisfied in I _G if and only if the corresponding typicality inclusion T (C _α ) ⊑ C _β  θ l is satisfied in I. □

Observe that the proof above does not depend on the choice of the truth degree set $\mathcal{S}={\mathcal{C}}_n$ . For the case when the truth degree set $\mathcal{S}$ is [0, 1], a mapping from weighted argumentation graphs to weighted knowledge bases in the fuzzy description logic $\mathcal{LC}\text{T}$ [3] can be defined in a similar way.

We can exploit the correspondence established by Proposition 3 to provide a proof method for verifying the conditional properties of an argumentation graph G under the φ-coherent semantics. As we have seen from the proof of Proposition 3, the set Σ of all the φ-coherent many-valued labellings of G can be regarded as the domain of a canonical φ-coherent model of the knowledge base K ^G . This allows the entailment algorithms developed for weighted ${\mathcal{LC}}_n\text{T}$ knowledge bases (see [2]) to be exploited in the verification of conditional properties of an argumentation graph G under the φ-coherent semantics in the finitely-valued case.

7 Verifying conditional properties of weighted argumentation graphs in the φ-coherent semantics: a complexity result

This section is devoted to establishing the exact complexity to determine if a graded implication T (α) → β θ l is satisfied in the preferential interpretation I _G of a weighted argumentation graph $G=〈\mathcal{A},$ $\mathcal{R},\pi 〉$ under the φ-coherent semantics with truth degree set ${\mathcal{C}}_n$ introduced in Section 3. From the mapping in previous section and the result about the polynomial complexity for the verification of typicality inclusions over a preferential interpretation [12], one can conclude that verifying a graded implication T (α) → β θ l over the interpretation I _G has a polynomial cost in the size of the interpretation itself. However, I _G might contain an exponential number of labellings in the size of $\left|\mathcal{A}\right|$ .

In the following, we show that verifying whether a graded implication T (α) → β θ l over the interpretation $I_G=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ , where Σ is the set of all the φ-coherent many-valued labellings of the weighted graph G is a PNP[log]-complete problem, that is, the next theorem holds.

Theorem 2. (Complexity result) Let $G=〈\mathcal{A},$ $\mathcal{R},\pi 〉$ be an argumentation graph. Determining if a graded implication T (α) → β θ l is satisfied in the preferential interpretation I _G of G, under the φ-coherent semantics with the truth degree set $\mathcal{S}={\mathcal{C}}_n$ , is PNP[log]-complete in the size of the argumentation graph.

Given the mapping from Section 6, and the PNP[log]-membership of deciding φ-coherent entailment of inclusion T (C) ⊑ D θ α from a weighted ${\mathcal{LC}}_n\text{T}$ knowledge base K (Theorem 1 in [2]), the next result is established.

Proposition 4. (Complexity upper bound) Let $G=〈\mathcal{A},$ $\mathcal{R},\pi 〉$ be an argumentation graph. Determining if a graded implication T (α) → β θ l is satisfied in the preferential interpretation I _G of G, under the φ-coherent semantics with the truth degree set $\mathcal{S}={\mathcal{C}}_n$ , is in PNP[log].

To complete the proof of Theorem 2, we provide a strict lower bound to the complexity of entailment.

Proposition 5. (Complexity lower bound) Let $G=〈\mathcal{A},$ $\mathcal{R},\pi 〉$ be an argumentation graph. Determining if a graded implication T (α) → β θ l is satisfied in the preferential interpretation I _G of G, under the φ-coherent semantics with the truth degree set $\mathcal{S}={\mathcal{C}}_n$ , is PNP[log]-hard in the size of the argumentation graph G, even if α and β are arguments $A_i\in \mathcal{A}$ , and θ l is fixed to ≥1.

In the following, we prove the above claim by providing a reduction from the problem max sat even. max sat even asks for the parity of the maximum number of jointly satisfiable clauses in a given set. (The problem is often formulated as max sat odd, [65]). Let Γ = {γ₁, …, γ _n } be a set of n ≥ 1 clauses of propositional logic, and let vars (Γ) be the set of boolean variables occurring in Γ. We construct an argumentation graph $G=〈\mathcal{A},$ $\mathcal{R},\pi 〉$ , and $\phi :ℝ\to {\mathcal{C}}_n$ such that the maximum number of jointly satisfiable clauses is even if and only if T (Sat) → Even _n  ≥ 1 is satisfied in the preferential interpretation $I_G=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ , with Σ the set of all the φ-coherent labellings of G with truth degree set $\mathcal{S}={\mathcal{C}}_n$ .

We let the set of arguments $\mathcal{A}$ contain an argument A _x and its complement A_¬x for each x ∈ vars (Γ), an argument C _i for each clause in Γ, as well as the argument ⊤, Sat, and arguments Even _i , Even_i,1 and Even_i,2, for i = 0, …, n.

In the following σ denotes any φ-coherent labelling for G. Our construction comprises $\phi \left(w\right)=min(1,max(0,w+\frac{1}{n}\left)\right)$ , and the following gadgets (also shown in Fig. 2) to build the argumentation graph:

Fig. 2

Gadgets used in the reduction from max sat even.

• node $\top \in \mathcal{A}$ and arc $\underrightarrow{+1}$ ⊤ to enforce σ (⊤) =1;

• for each x ∈ vars (Γ), nodes A _x , A_¬x and arcs A _x $\underrightarrow{+1}$ A _x , A_¬x $\underrightarrow{+1}$ A_¬x, A _x $\underrightarrow{-2}$ A_¬x, A _x $\underrightarrow{-2}$ A_¬x, to enforce crisp and different values for A _x and A_¬x; in formulas, σ (A _x ) =1 - σ (A_¬x);

• for each i = 1 . . n, node C _i and arc ⊤ $\underrightarrow{-1}$ C _i , as well as arc A_ℓ $\underrightarrow{+2}$ C _i for each literal ℓ in clause γ _i , to enforce σ (C _i ) =1 if there is ℓ ∈ γ _i such that σ (ℓ) =1, and 0 otherwise;

• node Sat and arc $\top \underrightarrow{-\frac{1}{n}}\mathit{Sat}$ , as well as arc $C_i\underrightarrow{+\frac{1}{n}}\mathit{Sat}$ for all i = 1 . . n, to enforce $\sigma \left(\mathit{Sat}\right)=\frac{k}{n}$ , where k is the number of i = 1 . . n such that σ (C _i ) =1;

• node Even₀ and arc ⊤ $\underrightarrow{+1}$ Even₀ to enforce σ (Even₀) =1, representing the fact that there is an even number of true clauses with index i ≤ 0

• nodes Even _i , Even_i,1, Even_i,2 and the following groups of arcs:

• ⊤ $\underrightarrow{-1}$ Even_i,2, Even_i,2 $\underrightarrow{+1}$ Even_i,2, Even_i-1 $\underrightarrow{+1}$ Even_i,2, C _i $\underrightarrow{-2}$ Even_i,2, to enforce σ (Even_i,2) =1 if σ (Even_i-1) =1 and σ (C _i ) =0, and 0 otherwise;

• ⊤ $\underrightarrow{+1}$ Even _i , Even_i,1 $\underrightarrow{+2}$ Even _i , Even_i,2 $\underrightarrow{+2}$ Even _i , to enforce σ (Even _i ) =1 if σ (Even_i,1) =1 or σ (Even_i,2) =1, and 0 otherwise.

Essentially, the above construction enforces a crisp valuation for vars (Γ), so that each φ-coherent labelling σ is one-to-one with a boolean assignment I _σ  = {x ↦ σ (A _x ) ∣ x ∈ vars (Γ)} for Γ. Moreover, σ (C _i ) = I _σ  (γ _i ) for all i = 1 . . n, and $\sigma \left(\mathit{Sat}\right)=\frac{k}{n}$ , where k = | {i : i = 1 . . n, I _σ  (γ _i ) =1} | is the number of clauses in Γ satisfied in the interpretation I _σ . Finally, σ (Even₀) =1 and I _σ  (Even _i ) = I _σ  (Even_i-1) XOR I _σ  (C _i ) (for all i = 1 . . n).

All in all, $\sigma \left(\mathit{Sat}\right)=\frac{k}{n}$ if and only if k is the number of clauses of Γ satisfied by I _σ , and σ (Even _n ) =1 if and only if such k is even.

To complete the proof of Proposition 5, we show that the graded implication T (Sat) → Even _n  ≥ 1 holds in I _G if and only if the maximum number k of jointly satisfiable clauses in Γ is even. In fact, if $\sigma \left(\text{T}\right(\mathit{Sat}\left)\right)=\frac{k}{n}$ , then k is the maximum number of jointly satisfiable clauses from Γ. For all the labellings σ such that | {i : i = 1 . . n,  I _σ  (γ _i ) =1} | = k, for Even _n there are only two possibilities: either for all such σ, σ (Even _n ) =1 as k is even, or, for all of them σ (Even _n ) =0. But in the second case, the truth degree of the implication T (Sat) → Even _n would be 0. Therefore, T (Sat) → Even _n  ≥ 1 holds in I _G if and only if the maximum number k of jointly satisfiable clauses in Γ is even.

8 Mapping weighted KBs to weighted argumentation graphs under the φ-coherent semantics

An interesting question is whether a weighted knowledge base can be encoded into a weighted argumentation graph, under the φ-coherent semantics. In this section we show that, under some conditions, the answer is positive. Specifically, we describe an encoding of a KB for the case when ABox is empty, the function φ is the one used in Section 7 to prove the lower bound result, and the choice of combination functions is as in Łukasiewicz logic. We also assume that the DBox in the weighted knowledge base K does not contain occurrences of concept ⊥ on the left hand side of weighted inclusions.

First, let us consider the simpler case when the TBox is empty, and no complex concept is contained in the DBox $\mathcal{D}$ ; a direct mapping of K into an argumentation graph G can be given in this case.

Let $K=(\mathcal{T},\mathcal{D},\mathcal{A})$ , where $\mathcal{T}=\mathcal{A}=\varnothing$ , and for all typicality inclusions $\left(\text{T}\right(A)⊑B,w_i)\in \mathcal{D}$ , A and B are atomic concepts. The knowledge base K can be mapped directly into a weighted argumentation graph $G^K=〈\mathcal{A},\mathcal{R},\pi 〉$ , in the obvious way, by letting the set $\mathcal{A}$ of arguments to be the set of all concept names occurring in K, plus arguments ⊤ and ⊥, and by letting $\mathcal{R}=\left\{\right({\mathcal{A}}_j,{\mathcal{A}}_i)\mid (\mathcal{T}\left({\mathcal{A}}_i\right)⊑{\mathcal{A}}_j,{\mathcal{w}}_{\mathcal{j},\mathcal{i}})\in \mathcal{D}\}\cup {\mathcal{R}}_{\top }\cup {\mathcal{R}}_{\perp }$ , and π (A _j , A _i ) = w_j,i, for A _i , A _j such that $\left(\text{T}\right(A_i)⊑A_j,w_{j,i})\in \mathcal{D}$ , while ${\mathcal{R}}_{\top }$ and ${\mathcal{R}}_{\perp }$ are used to constrain the values of arguments ⊤ and ⊥ to be, resp., 0 and 1: ${\mathcal{R}}_{\top }=\left\{\right(\top ,\top \left)\right\}$ , with π (⊤ , ⊤) = +1 (as in Fig. 2 (a)), while ${\mathcal{R}}_{\perp }=\left\{\right(\top ,\perp \left)\right\}$ , with π (⊤ , ⊥) = -1.

The following correspondence can be easily proven.

Proposition 6. For a weighted knowledge base K (satisfying the conditions stated above), let I _{G ^K} be the preferential interpretation of the argumentation graph G ^K under the φ-coherent semantics. For each canonical φ-coherent model I of K, if the typicality inclusions T (C) ⊑ D θ l is satisfied by I, the corresponding graded conditional implications T (α _C ) → α _D  θ l is satisfied in I _{G ^K} ; and vice-versa.

Note that a formula α _C is obtained from a concept C by replacing the operators ⊓ and ⊔ occurring in C with connectives ∧ and ∨. The correspondence above does not depend on the choice of the function φ.

We aim at generalizing the result above to the case when the DBox may contain occurrences of complex concepts and TBox is a set of strict graded inclusions C ⊑ Dθl (we still assume the ABox is empty). To this purpose we show that: (a) we can replace the complex concepts in the DBox with new atomic concepts by adding some new TBox axioms; (b) we can encode the resulting TBox into the DBox. For the encoding in step (b), we choose a specific function φ, namely, we let $\phi \left(w\right)=\mathit{min}(1,\mathit{max}(0,w+\frac{1}{n})$ .

For step (a), let $K=〈\mathcal{T},\mathcal{D},\mathcal{A}〉$ be a weighted knowledge base which allows in the DBox $\mathcal{D}$ occurrences of weighted inclusions (T (C _i ) ⊑ C _j , w_j,i), with C _i and C _j complex boolean concepts. We can replace each complex concept C _i occurring in $\mathcal{D}$ with a new named concept A _i , thus replacing in $\mathcal{D}$ the weighted inclusion above with (T (A _i ) ⊑ A _j , w_j,i), and adding to the TBox $\mathcal{T}$ the two inclusions A _i  ⊑ C _i  ≥ 1 and C _i  ⊑ A _i  ≥ 1.

Let us call $K^{\prime }=〈{\mathcal{T}}^{\prime },{\mathcal{D}}^{\prime },\mathcal{A}〉$ the resulting knowledge base. It is easy to prove that, when restricting to the language of K, the two knowledge bases K and K′ entail the same graded concept inclusions in the φ-coherent semantics (and similarly for the coherent and the faithful semantics), that is: for C and D in the language of K, T (C) ⊑ Dθ l is entailed by K iff T (C) ⊑ Dθ l is entailed by K′; and similarly for the strict inclusions C ⊑ D.

For step (b), we start from the knowledge base $K^{\prime }=〈{\mathcal{T}}^{\prime },{\mathcal{D}}^{\prime },{\mathcal{A}}^{\prime }〉$ obtained by step (a), and encode the strict axioms occurring in the TBox into the defeasible part of the knowledge base, by adding to ${\mathcal{D}}^{\prime }$ some new weighted inclusions (possibly, with the addition of new concept names).

As we have assumed that TBox $\mathcal{T}$ does not contain occurrences of typicality operator, and that it only contains strict inclusions of the form C ⊑ D θ l, the same holds for ${\mathcal{T}}^{\prime }$ . Also, ABox ${\mathcal{A}}^{\prime }$ is empty, as ${\mathcal{A}}^{\prime }=\mathcal{A}=\varnothing$ .

Let us consider an ${\mathcal{LC}}_n\mathcal{T}$ knowledge base, under the choice of combination functions as in Łukasiewicz Logic, and assume that function $\phi :ℝ\to {\mathcal{C}}_n$ is defined as $\phi \left(w\right)=\mathit{min}(1,\mathit{max}(0,w+\frac{1}{n}\left)\right)$ , as in Section 7.

We encode each inclusion axiom C ⊑ D θ l occurring in ${\mathcal{T}}^{\prime }$ by adding to ${\mathcal{D}}^{\prime }$ a set of weighted inclusions. ${\mathcal{D}}^{″}$ will be the resulting DBox. The resulting weighted knowledge base will be $K^{″}=〈{\mathcal{T}}^{″},{\mathcal{D}}^{″},{\mathcal{A}}^{″}〉$ , with ${\mathcal{T}}^{″}={\mathcal{A}}^{″}=\varnothing$ .

First we show that we can represent any boolean combination of concepts, based on Łukasiewicz t-norm, s-norm, implication and negation function, where a ⊗ b = max {a + b − 1, 0}, a ⊕ b = min {a + b, 1}, a ⊳ b = min {1 − a + b, 1} and ⊖a = 1 − a. For each boolean combination of concepts C occurring in ${\mathcal{T}}^{\prime }$ , a new concept name A _C is introduced in the language. For each concept name B ∈ N _C occurring in ${\mathcal{T}}^{\prime }$ , we do not need to introduce a new concept name A _B , but in the following, we will let A _B stand for B itself. To emphasize the fuzzy interpretation of concepts, we will write A_B1⊗B2, A_B1⊕B2, A_⊖B2, rather than A_B1⊓B2, A_B1⊔B2, A_¬B2

For each complex concept occurring in the TBox, we add a set of defeasible inclusions in the DBox, as follows:

We represent intersection B₁ ⊓ B₂ by introducing a new concept name A_B1⊗B2, and the following weighted inclusions in ${\mathcal{D}}^{″}$ :

$\text{T}\left(A_{B_1\otimes B_2}\right)⊑\top ,-1-\frac{1}{n}$

T (A_B1⊗B2) ⊑ A _{B 1} , + 1

T (A_B1⊗B2) ⊑ A _{B 2} , + 1

We represent the union B₁ ⊔ B₂ by introducing a new concept name A_B1⊕B2, and the following weighted inclusions in ${\mathcal{D}}^{″}$ :

$\text{T}\left(A_{B_1\oplus B_2}\right)⊑\top ,-\frac{1}{n}$

T (A_B1⊕B2) ⊑ A _{B 1} , + 1

T (A_B1⊕B2) ⊑ A _{B 2} , + 1

We represent the complement ¬B by introducing a new concept name A_⊖B, and the following weighted inclusions in ${\mathcal{D}}^{″}$ :

$\text{T}\left(A_{\ominus B}\right)⊑\top ,+1-\frac{1}{n}$

T (A_⊖B) ⊑ A _B , - 1

To enforce the inclusion B₁ ⊑ B₂ we introduce a new concept name A_B1⊳B2, and the following weighted inclusions in ${\mathcal{D}}^{″}$ :

$\text{T}\left(A_{B_1⊳B_2}\right)⊑\top ,+1-\frac{1}{n}$

T (A_B1⊳B2) ⊑ A _{B 1} , - 1

T (A_B1⊳B2) ⊑ A _{B 2} , + 1

The weighted axioms above enforce a φ-coherent interpretation to satisfy the following conditions in ${\mathcal{D}}^{″}$ :

$A_{B_1\otimes B_2}^I\left(x\right)=B_1^I\left(x\right)\otimes B_2^I\left(x\right)$

$A_{B_1\oplus B_2}^I\left(x\right)=B_1^I\left(x\right)\oplus B_2^I\left(x\right)$

$A_{\ominus B}^I\left(x\right)=\ominus B^I\left(x\right)$

$A_{B_1⊳B_2}^I\left(x\right)=B_1^I\left(x\right)⊳B_2^I\left(x\right)$

Any boolean concept C can then be represented by a concept name A _C , and the typicality inclusions above allow to define the interpretation of C, based on the interpretation of concept names occurring in C according on the meaning of combination functions.

Let us consider an inclusion axiom C ⊑ D ≥ l (the other cases for θ are similar). It requires that, for all domain individuals x, C ^I  (x) ⊳ D ^I  (x) ≥ l. As in an interpretation I it holds that $A_{C⊳D}^I\left(x\right)=C^I\left(x\right)⊳D^I\left(x\right)$ , we have to require that $A_{C⊳D}^I\left(x\right)\ge l$ .

First we introduce a concept name A _l whose interpretation is $A_l^I\left(x\right)=l$ , for all domain individuals x. This can be done by adding in ${\mathcal{D}}^{″}$ :

$\text{T}\left(A_l\right)⊑\top ,+l-\frac{1}{n}$

The value of the implication $A_l^I\left(x\right)⊳A_{C⊳D}^I\left(x\right)$ will be 1 when $A_{C⊳D}^I\left(x\right)\ge l$ .

Hence, one can require that C ^I  (x) ⊳ D ^I  (x) ≥ l for all elements x, by requiring that, for all domain elements x, $A_l^I\left(x\right)⊳A_{C⊳D}^I\left(x\right)=A_{A_l⊳(C⊳D)}^I\left(x\right)=1$ . To avoid that $A_{A_l⊳(C⊳D)}^I\left(x\right)$ takes a value different from 1, we add a new concept name A_C^⊑D≥l and the following inclusions in ${\mathcal{D}}^{″}$ :

T (A_C^⊑D≥l) ⊑ A_C^⊑D≥l, - 1

T (A_C^⊑D≥l) ⊑ A_{(A l ⊳(C⊳D))}, + 2

For any given x, if $A_{(A_l⊳(C⊳D\left)\right)}^I\left(x\right)=1$ , then $A_{C^{⊑}D\ge l}^I\left(x\right)$ must be 1 and C ^I  (x) ⊳ D ^I  (x) ≥ l holds. Otherwise, $A_{(A_l⊳(C⊳D\left)\right)}^I\left(x\right)<1$ , and any possible value assignment to $A_{C^{⊑}D\ge l}^I\left(x\right)$ falsifies the φ-coherence condition for $A_{C^{⊑}D\ge l}^I\left(x\right)$ . That is, x cannot belong to any φ-coherent interpretation I satisfying the DBox.

Observe that in step (b) the encoding of the typicality inclusions C ⊑ D ≥ l only introduces in the DBox weighed inclusions over named concepts.

After steps (a) and (b), The resulting weighted knowledge base $K^{″}=〈{\mathcal{T}}^{″},{\mathcal{D}}^{″},{\mathcal{A}}^{″}〉$ , is such that ${\mathcal{T}}^{″}={\mathcal{A}}^{″}=\varnothing$ , and ${\mathcal{D}}^{″}$ only contains occurrences of concept names. Therefore, it can be encoded in a weighted argumentation graph, as shown by Proposition 8.

In the encoding we have taken a specific choice of the function φ and combination functions. Whether the encoding can be extended to other choices of function φ and combination functions is a matter of further investigation.

A weighted argumentation graph G could be enriched with a set of strict graded implications of the form α → β θl (with α and β boolean combinations of arguments), so to filter out some of the labellings (i.e., those that do not satisfy the graded implications) in a similar way as done in weighted knowledge bases with TBox axioms. However, based on the mapping in this section, strict graded implications could be encoded in the weighted graph itself.

9 Implementation and empirical assessment

As a consequence of the mapping of a weighted argumentation graph into a weighted KB in Section 6, on the one hand the model checking approach developed in [12] for weighted knowledge bases with finitely-many values can be extended to the argumentation semantics with truth degree domain ${\mathcal{C}}_n$ . On the other hand, the encoding developed for weighted knowledge bases can be specialized for the verification of graded inclusions over weighted graphs, and allows for an implementation of a reasoner that, given a weighted graph G and graded implication T (C _q ) → D _q  θl, verifies whether the implication is satisfied under the φ-coherent semantics.

Therefore, we extended the valphi system (https://github.com/alviano/valphi) to address such a verification. In Section 9.1 we adapt the ASP encodings introduced in [2], and in Section 9.2 we provide an empirical assessment.

9.1 Implementation

The valphi system is powered by the clingo python api [39] coupled with carefully designed ASP encodings [2]. A revised version of the base encoding used by valphi is reported in Fig. 3, together with the weight constraint enforcing φ-coherence. It is actually a simplified version of the encoding, driven by the fact that the mapping from Section 6 produces knowledge bases containing only weighted typicality inclusions.

Fig. 3

Base encoding expanded with weight constraints enforcing φ-coherence, with θ ∈ {≥ , ≤ , > , <}, θ_> ∈ {> , ≥}, and θ_< ∈ {< , ≤}.

Given an input graph $G=〈\mathcal{A},\mathcal{R},\pi 〉$ , the domain of argument valuation $\mathcal{S}={\mathcal{C}}_n$ , and a monotonically non-decreasing function $\phi :ℝ\to \mathcal{S}$ , we want to verify the satisfiability of a graded implication T (α _q ) → β _q  θl (called query in the following) in the preferential interpretation $I=(\mathcal{S},\Sigma ,\{{<}_{\alpha }\left\}\right)$ of the weighted graph G with respect to the φ-coherent semantics. The input of the encoding comprises the following facts (with weights represented as integers):

val _ phi(v,LB,UB) whenever $\phi \left(w\right)=\frac{v}{n}$ if and only if LB < w ≤ UB holds;

argument(A) for each argument A in $\mathcal{A}$ , where A is represented as a constant term;

link(A,B,w) for each support/attack arc A $\underrightarrow{w}$ B in $\mathcal{R}$ ;

query(α _q ,β _q ,θ,l) for the graded implication, where α _q and β _q are represented by (possibly complex) terms combining the uninterpreted functions and, or, neg and impl.

The @-term @is_named_argument(A) returns 1 if A is an argument in $\mathcal{A}$ , and 0 otherwise (when A is a boolean combination of arguments). similarly, @min(v,v′), @max(v,v′), @neg(v) and @impl(v,v′,n) return the truth degree functions ⊗, ⊕, ⊖ and ⊳ in Gödel logic with standard involutive negation. Intuitively, line 1 introduces the truth degrees from ${\mathcal{C}}_n$ and fixes the interpretation of ⊥ and ⊤. Line 2 guesses a truth degree for arguments in $\mathcal{A}$ . Lines 3–6 evaluate boolean combination of arguments. Line 8 expresses a preference for labellings assigning a large truth degree to α _q . Lines 10–12 define typical α _q -labellings and express a weaker preference for the existence of a witness: if the query uses θ_> ∈ {> , ≥}, a witness is a labelling σ ∈ Σ such that $\sigma \left(\text{T}\right({\alpha }_q\left)\right)⊳\sigma \left({\beta }_q\right){\theta }_{>}\frac{l}{n}$ holds in I (i.e., σ makes the query false), and the query is true if such a witness does not exist; if the query uses θ_< ∈ {< , ≤}, a witness is a labelling σ ∈ Σ such that $\sigma \left(\text{T}\right({\alpha }_q\left)\right)⊳\sigma \left({\beta }_q\right){\theta }_{<}\frac{l}{n}$ holds in I (i.e., α makes the query true), and the query is false if such a witness does not exist. Lines 13–14 report in the output whether a witness was found (and the truth degrees it assigns to arguments). The base encoding is enriched with the weight constraints in lines 15–19 to enforce φ-coherence. Alternatively, an ad-hoc propagator can be used. In any case, the base encoding can be further optimized to obtain an order encoding; details on the order encoding are given in [2].

9.2 Empirical assessment

Based on the mapping in section 6, the ASP-based system described in section 9.1 has been tested for synthetic argumentation graphs. The graphs were generated with a given number of nodes; arcs with random weights were generated between random nodes, up to a given number of “forward” arcs (from a node i to a node j > i) and “backward” arcs (from i to j < i). The proportion of backward arcs was chosen to be large enough in order to obtain graphs with loops, which constrain the number of φ-coherent labellings; but not too large, which would overconstrain the labellings, producing graphs with no φ-coherent labellings. The resulting number of labellings is related to the number of resulting “input” nodes, i.e., nodes with no incoming arcs, and the size of the domain ${\mathcal{C}}_n$ . In a relatively sparse graph with random arcs, there is a non-zero variable number of such nodes, and, as shown below, in a set of graphs with the same number of nodes and arcs, the resulting number of labellings is quite variable.

Figures 4–5 provide results on the largest graphs in the benchmark, with 60 nodes and about 300 support/attack arcs (270 forward arcs plus 27 backward ones), evaluated in a domain of argument valuations of size 5 and 10, with running times on an Intel Xeon 5520, 2.26 GHz.

Fig. 4

Results for domain of argument valuation ${\mathcal{C}}_4$ (5 truth degrees), graphs with 60 nodes A₁, …, A₆₀ and 300 support/attack arcs. Number of labellings, execution time for enumerating them and for queries of the form T (A₆₀) → A₁ ∨ … ∨ A₁₀ ≥ 1/2.

Fig. 5

Results for the same graphs and queries in Fig. 4 using as domain of argument valuation ${\mathcal{C}}_9$ (10 truth degrees). Graph d not reported in the plot due to scaling issues (12 002 labellings enumerated in 1 255 seconds, query answered in 2.28 seconds).

There are large variations in the number of labellings (3–700 and 4–12002 resp.) and the time for enumerating them (2.3–69.9 s, 2–1255 s, i.e., around 7–10 solutions per second). In spite of that, graded conditionals can be verified in much shorter times, with very small variations (in the range 2.10–2.25 s in one case, 2.02–2.28 s in the other one).

This also holds for different sets of graphs (with 20 nodes and 30+3 arcs; 40 nodes and 120+12 arcs) where, for some of them, there are too many labellings for enumerating them within a timeout of 30 minutes; running times for evaluating graded conditionals are however always in the range 0.7–1.5 seconds.

10 Conclusions

Defeasible reasoning over weighted KBs with typicality is a computationally intensive task, that has been previously addressed for logic ${\mathcal{LC}}_n\text{T}$ (a defeasible description logic which does not allow for roles, but only for boolean concepts) in the finitely many-valued case, by adopting solving techniques suitable for problems in the complexity class ${\Pi }_2^p$ [46]. In [2] ASP has been proposed as a basis for defining an algorithm asking all required queries to the NP oracle in parallel, and then inspecting the obtained answers to decide if the entailment holds. In particular, an PNP[log]-completeness result has been proven, and the scalability of different ASP encodings has been evaluated.

The work in this paper aims at extending the proposed approach for reasoning about some gradual argumentation semantics, namely, the coherent, faithful and φ-coherent semantics, first proposed in the fuzzy case [42] and in the finite many-valued case [1], stemming from the strong similarity between weighted knowledge bases and weighted argumentation graphs.

In this paper we establish relationships and mappings between the φ-coherent semantics of weighted KBs with typicality and the respective semantics of a weighted argumentation graph, by further proposing an approach for defeasible reasoning over a weighted argumentation graph, building on the gradual semantics.

We show that a weighted argumentation graph can be mapped to a weighted knowledge base with empty ABox and TBox. The many-valued labellings of the argumentation graph give rise to a preferential interpretation over which graded typicality implication can be verified. The mapping suggests that simplified versions of the ASP encodings proposed for weighted KBs can be adopted for verifying the satisfiability of such graded implications over the argumentation graph, and also provides a P||NP = PNP[log] upper bound on the complexity of the problem. A lower complexity bound is also proven in Section 7. This suggests that a mapping from a weighted KB (including strict graded inclusion axioms) to a weighted argumentation graph might be possible, under the φ-coherent semantics. The paper provides a positive result under some specific conditions on the choice of function φ, on the combination functions, and by assuming an empty ABox. Whether these result can be generalized to other cases is an interesting subject for future work. Another interesting question is whether this approach for conditional reasoning over argumentation graphs can be extended to other gradual semantics. Preliminary results can be found in [1].

Our approach for defeasible reasoning over weighted argumentation graphs has been suggested by the strong relationships between weighted argumentation graphs and neural networks (namely, multilayer networks for acyclic argumentation graphs, and recurrent networks for argumentation graphs with cycles). In this regard, our approach is inline with the work by Garcez, et al. [33] and by Potyka [61].

The work by Garcez, et al. [33] combines value-based argumentation frameworks [13] and neural-symbolic learning systems by providing a translation from argumentation networks to neural networks with 3 layers (input, output layer and one hidden layer). This enables the accrual of arguments through learning as well as the parallel computation of arguments.

The work by Potyka [61] considers a quantitative bipolar argumentation frameworks (QBAFs) similar to [10] and exploits an influence function based on the logistic function to define an MLP-based semantics σ _MLP for a QBAF. As we have seen in Section 4, our semantics based on φ-coherent models fails to satisfy some of the properties studied in [5] and in [61].

Let us further consider Ranking-based semantics for argumentation frameworks [8, 19] and Fuzzy Argumentation Frameworks by Jenssen et al. [54].

A ranking-based semantics for argumentation frameworks [8, 19], transforms any argumentation graph into a ranking on its set of arguments. In such frameworks a ranking relation on arguments is a total and transitive binary relation ⪯, where a ⪯ b means that argument b is more acceptable then argument a.

Note that the degree of argument in a many-valued labelling σ induces a ranking relation on arguments, which is used in the definition of the coherent and faithful semantics (see Definition 5). In our approach, we also consider preference relations in Section 5, to define the preferential semantics of the conditional logic. However, these are preferences between many-valued labellings (that is, many-valued valuations).

Unlike the Fuzzy Argumentation Frameworks by Jenssen et al. [54], where an attack relation is a fuzzy binary relation over the set of arguments, here we have considered real-valued (positive or negative) weights associated to pairs of arguments. This makes the computation of the strength of an argument in our semantics more similar (although not equivalent) to [61].

In general, unlike all the frameworks mentioned above, our approach aims at verifying conditional properties of a weighted argumentation graph, and it is based on a preferential conditional semantics, which builds on the gradual argumentation semantics and exploits a notion of typicality in the formalization of (graded) conditional properties. In this regard, it also relates to the fuzzy extension of rational closure by Casini and Straccia [28], but for being based on a many-valued multi-preferential semantics and on a different closure construction.

Our work also builds on the fuzzy and many-valued extensions of description logics, which have been widely studied in the literature [16, 64]. The finitely-valued case is also well studied for DLs [15, 38], and in this paper we have considered the boolean fragment ${\mathcal{LC}}_n$ of a finitely-valued $\mathcal{ALC}$ extended with typicality.

The semantics has strong relations with KLM preferential semantics [56] and with other preferential semantics exploiting weights, such as Kern-Isberner’s c-representations [55], where the weights of falsified conditionals represent penalty points, and the algebraic semi-qualitative approach by Weydert [66], exploiting ranking measures over a ranking algebra. The specificity of our many-valued approach is that we exploit a concept-wise multi-preferential semantics, in which preferences ≺ _C are associated with the different concepts C. This also makes our formalism different from the one considered by Casini and Straccia [29], in their rational closure construction for fuzzy logic.

Concerning the relationships between argumentation semantics and conditional reasoning, Weydert [67] has proposed one of the first approaches for combining abstract argumentation with a conditional semantics. He has studied “how to interpret abstract argumentation frameworks by instantiating the arguments and characterizing the attacks with suitable sets of conditionals describing constraints over ranking models”. In doing this, he has exploited the JZ-evaluation semantics, which is based on system JZ [66]. Although in this paper we have focused on the coherent, faithful and φ-coherent semantics for weighted argumentation, our approach for conditional reasoning over an argumentation graph does not commit to a specific gradual semantics. As shown in [1], it aims at providing a preferential and conditional interpretation for a large class of gradual argumentation semantics, provided that the domain of argument interpretation is equipped with a preorder relation.

For Abstract Dialectical Frameworks (ADFs) [24], the correspondence between ADFs and Nonmonotonic Conditional Logics has been studied by Heynink et al. [52] with respect to the two-valued models, the stable, the preferred semantics and the grounded semantics of ADFs.

In [62] Ordinal Conditional Functions (OCFs) have been interpreted and formalized for Abstract Argumentation, by developing a framework that allows to rank sets of arguments with respect to their plausibility. An attack from argument a to argument b is interpreted as the conditional relationship, “if a is acceptable then b should not be acceptable". Based on this interpretation, an OCF inspired by System Z ranking function is defined. In this paper we focus on the gradual case, based on a many-valued logic.

While in this paper we have assessed our encoding approach for conditional reasoning over weighted argumentation graphs, in [3] acyclic weighted knowledge bases have been considered in the verification of conditional properties of some trained multilayer feedforward networks for the recognition of basic emotions. The co-existence of strict inclusions and defeasible weighted inclusions in weighted KBs allows for combining empirical knowledge with elicited knowledge for reasoning and for post-hoc verification. The possibility of encoding strict TBox axioms by a set of weighted inclusions, may suggest further alternative modes of combination. The interplay of different functions φ _i which may be used for different units, is also a direction that can be considered for weighted argumentation graphs, as done for weighted knowledge bases [3], by associating different functions φ _i to different arguments A _i in the graph.