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 $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.

Keywords

Preferential semantics description logic many-valued logic answer set programming gradual argumentation

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 $LC$ fragment of $ALC$ , in which only boolean concepts are allowed [2]. More precisely, when the truth degree set is taken to be $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 $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: ${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] ${LC}_{n} 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 $ALC$ , without roles (more expressive DLs with typicality, including all $ALC$ constructs, have been considered in [3]).

Let us consider the finitely-valued set of truth degrees $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 ${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 ${LC}_{n}$ knowledge baseK is defined as a pair $(T, A)$ , where $T$ (the TBox) is a set of concept inclusions of the form C ⊑ D θ l, and $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} : Δ^{I} \to 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 $C_{n}$ . The interpretation of composed concepts is defined according to the following inductive definition: $\begin{matrix} \begin{matrix} ⊤^{I} (x) = 1 & (C ⊓ D)^{I} (x) = C^{I} (x) \otimes D^{I} (x) \\ ⊥^{I} (x) = 0 & (C ⊔ D)^{I} (x) = C^{I} (x) \oplus D^{I} (x) \\ (\neg C)^{I} (x) = ⊖ C^{I} (x) \end{matrix} \end{matrix}$

The interpretation function ·^I is also extended to axioms as follows: $\begin{matrix} (C ⊑ D)^{I} = \inf_{x \in Δ^{I}} C^{I} (x) ⊳ D^{I} (x) \\ (C (a))^{I} = C^{I} (a^{I}) \end{matrix}$ 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 = (T, A)$ be an ${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 ⊨ T$ and $I ⊨ 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.

${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 ≺ _Cy means that x is preferred to y) is obtained as follows: for all x, y ∈ Δ^I, x ≺ _Cy 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 ≺ _Cx, 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 ${LC}_{n}$ with the typicality operator is called ${LC}_{n} 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 ${LC}_{n} T$ knowledge base is a tuple $〈 T, D, A 〉$ , where the (strict) TBox $T$ is a set of concept inclusions, the defeasible TBox $D$ is a set of weighted typicality inclusions, and $A$ is a set of assertions.

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

The defeasible TBox $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 ${weight}_{C} (x) = \sum_{(T (C) ⊑ D, w) \in T} w \cdot D^{I} (x) .$

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 $φ : ℝ \to C_{n}$ .

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

$C^{I} (x) = φ ({weight}_{C} (x))$ (1) holds for all x ∈ Δ^I and all distinguished concept C in $D$ . I is a φ-coherent model of K if it is a φ-coherent interpretation satisfying $T$ and $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 ≺ _Cyiff weight_C (x) > weight_C (y),

or with the (weaker) faithfulness condition: x ≺ _Cy ⇒ 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 = 〈 T, D, A 〉$ be a weighted ${LC}_{n} T$ knowledge base, and $φ : ℝ \to 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 $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 ${LC}_{n} T$ knowledge base $K = 〈 T, D, 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 $D$ of a weighted ${LC}_{n} T$ knowledge base. In such a case, the defeasible TBox $D$ can be represented as a weighted graph where the named concepts occurring in $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 $D$ as arguments, then $D$ can be regarded as a weighted argumentation graph. The many-valued semantics developed for ${LC}_{n} 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 $S$ of argument valuation. Here, we will consider as well the case where $S$ is the finite set $C_{n}$ , for n > 1.

Let a weighted argumentation graph be a triple $G = 〈 A, R, π 〉$ , where $A$ is a set of arguments, $R \subseteq A \times A$ and $π : 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 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 $S$ be the interval [0, 1] or the set $C_{n}$ . Given a weighted argumentation graph $G = 〈 A, R, π 〉$ , a many-valued labelling of G is a function $σ : A \to 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 ∣ (B, A) \in R}$ . When R^- (A) = ∅, argument A has no supports nor attacks. For $G = 〈 A, R, π 〉$ and a many-valued labelling σ, we introduce a weight $W_{σ}^{G}$ on $A$ as a partial function $W_{σ}^{G} : A \to ℝ$ , assigning a positive or negative support (relative to labelling σ) to all arguments $A_{i} \in A$ such that R^- (A_i)≠ ∅, as follows: $W_{σ}^{G} (A_{i}) = \sum_{(A_{j}, A_{i}) \in R} π (A_{j}, A_{i}) σ (A_{j})$ (2) $W_{σ}^{G} (A_{i})$ 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 $C_{n}$ . The next definition and proposition hold for both $S = [0, 1]$ and $S = C_{n}$ , for n > 1.

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

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

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

given a non-decreasing function $φ : ℝ \to S$ , σ is a φ-coherent many-valued labelling of G if, for all arguments $A \in A$ , s.t. R^- (A)≠ ∅, $σ (A) = φ (W_{σ}^{G} (A))$ (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 $S$ be either [0, 1] or $C_{n}$ .

Proposition 1. Given $G = 〈 A, R, π 〉$ and $φ : ℝ \to$ $S$ , (1) a coherent many-valued labelling $σ : A \to 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 $σ (A) = φ (W_{σ}^{G} (A))$ , 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 A$ such that R^- (A)≠ ∅, $σ (A) = φ (W_{σ}^{G} (A))$ . We have to prove that for all arguments $A, B \in A$ s.t. R^- (A)≠ ∅ and R^- (B)≠ ∅, $σ (A) < σ (B) \Rightarrow W_{σ}^{G} (A) < W_{σ}^{G} (B) .$ If σ (A) < σ (B) holds, from the hypothesis that R^- (A)≠ ∅ and R^- (B)≠ ∅, by condition (3), we have $φ (W_{σ}^{G} (A)) < φ (W_{σ}^{G} (B))$ . By absurd, let us assume that the conclusion $W_{σ}^{G} (A) < W_{σ}^{G} (B)$ does not hold. Then $W_{σ}^{G} (A) \geq W_{σ}^{G} (B)$ . As φ is non-decreasing, $φ (W_{σ}^{G} (A)) \geq φ (W_{σ}^{G} (B))$ 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 A$ sucht that R^- (A)≠ ∅, $σ (A) = φ (W_{σ}^{G} (A))$ . We have to prove that for all arguments $A, B \in A$ s.t. R^- (A)≠ ∅ and R^- (B)≠ ∅, $σ (A) < σ (B) \Leftrightarrow W_{σ}^{G} (A) < W_{σ}^{G} (B) .$

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

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

Restricting the domain of argument valuation to the finite number of values in $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 $S = 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 $C_{n}$ ).

Example 2. For $S = 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., $σ (A_{4}) = φ (W_{σ}^{G} (A_{4}))$ . In fact, $W_{σ}^{G}$ (A₄) =4/5 -1.5 * 3/5 = -0.1; $S (W_{σ}^{G} (A_{4})) = S (- 0.1) = 0.475$ , and then $φ (W_{σ}^{G} (A_{4})) = 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 $σ_{0} : A \to [0, 1]$ in the definition of a weighted graph, where σ₀ assigns to each argument $A \in A$ its basic strength (also called base score). Hence, a graph G becomes a quadruple $G = 〈 A, σ_{0}, R, π 〉$ .

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 = 〈 A, σ_{0}, R, π 〉$ is a triple M = 〈 h, g, f〉, where 1 :

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

$g : ⋃_{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 = 〈 A, σ_{0}, R, π 〉$ a weighting ${Deg}_{G}^{S}$ on $A$ , i.e., ${Deg}_{G}^{S} : A \to [0, 1]$ , where ${Deg}_{G}^{S} (A)$ 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 = 〈 A, σ_{0}, R, π 〉$ , $\forall A \in A$ ,

${Deg}_{G}^{S} (A) = f (σ_{0} (A), g (h (π (B_{1}, A), {Deg}_{G}^{S} (B_{1}))$ ,

…,

$h (π (B_{n}, A), {Deg}_{G}^{S} (B_{n})))$

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_{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 = 〈 A, R, π 〉$ be a weighted argumentation graph. If, for some $σ_{0} : A \to [0, 1]$ , S is a gradual semantics based on the evaluation method M^φ = 〈 h_prod, g_sum, f_φ〉 for graph $G^{'} = 〈 A, σ_{0}, R, π 〉$ , then ${Deg}_{G^{'}}^{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^{'} = 〈 A, σ_{0}, R, π 〉$ , such that, ${Deg}_{G^{'}}^{S} \equiv σ$ .

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 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 = (A, E, β, w)$ , where $A$ is a set of arguments, $E \subseteq A \times A$ is a set of edges between arguments, β is a function assigning a base score β (a) to each argument $a \in A$ , and $w : E \to ℝ$ assigns a weight to every edge. For each argument $a \in A$ , the interpretation of Q under MLP-based semantics is given by a function σ_MLP defined by: $σ_{MLP} (a) = lim_{k \to \infty} s_{a}^{(k)}$ , when the limit exists, and ⊥ (undefined) otherwise; where $s_{a}^{(k)}$ is a value in the interval [0, 1], and k represents the iteration. More precisely, for all arguments $a \in A$ ,

$s_{a}^{(0)} = β (a)$ (initial strength),

$s_{a}^{(i + 1)} = φ_{l} (\ln (\frac{β (a)}{1 + β (a)}) + α_{a}^{(i + 1)})$ (influence),

where φ_l is the logistic function and $α_{a}^{(i + 1)} = \sum_{(b, a) \in E} w (b, a) \cdot s_{b}^{(i)} .$

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 $S$ of argument valuation (again, we assume $S$ to be either [0, 1] or $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 = 〈 A, R, π 〉$ , let $L$ be a propositional language whose set of propositional variables Prop is the set of arguments $A$ . We assume that the language $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 $A$ using connectives ∧, ∨ and ¬ boolean combination of arguments (and denote them with α, β, γ).

Let ⊗, ⊕, ⊳ and ⊖ be the truth degree functions in the truth degree set $S$ for the connectives ∧, ∨, ¬ and → (respectively). As $S$ is either [0, 1] or the finite set $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 $σ : A \to S$ of graph G, assigning to each argument $A_{i} \in A$ a truth degree in $S$ , can be regarded as a many-valued valuation, which can be inductively extended to all propositional formulas of $L$ as follows:

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

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

5.1 Preferences with respect to arguments

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

Definition 6. Given a semantics $(S, Σ)$ , 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 $S =$ $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
₁}σ′ and σ′ < _{A
₃}σ.

For instance, σ = (1, 4/5, 0, 1, 1/5, 1) is preferred to all other labellings with respect to <_{A
₆}, 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 $S = 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 $(S, Σ)$ , the preferential interpretation of G with respect to $(S, Σ$ ) is the triple $I = (S, Σ, {<_{α}})$ .

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 $L^{T}$ is obtained by extending language $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 = (S, Σ, {<_{α}})$ . Informally, the preference relation <_α allows to identify the most typical situations in which α holds.

Definition 8. Given a preferential interpretation $I = (S, Σ, {<_{α}})$ , 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 = (C_{5}, Σ, {<_{α}})$ , where Σ is the set of labellings of graph G in Fig. 1 in the φ-coherent semantics with truth space $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 $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 = (S, Σ, {<_{α}})$ of an argumentation graph G, the truth degree of an implication α → β wrt. I is defined as:

$(α \to β)^{I} = \inf_{σ \in Σ} (σ (α) ⊳ σ (β))$ .

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

Definition 10. Given a preferential interpretation $I = (S, Σ, {<_{α}})$ 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 $S = 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 $S = C_{n}$ and the weighted ${LC}_{n} T$ knowledge bases defined in Section 2, under the φ-coherent semantics.

Let us consider a weighted argumentation graph $G = 〈 A, R, π 〉$ , as in Section 3, and its φ-coherent semantics, for some monotonically non-decreasing function $φ : ℝ \to S$ . Let $I_{G} = (S, Σ, {<_{α}})$ 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 A$ as a named concept in the logic ${LC}_{n} T$ , we can define a conditional knowledge base $K^{G} = (T, D, A)$ associated with G, as follows:

$T = A = \emptyset$ , and

$D = {(T (A_{i}) ⊑ A_{j}, w_{ji}) ∣ (A_{j}, A_{i}) \in R 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

{LC}_{n} 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} = (S, Σ, {<_{α}})$ , the thesis can be proved by building a canonical interpretation of K^G in ${LC}_{n} T$ , whose domain is the set Σ of all many-valued labelling of the weighted graph G.

Let $N_{C} = A$ , and let N_I = {x₁, x₂, …} contain one individual name x_j for each labelling σ_j ∈ Σ. We can define an ${LC}_{n} T$ preferential interpretation I = 〈 Δ^I, · ^I) as follows:

Δ^I = Σ;

for all x_j ∈ N_I, $x_{j}^{I} = σ_{j}$ ;

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

As usual in ${LC}_{n} T$ interpretations, the valuation function ·^I induces, for each concept A_i ∈ N_C, a preference relation $<_{A_{i}}^{'}$ on Δ^I such that:

$σ_{j} <_{A_{i}}^{'} σ_{k}$ iff $A_{i}^{I} (σ_{j}) > A_{i}^{I} (σ_{k})$

Hence, by construction, $σ_{j} <_{A_{i}}^{'} σ_{k}$ iff σ_j (A_i) > σ_k (A_i)

so that the preference relations $<_{A_{i}}^{'}$ defined on the domain of the ${LC}_{n} 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_{α}^{I} (σ) = σ (α)$ , 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} ⊓ A_{2} ⊓ \neg A_{3})^{I} (σ) = A_{1}^{I} (σ) \otimes A_{2}^{I} (σ) \otimes ⊖ A_{3}^{I} (σ) = σ (A_{1}) \otimes σ (A_{2}) \otimes ⊖ σ (A_{3}) = σ (A_{1} \land A_{2} \land \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} (y) = A_{i}^{J} (z)$ . 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} (z) = φ (\sum_{(T (A_{i}) ⊑ A_{j}, w_{ji}) \in T} w_{ji} \cdot A_{j}^{I} (z))$ (4) Then z determines a labelling σ_z of G, defined as $σ_{z} (A_{j}) = A_{j}^{I} (z)$ , 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 $S = C_{n}$ . For the case when the truth degree set $S$ is [0, 1], a mapping from weighted argumentation graphs to weighted knowledge bases in the fuzzy description logic $LC 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 ${LC}_{n} 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 = 〈 A,$ $R, π 〉$ under the φ-coherent semantics with truth degree set $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 $| A |$ .

In the following, we show that verifying whether a graded implication T (α) → β θ l over the interpretation $I_{G} = (S, Σ, {<_{α}})$ , 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 = 〈 A,$ $R, π 〉$ 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 $S = 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 ${LC}_{n} T$ knowledge base K (Theorem 1 in [2]), the next result is established.

Proposition 4. (Complexity upper bound) Let $G = 〈 A,$ $R, π 〉$ 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 $S = 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 = 〈 A,$ $R, π 〉$ 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 $S = C_{n}$ , is PNP[log]-hard in the size of the argumentation graph G, even if α and β are arguments $A_{i} \in 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 = 〈 A,$ $R, π 〉$ , and $φ : ℝ \to 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} = (S, Σ, {<_{α}})$ , with Σ the set of all the φ-coherent labellings of G with truth degree set $S = C_{n}$ .

We let the set of arguments $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 $φ (w) = min (1, max (0, w + \frac{1}{n}))$ , 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 $⊤ \in A$ and arc $\underset{\to}{+ 1}$ ⊤ to enforce σ (⊤) =1;

for each x ∈ vars (Γ), nodes A_x, A_¬x and arcs A_x $\underset{\to}{+ 1}$ A_x, A_¬x $\underset{\to}{+ 1}$ A_¬x, A_x $\underset{\to}{- 2}$ A_¬x, A_x $\underset{\to}{- 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 ⊤ $\underset{\to}{- 1}$ C_i, as well as arc A_ℓ $\underset{\to}{+ 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 $⊤ \underset{\to}{- \frac{1}{n}} Sat$ , as well as arc $C_{i} \underset{\to}{+ \frac{1}{n}} Sat$ for all i = 1 . . n, to enforce $σ (Sat) = \frac{k}{n}$ , where k is the number of i = 1 . . n such that σ (C_i) =1;

node Even₀ and arc ⊤ $\underset{\to}{+ 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:

⊤ $\underset{\to}{- 1}$ Even_i,1, Even_i,1 $\underset{\to}{+ 1}$ Even_i,1, Even_i-1 $\underset{\to}{- 2}$ Even_i,1, C_i $\underset{\to}{+ 1}$ Even_i,1, to enforce σ (Even_i,1) =1 if σ (Even_i-1) =0 and σ (C_i) =1, and 0 otherwise;

⊤ $\underset{\to}{- 1}$ Even_i,2, Even_i,2 $\underset{\to}{+ 1}$ Even_i,2, Even_i-1 $\underset{\to}{+ 1}$ Even_i,2, C_i $\underset{\to}{- 2}$ Even_i,2, to enforce σ (Even_i,2) =1 if σ (Even_i-1) =1 and σ (C_i) =0, and 0 otherwise;

⊤ $\underset{\to}{+ 1}$ Even_i, Even_i,1 $\underset{\to}{+ 2}$ Even_i, Even_i,2 $\underset{\to}{+ 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 $σ (Sat) = \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, $σ (Sat) = \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 $σ (T (Sat)) = \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 $D$ ; a direct mapping of K into an argumentation graph G can be given in this case.

Let $K = (T, D, A)$ , where $T = A = \emptyset$ , and for all typicality inclusions $(T (A) ⊑ B, w_{i}) \in D$ , A and B are atomic concepts. The knowledge base K can be mapped directly into a weighted argumentation graph $G^{K} = 〈 A, R, π 〉$ , in the obvious way, by letting the set $A$ of arguments to be the set of all concept names occurring in K, plus arguments ⊤ and ⊥, and by letting $R = {(A_{j}, A_{i}) ∣ (T (A_{i}) ⊑ A_{j}, w_{j, i}) \in D} \cup R_{⊤} \cup R_{⊥}$ , and π (A_j, A_i) = w_j,i, for A_i, A_j such that $(T (A_{i}) ⊑ A_{j}, w_{j, i}) \in D$ , while $R_{⊤}$ and $R_{⊥}$ are used to constrain the values of arguments ⊤ and ⊥ to be, resp., 0 and 1: $R_{⊤} = {(⊤, ⊤)}$ , with π (⊤ , ⊤) = +1 (as in Fig. 2 (a)), while $R_{⊥} = {(⊤, ⊥)}$ , 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 $φ (w) = \min (1, \max (0, w + \frac{1}{n})$ .

For step (a), let $K = 〈 T, D, A 〉$ be a weighted knowledge base which allows in the DBox $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 $D$ with a new named concept A_i, thus replacing in $D$ the weighted inclusion above with (T (A_i) ⊑ A_j, w_j,i), and adding to the TBox $T$ the two inclusions A_i ⊑ C_i ≥ 1 and C_i ⊑ A_i ≥ 1.

Let us call $K^{'} = 〈 T^{'}, D^{'}, 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^{'} = 〈 T^{'}, D^{'}, A^{'} 〉$ obtained by step (a), and encode the strict axioms occurring in the TBox into the defeasible part of the knowledge base, by adding to $D^{'}$ some new weighted inclusions (possibly, with the addition of new concept names).

As we have assumed that TBox $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 $T^{'}$ . Also, ABox $A^{'}$ is empty, as $A^{'} = A = \emptyset$ .

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

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

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 $T^{'}$ , a new concept name A_C is introduced in the language. For each concept name B ∈ N_C occurring in $T^{'}$ , 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_B₁⊗B₂, A_B₁⊕B₂, A_⊖B₂, rather than A_B₁⊓B₂, A_B₁⊔B₂, A_¬B₂

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_B₁⊗B₂, and the following weighted inclusions in $D^{″}$ :

$T (A_{B_{1} \otimes B_{2}}) ⊑ ⊤, - 1 - \frac{1}{n}$

T (A_B₁⊗B₂) ⊑ A_B
₁, + 1

T (A_B₁⊗B₂) ⊑ A_B
₂, + 1

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

$T (A_{B_{1} \oplus B_{2}}) ⊑ ⊤, - \frac{1}{n}$

T (A_B₁⊕B₂) ⊑ A_B
₁, + 1

T (A_B₁⊕B₂) ⊑ A_B
₂, + 1

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

$T (A_{⊖ B}) ⊑ ⊤, + 1 - \frac{1}{n}$

T (A_⊖B) ⊑ A_B, - 1

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

$T (A_{B_{1} ⊳ B_{2}}) ⊑ ⊤, + 1 - \frac{1}{n}$

T (A_B₁⊳B₂) ⊑ A_B
₁, - 1

T (A_B₁⊳B₂) ⊑ A_B
₂, + 1

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

$A_{B_{1} \otimes B_{2}}^{I} (x) = B_{1}^{I} (x) \otimes B_{2}^{I} (x)$

$A_{B_{1} \oplus B_{2}}^{I} (x) = B_{1}^{I} (x) \oplus B_{2}^{I} (x)$

$A_{⊖ B}^{I} (x) = ⊖ B^{I} (x)$

$A_{B_{1} ⊳ B_{2}}^{I} (x) = B_{1}^{I} (x) ⊳ B_{2}^{I} (x)$

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} (x) = C^{I} (x) ⊳ D^{I} (x)$ , we have to require that $A_{C ⊳ D}^{I} (x) \geq l$ .

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

$T (A_{l}) ⊑ ⊤, + l - \frac{1}{n}$

The value of the implication $A_{l}^{I} (x) ⊳ A_{C ⊳ D}^{I} (x)$ will be 1 when $A_{C ⊳ D}^{I} (x) \geq 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} (x) ⊳ A_{C ⊳ D}^{I} (x) = A_{A_{l} ⊳ (C ⊳ D)}^{I} (x) = 1$ . To avoid that $A_{A_{l} ⊳ (C ⊳ D)}^{I} (x)$ takes a value different from 1, we add a new concept name A_C^⊑D≥l and the following inclusions in $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))}^{I} (x) = 1$ , then $A_{C^{⊑} D \geq l}^{I} (x)$ must be 1 and C^I (x) ⊳ D^I (x) ≥ l holds. Otherwise, $A_{(A_{l} ⊳ (C ⊳ D))}^{I} (x) < 1$ , and any possible value assignment to $A_{C^{⊑} D \geq l}^{I} (x)$ falsifies the φ-coherence condition for $A_{C^{⊑} D \geq l}^{I} (x)$ . 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^{″} = 〈 T^{″}, D^{″}, A^{″} 〉$ , is such that $T^{″} = A^{″} = \emptyset$ , and $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 $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 = 〈 A, R, π 〉$ , the domain of argument valuation $S = C_{n}$ , and a monotonically non-decreasing function $φ : ℝ \to 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 = (S, Σ, {<_{α}})$ 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 $φ (w) = \frac{v}{n}$ if and only if LB < w ≤ UB holds;

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

link(A,B,w) for each support/attack arc A $\underset{\to}{w}$ B in $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

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

C_{n}

and fixes the interpretation of ⊥ and ⊤. Line 2 guesses a truth degree for arguments in

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

σ (T (α_{q})) ⊳ σ (β_{q}) θ_{>} \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

σ (T (α_{q})) ⊳ σ (β_{q}) θ_{<} \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 $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 $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 $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 ${LC}_{n} 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 $Π_{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 ${LC}_{n}$ of a finitely-valued $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.

Footnotes

Acknowledgements

We thank the anonymous referees for their helpful comments and suggestions that helped to improve the paper. This work was partially supported by the INDAM-GNCS Project 2024 “LCXAI: Logica Computazionale per eXplainable Artificial Intelligence”. Mario Alviano was partially supported by Italian Ministry of University and Research (MUR) under PRIN project PRODE “Probabilistic declarative process mining” (CUP H53D23003420006), under PNRR projects FAIR “Future AI Research” (CUP H23C22000860006), Tech4You “Technologies for climate change adaptation and quality of life improvement” (CUP H23C22000370006), and SERICS “SEcurity and RIghts in the CyberSpace” (CUP H73C22000880001); by Italian Ministry of Health (MSAL) under POS projects CAL.HUB.RIA (CUP H53C22000800006) and RADIOAMICA (CUP H53C22000650006); by Italian Ministry of Enterprises and Made in Italy under project STROKE 5.0 (CUP B29J23000430005); by the LAIA lab (part of the SILA labs).

This definition is the same as in [], but for the fact that in the domain and range of function h and in the domain of function g interval [0, 1] is replaced by $ℝ$ .

Note that in [], {B₁, …, B_n} is the set Att_G (A) of all the direct attackers to A in G.

Note that α and β in a strict or a conditional implication are boolean combination of arguments, and cannot contain implications.

References

Alviano

, Giordano

and Theseider Dupre

, Typicality, conditionals and a probabilistic semantics for gradual argumentation. In Proc. 21st International Workshop on Non-Monotonic Reasoning (NMR 2023), Rhodes, Greece, September 2-4, 2023, volume 3464 of CEUR Workshop Proceedings, (2023), pp. 4–13. CEUR-WS.org.

Alviano

, Giordano

and Theseider Dupre

, Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases. In Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Dresden, Germany, September 20-22, 2023, Proceedings, volume 14281 of LectureNotes in Computer Science, pages 481–497. Springer, 2023. doi: 10.1007/978-3-031-43619-2_33.

Alviano

, Bartoli

, Botta

, Esposito

, Giordano

and Theseider Dupre

, A preferential interpretation of multilayer perceptrons in a conditional logic with typicality, Int. Journal of Approximate Reasoning (2024), 164. URL https://doi.org/10.1016/j.ijar.2023.109065.

Amgoud

and Ben-Naim

, Evaluation of arguments in weighted bipolar graphs. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 14th European Conference, ECSQARU 2017, Lugano, Switzerland, July 10-14, 2017, Proceedings, volume 10369 of Lecture Notes in Computer Science, (2017), pp. 25–35. Springer.

Amgoud

and Doder

, Gradual semantics accounting for varied-strength attacks. In Proceedings AAMAS ’19, Montreal, QC, Canada May 13-17, (2019), pp. 1270–1278.

Amgoud

, Cayrol

and Lagasquie-Schiex

, On the bipolarity in argumentation frameworks. In 10th International Workshop on Non-Monotonic Reasoning (NMR 2004), Whistler, Canada, June 6-8, 2004, Proceedings, (2004), pp. 1–9.

Amgoud

, Ben-Naim

, Doder

and Vesic

, Acceptability semantics for weighted argumentation frameworks. In IJCAI 2017, Melbourne, Australia, (2017), pp. 56–62.

Amgoud

and Ben-Naim

, Ranking-based semantics for argumentation frameworks. In Scalable Uncertainty Management - 7th International Conference, SUM 2013, Washington, DC, USA, September 16-18, 2013. Proceedings, volume 8078 of Lecture Notes in Computer Science, (2013), pp. 134–147. Springer.

Baader

, Calvanese

, McGuinness

D.L.

, Nardi

and Patel-Schneider

P.F.

, The Description Logic Handbook - Theory, Implementation, and Applications. Cambridge, 2007.

10.

Baroni

, Rago

and Toni

, How many properties do we need for gradual argumentation? In Proc. AAAI 2018, New Orleans, Louisiana, USA, February 2-7, (2018), pp. 1736–1743.

11.

Baroni

, Rago

and Toni

, From fine-grained properties to broad principles for gradual argumentation: A principled spectrum, Int. J. Approx. Reason.105 (2019), 252–286.

12.

Bartoli

, Botta

, Esposito

, Giordano

and Theseider Dupre

, An ASP approach for reasoning about the conditional properties of neural networks: an experiment in the recognition of basic emotions. In Datalog 2.0 2022, volume 3203 of CEUR Workshop Proceedings, (2022), pp. 54–67. CEUR-WS.org. URL, http://ceur-ws.org/Vol-3203/paper4.pdf.

13.

Bench-Capon

T.J.M.

, Persuasion in practical argument using value-based argumentation frameworks, J. Log. Comput.13(3) (2003), 429–448.

14.

Benferhat

, Cayrol

, Dubois

, Lang

and Prade

, Inconsistency management and prioritized syntax-based entailment, In Proc. IJCAI’93, Chambery, (1993), pp. 640–647.

15.

Bobillo

and Straccia

, Reasoning with the finitely many-valued Łukasiewicz fuzzy Description Logic SROIQ, Inf. Sci. 181(4) (2011), 758–778.

16.

Bobillo

and Straccia

, Reasoning within fuzzy OWL 2 EL revisited, Fuzzy Sets Syst. 351 (2018), 1–40.

17.

Bobillo

, Delgado

, Gomez-Romero

and Straccia

, Joining Godel and Zadeh Fuzzy Logics in Fuzzy Description Logics, Int. J. Uncertain. Fuzziness Knowl. Based Syst.20(4) (2012), 475–508.

18.

Bonatti

P.A.

and Sauro

, On the logical properties of the nonmonotonic description logic DLN, Artif. Intell.248 (2017), 85–111.

19.

Bonzon

, Delobelle

, Konieczny

and Maudet

, A comparative study of ranking-based semantics for abstract argumentation. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, (2016), pp. 914–920. AAAI Press.

20.

Booth

, Casini

, Meyer

and Varzinczak

, On rational entailment for propositional typicality logic, Artif. Intell. (2018), 277.

21.

Borgwardt

and Penaloza

, Undecidability of fuzzy description logics. In G. Brewka, T. Eiter and S.A. McIlraith, editors, Proc. KR 2012, Rome, Italy, June 10-14, (2012), 2012.

22.

Borgwardt

and Penaloza

, The complexity of lattice-based fuzzy description logics, J. Data Semant.2(1) (2013), 1–19.

23.

Brewka

, A rank based description language for qualitative preferences. In 6th Europ. Conf. on Artificial Intelligence, ECAI’2004, Valencia, Spain, August 22-27, (2004), pp. 303–307.

24.

Brewka

, Strass

, Ellmauthaler

, Wallner

J.P.

and Woltran

, Abstract dialectical frameworks revisited. In IJ-CAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, (2013), pp. 803–809. IJCAI/AAAI.

25.

Britz

, Heidema

and Meyer

, Semantic preferential subsumption. In G. Brewka and J. Lang, editors, KR 2008, pp. 476–484, Sidney, Australia, September 2008. AAAI Press.

26.

Britz

, Casini

, Meyer

, Moodley

, Sattler

and Varzinczak

, Principles of KLM-style defeasible description logics, ACM Trans. Comput. Log.22(1) (2021), 1:1–1:46.

27.

Casini

and Straccia

, Rational Closure for Defeasible Description Logics. In T. Janhunen and I. Niemela, editors, JELIA 2010, volume 6341 of LNCS, (2010), pp. 77–90, Helsinki Sept. 2010. Springer.

28.

Casini

and Straccia

, Towards Rational Closure for Fuzzy Logic: The Case of Propositional Godel Logic. In Proc. LPAR-19, Stellenbosch, South Africa, December 14-19, volume 8312 of LNCS, (2013), pp. 213–227. Springer.

29.

Casini

and Straccia

, Towards rational closure for fuzzy logic: The case of propositional godel logic. In LPAR-19, Stellenbosch, South Africa, December 14-19, 2013, Proceedings, (2013), pp. 213–227.

30.

Casini

, Meyer

, Varzinczak

I.J.

and Moodley

, Non-monotonic Reasoning in Description Logics: Rational Closure for the ABox. In 26th International Workshop on Description Logics (DL 2013), volume 1014 of CEUR Workshop Proceedings (2013), pp. 600–615.

31.

Casini

, Straccia

and Meyer

, A polynomial time subsumption algorithm for nominal safe elo⊥ under rational closure, Inf. Sci.501 (2019), 588–620.

32.

Cayrol

and Lagasquie-Schiex

, Graduality in argumentation, J. Artif. Intell. Res.23 (2005), 245–297 doi: 10.1613/jair.1411.

33.

d’Avila Garcez

A.S.

, Gabbay

D.M.

, and Lamb

L.C.

, Value-based argumentation frameworks as neural-symbolic learning systems, J. Log. Comput.15(6) (2005), 1041–1058.

34.

Dung

P.M.

, On the acceptability of arguments and its fundamental role in non-monotonic reasoning, logic programming and n-person games, Artif. Intell.77 (1995), 321–357.

35.

Dunne

P.E.

, Hunter

, McBurney

, Parsons

and Wooldridge

M.J.

, Weighted argument systems: Basic definitions, algorithms, and complexity results, Artif. Intell.175(2) (2011), 457–486.

36.

Egilmez

, Martins

J.G.

and Leite

, Extending social abstract argumentation with votes on attacks. In TAFA 2013, Beijing, China, Aug. 3-5, LNCS 8306, (2013), pp. 16–31. Springer.

37.

Gabbay

D.M.

, Equational approach to argumentation networks, Argument Comput.3(2-3) (2012), 87–142.

38.

Garcia-Cerdana

, Armengol

and Esteva

, Fuzzy description logics and t-norm based fuzzy logics, Int. J. Approx. Reason.51(6) (2010), 632–655.

39.

Gebser

, Kaminski

, Kaufmann

and Schaub

, Multi-shot ASP solving with clingo, Theory Pract. Log. Program.19(1) (2019), 27–82.

40.

Geffner

and Pearl

, Conditional entailment: Bridging two approaches to default reasoning, Artif. Intell.53(2-3) (1992), 209–244.

41.

Giordano

, On the KLM properties of a fuzzy DL with Typicality. In Proc. ECSQARU 2021, Prague, Sept. 21-24, 2021, volume 12897 of LNCS, (2021), pp. 557–571. Springer.

42.

Giordano

, From weighted conditionals of multilayer perceptrons to a gradual argumentation semantics. In 5th Work-shop on Advances in Argumentation in Artif. Intell., Milan, Italy, Nov. 29, volume 3086 of CEUR Workshop Proceedings. CEUR-WS.org, 2021. URL http://ceur-ws.org/Vol-3086/paper8.pdf.

43.

Giordano

, From weighted conditionals with typicality to a gradual argumentation semantics and back. In Proc. 20th International Workshop on Non-Monotonic Reasoning, NMR 2022, Part of FLoC 2022, Haifa, Israel, August 7-9, 2022, volume 3197 of CEUR Workshop Proceedings, (2022), pp. 127–138. CEUR-WS.org.

44.

Giordano

and Theseider Dupre

, An ASP approach for reasoning in a concept-aware multipreferential lightweight DL, TPLP10(5) (2020), 751–766.

45.

Giordano

and Theseider Dupre

, Weighted defeasible knowledge bases and a multipreference semantics for a deep neural network model. In Proc. JELIA 2021, May 17-20, volume 12678 of LNCS, (2021), pp. 225–242. Springer.

46.

Giordano

and Theseider Dupre

, An ASP approach for reasoning on neural networks under a finitely many-valued semantics for weighted conditional knowledge bases, Theory Pract. Log. Program.22(4) (2022), 589–605. doi: 10.1017/S1471068422000163

47.

Giordano

, Gliozzi

, Olivetti

and Pozzato

G.L.

, Preferential Description Logics. In LPAR 2007, volume 4790 of LNAI, (2007), pp. 257–272, Yerevan, Armenia, October. Springer.

48.

Giordano

, Gliozzi

, Olivetti

and Pozzato

G.L.

, ALC+T: a preferential extension of Description Logics, Fundamenta Informaticae96 (2009), 1–32.

49.

Giordano

, Gliozzi

, Olivetti

and Pozzato

G.L.

, Semantic characterization of rational closure: From propositional logic to description logics, Art. Int.226 (2015), 1–33.

50.

Gottwald

, A Treatise on Many-valued Logics, Research Studies Press, 2001.

51.

Haykin

, Neural Networks - A Comprehensive Foundation, Pearson, 1999.

52.

Heyninck

, Kern-Isberner

and Thimm

, On the correspondence between abstract dialectical frameworks and nonmonotonic conditional logics. In Proceedings of the Thirty-Third International Florida Artificial Intelligence Research Society Conference, May 17-20, 2020, (2020), pp. 575–580. AAAI Press.

53.

Hitzler

, Krotzsch

and Rudolph

, Foundations of Semantic Web Technologies, Chapman and Hall/CRC Press, 2010. ISBN 9781420090505. URL http://www.semantic-web-book.org/.

54.

Janssen

, De Cock

and Vermeir

, Fuzzy argumentation frameworks. In IPMU (2008), pp. 513–520.

55.

Kern-Isberner

, Conditionals in Nonmonotonic Reasoning and Belief Revision - Considering Conditionals as Agents, volume 2087 of LNCS. Springer, 2001.

56.

Kraus

, Lehmann

and Magidor

, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence44(1-2) (1990), 167–207.

57.

Lehmann

and Magidor

, What does a conditional knowledge base entail?Artificial Intelligence55(1) (1992), 1–60. ISSN 0004-3702.

58.

Lukasiewicz

and Straccia

, Description logic programs under probabilistic uncertainty and fuzzy vagueness, Int. J. Approx. Reason.50(6) (2009), 837–853.

59.

Mossakowski

and Neuhaus

, Modular semantics and characteristics for bipolar weighted argumentation graphs, CoRR, abs/1807.06685, 2018.

60.

Pearl

, System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In TARK’90, Pacific Grove, CA, USA, (1990), pp. 121–135.

61.

Potyka

, Interpreting neural networks as quantitative argumentation frameworks. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, February 2-9, 2021, (2021), pp. 6463–6470. AAAI Press.

62.

Skiba

and Thimm

, Ordinal conditional functions for abstract argumentation. In COMMA 2022, Cardiff, Wales, UK, 14-16 September 2022, volume 353 of Frontiers in Artificial Intelligence and Applications, (2022), pp. 308–319. IOS Press.

63.

Stoilos

, Stamou

G.B.

, Tzouvaras

, Pan

J.Z.

and Horrocks

, Fuzzy OWL: uncertainty and the semantic web. In OWLED*05 Workshop, volume 188 of CEUR Workshop Proc., 2005.

64.

Straccia

, Towards a fuzzy description logic for the semantic web (preliminary report). In ESWC 2005, Heraklion, Crete, May 29 - June 1, 2005, volume 3532 of LNCS, (2005), pp. 167–181. Springer.

65.

Wagner

K.W.

, Bounded query classes, SIAM J. Comput.19(5) (1990), 833–846.

66.

Weydert

, System JLZ - rational default reasoning by minimal ranking constructions, Journal of Applied Logic1(3-4) (2003), 273–308.

67.

Weydert

, On the plausibility of abstract arguments. In Proc. Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 12th European Conference, ECSQARU 2013, Utrecht, The Netherlands, July 8-10, 2013, volume 7958 of LNCS (2013), pp. 522–533. Springer.

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

Abstract

Keywords

1 Introduction

2 Background: LC n with typicality and weighted knowledge bases

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

5.1 Preferences with respect to arguments

5.2 Graded implications

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

9 Implementation and empirical assessment

9.1 Implementation

Footnotes

Acknowledgements

References

2 Background: ${LC}_{n}$ with typicality and weighted knowledge bases