<figure><img src="image_1.png" /></figure>

HAL
open science

# A Novel Approach for Resolving Knowledge Inconsistency on Ontology Syntactic Level

Trung Van Nguyen, Jason J. Jung, Hanh Huu Hoang

► To cite this version:

Trung Van Nguyen, Jason J. Jung, Hanh Huu Hoang. A Novel Approach for Resolving Knowledge Inconsistency on Ontology Syntactic Level. 4th IFIP International Conference on Artificial Intelligence in Theory and Practice (AI 2015), Oct 2015, Daejeon, South Korea. pp.39-49, 10.1007/978-3-319-25261-2_4. hal-01383945

HAL Id: hal-01383945

https://inria.hal.science/hal-01383945

Submitted on 19 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Novel Approach for Resolving Knowledge Inconsistency on Ontology Syntactic level

Trung Van Nguyen<fnref n="1" />, Jason J. Jung<fnref n="2" />, and Hanh Huu Hoang<fnref n="3" />

**Abstract.** Solving the inconsistency of knowledge is a challenging task in the ontology integration. There are two levels for processing knowledge inconsistency which are based on logics: syntactic level and semantic level. In this paper, we propose a consensus-based method to resolve inconsistent knowledge on the syntactic level, where a knowledge state can be represented by a conjunction of literals.

**Keywords:** ontology integration, consensus theory, syntactic level, con-junction, inconsistency

## 1 Introduction

The inconsistency consists of two levels in knowledge processing based on log-ics [4]: the syntactic level and the semantic level. In the syntactic level, knowledge states can be represented by logic expressions, and they are in conflict if expres-sions' syntaxes are different. Meanwhile, in the semantic level, the knowlege inconsistency and consistency are considered further at their interpretations [7].

In this paper, we propose a consensus-based method to resolve the knowl-edge inconsistency on its syntactic level. One of the most important things in consensus-based methods is the distance function of two elements in the uni-verse set. There have been several and similar approaches to evaluate distance between two logic expressions: Zhisheng Huang, Frank van Harmelen [3] mea-sure a so-called relevance between two formulas by considering the number of their common and different symbols. Ferilli [1, 2] further considered occurrences of objects, predicates in the formulas based on taxonomic background knowledge such as WordNet ontology. We assume that, a knowledge state can be expressed as a conjunction of literals as [4]. However, by using other distance function of two sets of symbols than [4], we analyse and prove some interesting properties of

<footnote n="1">¹ College of Sciences, Hue University
77 Nguyen Hue Street, Hue, Vietnam
nvtrung@hueuni.edu.vn</footnote>

<footnote n="2">² Department of Computer Engineering, Chung-Ang University
Seoul, Republic of Korea 156-756
j2jung@gmail.com</footnote>

<footnote n="3">³ Hue University
3 Le Loi Street, Hue, Vietnam
hhhanh@hueuni.edu.vn</footnote>
postulates for consensus functions. Based on these properties, we propose a new algorithm for determining the consensus for a conflict profile of conjunctions.

Our paper will be detailed and structured as follows: Section 2 formalises the problem of determining the consensus for a conflict profile of conjunctions. Meanwhile, Section 3 presents postulates for the consensus function and analyse their properties. Based on this, we propose a new algorithm for determining the consensus in Section 4. The paper is then concluded with discussions and future work in Section 5.

## 2 Problems of determining consensus for a conflict profile of conjunctions

In this section, we recall essential notions directly used in formalising the problem of determining the consensus for a conflict profile of conjunctions in Nguyen's work [4].

Assume that, for expressing opinion about a subject in the real world, an expert agent uses a conjunction of literals $t_1 \wedge t_2 \wedge \dots t_k$, where $t_i \in \mathbf{L}$ or $t_i = \neg t'_{i'}$ and $t'_{i'} \in \mathbf{L}$. $\mathbf{L}$ is a definite set of symbols, which expresses a positive logic value, reference to an event in the real world.

A conjunction $x$ can be expressed as $(x^+, x^-)$, where $x^+$ contains $t \in \mathbf{L}$, and $x^-$ contains $t$ and $\neg t \in \mathbf{L}$. For example, $x = a \wedge \neg b \wedge c$, which $a, b, c \in \mathbf{L}$ can be written as $(x^+, x^-)$, where $x^+ = \{a, c\}$ and $x^- = \{b\}$.

By $\text{Conj}(\mathbf{L})$ we denote the set of all conjunctions with symbols from set $\mathbf{L}$.

**Definition 1 (Nonconflicting conjunction)** A conjunction $(x^+, x^-)$ where $x^+, x^- \subseteq \mathbf{L}$ is nonconflicting if $x^+ \cap x^- = \emptyset$.

**Definition 2 (Inconsistent conjunctions, sharply inconsistent conjunctions)**

Let $x = (x^+, x^-)$, $x' = (x'^+, x'^-)$ $\in \text{Conj}(\mathbf{L})$ are nonconflicting conjunctions.

We say:

(a) $x$ is inconsistent with $x'$ if

$$x^+ \cap x'^- \neq \emptyset \quad \text{or} \quad x'^+ \cap x^- \neq \emptyset,$$

(b) $x$ is sharply inconsistent with $x'$ if they are inconsistent and

$$x^+ \cap x'^+ = \emptyset \quad \text{and} \quad x^- \cap x'^- = \emptyset.$$

**Definition 3** A set of nonconflicting conjunctions

$$\mathbf{X} = \{x_i = (x^+, x^-) \in \text{Conj}(\mathbf{L}) : i = 1, 2, \dots, n\}$$

is inconsistent if $\bigcup_{x \in \mathbf{X}} x^+ \cap \bigcup_{x \in \mathbf{X}} x^- \neq \emptyset$, otherwise it is consistent.

Then we propose an our own distance function $d_\wedge$ for conjunctions. This function is based on the distance between sets of symbols.
**Definition 4 (Distance between two finite sets)** By the distance between two finite sets $\mathbf{X}_1, \mathbf{X}_2$ we understand the following number

$$ \eta(\mathbf{X}_1, \mathbf{X}_2) = \frac{\mathrm{card}(\mathbf{X}_1 \triangle \mathbf{X}_2)}{\mathrm{card}(\mathbf{L})} \qquad (1) $$

where, $\mathrm{card}(\mathbf{L})$ is the number of elements in $\mathbf{L}$, and $\mathbf{X}_1 \triangle \mathbf{X}_2$ is symmetric difference of the two sets $\mathbf{X}_1$ and $\mathbf{X}_2$.

**Definition 5 (Distance between two conjunctions [4])** By the distance between two conjunctions $x_1, x_2 \in \mathrm{Conj}(\mathbf{L})$ we understand the following number

$$ d_{\wedge}(x_1, x_2) = w_1 \eta(x_1^+, x_2^+) + w_2 \eta(x_1^-, x_2^-) , $$

where

* $\eta(x_1^+, x_2^+)$ is the distance between sets of nonnegated symbols in conjunctions $x_1$ and $x_2$.

* $\eta(x_1^-, x_2^-)$ is the distance between sets of negated symbols in conjunctions $x_1$ and $x_2$.

* $w_1, w_2$ are the weights of distances $\eta(x_1^+, x_2^+)$ and $\eta(x_1^-, x_2^-)$ in distance $d_{\wedge}(x_1, x_2)$, respectively, which satisfy the conditions:

$$ w_1 + w_2 = 1 \quad \text{and} \quad 0 < w_1, w_2 < 1. $$

In this paper, we use $w_1 = w_2 = \frac{1}{2}$.

By $\mathbf{U}$ we denote a finite set of objects representing possible values for a knowledge state. We also denote:

* $\prod_k(\mathbf{U})$ is the set of all $k$-element subsets (with repetitions) of set $\mathbf{U}$ ($k \in \mathbb{N}$, set of natural numbers).

* $\prod(\mathbf{U}) = \bigcup_{k \in \mathbb{N}} \prod_k(\mathbf{U})$ is the set of all nonempty subsets with repetitions of set $\mathbf{U}$. An element in $\prod(\mathbf{U})$ is called as a conflict profile.

The problem of determining consensus for a conflict profile of conjunctions is formulated as follows [4]:

For a given conflict profile of conjunctions

$$ \mathbf{X} := \{x_i = (x_i^+, x_i^-) \in \mathrm{Conj}(\mathbf{L}) : i = 1, 2, \dots, n\}. $$

It is necessary to determine a conjunction $x^* \in \mathrm{Conj}(\mathbf{L})$, called as a consensus of $\mathbf{X}$.

# 3 Consensus functions and Postulates for consensus

We also start with recalling definitions in [4]:
**Definition 6 (Consensus function for profiles)** By a consensus function for profiles of conjunctions we understand a function

$$C : \prod (\mathrm{Conj}(\mathbf{L})) \to 2^{\mathrm{Conj}(\mathbf{L})},$$

which satisfies one or more of the following postulates.

P1. For each conjunction $(x^+, x^-) \in C(X)$ there should be $\bigcap_{x \in X} x^+ \subseteq x^+$ and $\bigcap_{x \in X} x^- \subseteq x^-.$

P2. For each conjunction $(x^+, x^-) \in C(X)$ there should be $x^+ \subseteq \bigcup_{x \in X} x^+$ and $x^- \subseteq \bigcup_{x \in X} x^-$.

P3. If $X$ is consistent then conjunction $(\bigcup_{x \in X} x^+, \bigcup_{x \in X} x^-)$ should be a consensus of $X$.

P4. For each conjunction $(x^+, x^-) \in C(X)$, there should be $x^+ \cap x^- = \emptyset$.

P5. A consensus $x^* \in C(X)$ should minimize the sum of distances:

$$\sum_{x \in X} d_{\wedge}(x^*, x) = \min \left\{ \sum_{x \in X} d_{\wedge}(x', x) \mid x' \in \mathrm{Conj}(\mathbf{L}) \right\}$$

P6. For each symbol $z \in \mathbf{L}$ and a consensus $x^* \in C(X)$, the form of appearance of $z$ in $x^*$ depends only on its forms of appearance in conjunctions belonging to $X$.

In a consensus $(x^+, x^-) \in C(X)$, set $x^+$ (resp., set $x^-$) is called as the positive component (resp., the negative component).

By $C_{co}$ we denote the set of all consensus functions for profile of conjunctions.

Then, we analyse properties of the postulates for consensus functions. We denote:

* A consensus function $C$ satisfies a postulate $P$ for a profile $X$ written as $C(X) \vdash P$.

* A consensus function $C$ satisfies a postulate $P$ for all profiles, written as $C \vdash P$.

* A postulate $P$ is satisfied for all consensus functions $C \in C_{co}$, written as $C_{co} \vdash P$.

The first proposed theorem presented below shows that postulates P1 and P2 are the consequences of postulate P5.

**Theorem 1** A consensus function $C \in C_{co}$ which satisfies postulate P5 should also satisfies postulates P1 and P2; that is $(C \vdash P5) \Rightarrow (C \vdash P1 \wedge C \vdash P2)$.

*Proof.* We prove (a) $(C \vdash P5) \Rightarrow (C \vdash P1)$ and (b) $(C \vdash P5) \Rightarrow (C \vdash P2)$ as follow:
(a) $C \vdash P5 \Rightarrow C \vdash P1$

Let $\mathbf{X} \in \bigoplus(\text{Conj}(\mathbf{L}))$ is a profile of conjunctions, $C \in C_{\text{co}}$ is a consensus function which satisfies postulate P5. Let $(x^{*+}, x^{*-}) \in C(\mathbf{X})$ is a consensus of $\mathbf{X}$. To prove P1 is also satisfied by $C$, we have to prove

$$ \bigcap_{x \in \mathbf{X}} x^{+} \subseteq x^{*+} \qquad (2) $$

and

$$ \bigcap_{x \in \mathbf{X}} x^{-} \subseteq x^{*-} \qquad (3) $$

For the first dependence, let's assume that $\bigcap_{x \in \mathbf{X}} x^{+} \not\subseteq x^{*+}$; this means, there exists a symbol $t \in \bigcap_{x \in \mathbf{X}} x^{+}$ such that $t \notin x^{*+}$. In this case we create set $x'^* = (x'^{+}, x'^{-})$ where $x'^{+} = x^{+} \cup \{t\}$. For each $x \in \mathbf{X}$, we have

$$ \eta(x'^{*+}, x^{+}) = \frac{\text{card}(x'^{*+} \triangle x^{+})}{\text{card}(\mathbf{L})} \\ = \frac{\text{card}((x^{*+} \cup \{t\}) \triangle x^{+})}{\text{card}(\mathbf{L})} . $$

Because of $t \notin x^{*+}$ and $t \in \bigcap_{x \in \mathbf{X}} x^{+}$, we have $\forall x \in \mathbf{X}$:

$$ \text{card}((x^{*+} \cup \{t\}) \triangle x^{+}) = \text{card}(x^{*+} \triangle x^{+}) - 1 $$

So, we have $\forall x \in \mathbf{X}$:

$$ \eta(x'^{*+}, x^{+}) = \frac{\text{card}((x^{*+} \cup \{t\}) \div x^{+})}{\text{card}(\mathbf{L})} \\ = \frac{\text{card}(x^{*+} \triangle x^{+}) - 1}{\text{card}(\mathbf{L})} \\ < \frac{\text{card}(x^{*+} \triangle x^{+})}{\text{card}(\mathbf{L})} = \eta(x^{*+}, x^{+}) . $$

Finally, we have:

$$ \sum_{x \in \mathbf{X}} \eta(x'^{*+}, x^{+}) < \sum_{x \in \mathbf{X}} \eta(x^{*+}, x^{+}) \\ d_{\wedge}(x'^{*}, \mathbf{X}) = \sum_{x \in \mathbf{X}} (\frac{1}{2} \eta(x'^{*+}, x^{+}) + \frac{1}{2} \eta(x^{*-}, x^{-})) \\ < \sum_{x \in \mathbf{X}} (\frac{1}{2} \eta(x^{*+}, x^{+}) + \frac{1}{2} \eta(x^{*-}, x^{-})) \\ = d_{\wedge}(x^{*}, \mathbf{X}) $$

This is contradictory to the assumption that $((x^{*+}, x^{*-}) \in C(\mathbf{X})) \wedge (C(\mathbf{X}) \vdash P5))$. So, we have (2) is satisfied. The (3) can be proved similarly.
(b) P5 ⊢ P2 can be easily and similarly proved as the proof of P5 ⊢ P1. We omit the proof due to the limit of pages.

Another property of the postulate P5 is also stated in [4], wherein definition of distance between sets, and therefor conjunctions are defined slightly different to ours in this paper, as:

**Theorem 2** The positive and negative components of a consensus satisfying postulate P5 can be determined in an independent way; that is, conjunction $(x^{*+}, x^{*-})$ is a consensus of $\mathbf{X}$ if and only if conjunction $(x^{*+}, \emptyset)$ is a consensus of profile $\mathbf{X}' = \{(x_i^+, \emptyset) : i = 1, 2, \dots, n\}$, and conjunction $(\emptyset, x^{*-})$ is a consensus of profile $\mathbf{X}'' = \{(\emptyset, x_i^-) : i = 1, 2, \dots, n\}$ [4].

Theorem 2 is still valid in our paper's context. However, this theorem does not show how to construct a consensus of a conflict profile. Actually, the consensus can be determined based on the following theorem.

**Theorem 3** Let $\mathbf{X} = \{x_i, i = 1, 2, \dots, n\}$ is a profile of conjunctions, $\mathbf{X} \in \prod(\text{Conj}(\mathbf{L}))$. We denote

$\bullet \mathbf{Z}^+ = \bigcup_{x \in \mathbf{X}} x^+$.

$\bullet \mathbf{Z}^- = \bigcup_{x \in \mathbf{X}} x^-$.

$\bullet f^+(z) = \text{card}\{x_i \in \mathbf{X} \mid x_i^+ \ni z\}$.

$\bullet f^-(z) = \text{card}\{x_i \in \mathbf{X} \mid x_i^- \ni z\}$.

Assume that $C(\mathbf{X})$ satisfies postulate P5. In this case, $x^* = (x^{*+}, x^{*-})$ is a consensus of $\mathbf{X}$ if and only if (a) $x^{*+} = \{z \in \mathbf{Z}^+ | f^+(z) \ge \frac{n}{2}\}$ and (b) $x^{-} = \{z \in \mathbf{Z}^- | f^-(z) \ge \frac{n}{2}\}$.

*Proof.* As Theorem 2, we can formulate a consensus $x^* = (x^{*+}, x^{*-})$ satisfying postulate P5 by independently formulating $x^{*+}$ and $x^{*-}$ for $\mathbf{X}^+ = \{x_i^+, i = 1, 2, \dots, n\}$ and $\mathbf{X}^- = \{x_i^-, i = 1, 2, \dots, n\}$. We have to prove that (a) $x^{*+} = \{z \in \mathbf{Z}^+ | f^+(z) \ge \frac{n}{2}\}$. The proof for (b) is similar.

First, as Theorem 1, $x^{*+}$ contains only literals belonging to $\mathbf{Z}^+$. We will prove that, for any conjunction $x \in \text{Conj}(\mathbf{L})$, we have:

(i) If $z \in \mathbf{Z}^+$ such that $f^+(z) \ge \frac{n}{2}$ and $z \notin x^+$ then $d_\wedge((x^+, x^-), \mathbf{X}^+) \le d_\wedge((x^+ \cup \{z\}, x^-), \mathbf{X}^+)$, and

(ii) If $z \in \mathbf{Z}^+$ such that $f^+(z) < \frac{n}{2}$ and $z \notin x^+$ then $d_\wedge((x^+, x^-), \mathbf{X}^+) > d_\wedge((x^+ \cup \{z\}, x^-), \mathbf{X}^+)$.

We have:

$$d_\wedge((x^+ \cup \{z\}, x^-), \mathbf{X}) = \sum_{y \in \mathbf{X}} \left( \frac{1}{2} \cdot \frac{\text{card}((x^+ \cup \{z\}) \triangle y^+)}{\text{card}(\mathbf{L})} + \frac{1}{2} \cdot \frac{\text{card}(x^- \triangle y^-)}{\text{card}(\mathbf{L})} \right)$$
and

$$ \frac{\mathrm{card}((x^+ \cup \{z\}) \triangle y^+)}{\mathrm{card}(\mathbf{L})} = \begin{cases} \frac{\mathrm{card}(x^+ \triangle y^+) - 1}{\mathrm{card}(\mathbf{L})} & \text{if } y^+ \ni z, \\ \frac{\mathrm{card}(x^+ \triangle y^+) + 1}{\mathrm{card}(\mathbf{L})} & \text{if } y^+ \niiid z. \end{cases} $$

Let $\mathbf{X}_{\bar{z}} := \{x \in \mathbf{X} | x^+ \ni z\}$ and $\mathbf{X}_{\bar{z}} := \{x \in \mathbf{X} | x^+ \niiid z\}$. We have, $\mathrm{card}(\mathbf{X}_z) = f^+(z)$ and $\mathrm{card}(\mathbf{X}_{\bar{z}}) = n - f^+(z)$. So:

$$ \begin{aligned} \sum_{y \in \mathbf{X}} \frac{\mathrm{card}((x^+ \cup \{z\}) \triangle y^+)}{\mathrm{card}(\mathbf{L})} &= \sum_{y \in \mathbf{X}_{\bar{z}}} \frac{\mathrm{card}((x^+ \cup \{z\}) \triangle y^+)}{\mathrm{card}(\mathbf{L})} + \sum_{y \in \mathbf{X}_{\bar{z}}} \frac{\mathrm{card}((x^+ \cup \{z\}) \triangle y^+)}{\mathrm{card}(\mathbf{L})} \\ &= \sum_{y \in \mathbf{X}_{\bar{z}}} \frac{\mathrm{card}(x^+ \triangle y^+) - 1}{\mathrm{card}(\mathbf{L})} + \sum_{y \in \mathbf{X}_{\bar{z}}} \frac{\mathrm{card}(x^+ \triangle y^+) + 1}{\mathrm{card}(\mathbf{L})} \\ &= \sum_{y \in \mathbf{X}} \frac{\mathrm{card}(x^+ \triangle y^+)}{\mathrm{card}(\mathbf{L})} + \frac{-f^+(z) + n - f^+(z)}{\mathrm{card}(\mathbf{L})} \\ &= \sum_{y \in \mathbf{X}} \frac{\mathrm{card}(x^+ \triangle y^+)}{\mathrm{card}(\mathbf{L})} + \frac{n - 2.f^+(z)}{\mathrm{card}(\mathbf{L})}. \end{aligned} $$

Finally, we have

$$ \begin{aligned} d_{\wedge}((x^+ \cup \{z\}, x^-), \mathbf{X}) &= \sum_{y \in \mathbf{X}} \left( \frac{1}{2} \cdot \frac{\mathrm{card}((x^+ \cup \{z\}) \triangle y^+)}{\mathrm{card}(\mathbf{L})} + \frac{1}{2} \cdot \frac{\mathrm{card}(x^- \triangle y^-)}{\mathrm{card}(\mathbf{L})} \right) \\ &= \sum_{y \in \mathbf{X}} \left( \frac{1}{2} \cdot \left( \frac{\mathrm{card}(x^+ \triangle y^+)}{\mathrm{card}(\mathbf{L})} + \frac{n - 2.f^+(z)}{\mathrm{card}(\mathbf{L})} \right) + \frac{1}{2} \cdot \frac{\mathrm{card}(x^- \triangle y^-)}{\mathrm{card}(\mathbf{L})} \right) \\ &= d_{\wedge}(x, \mathbf{X}) + \frac{1}{2} \cdot \frac{n - 2.f^+(z)}{\mathrm{card}(\mathbf{L})} \end{aligned} $$

Therefore, when $n - 2.f^+(z) \le 0$, or $f^+(z) \le \frac{n}{2}$, adding $z$ to $x^+$ will not make increase sum of distances of $x$ to $\mathbf{X}$. Otherwise, when $f^+(z) < \frac{n}{2}$, adding $z$ to $x^+$ will make increase sum of distances of $x$ to $\mathbf{X}$. Finally, (i) and (ii) are satisfied.

Back to proving (a), we can see that, start at the set $\{z \in \mathbf{Z}^+ | f^+(z) \ge \frac{n}{2}\}$, we can not remove any element(s) from this set, and can not add any other element(s) from $\mathbf{Z}^+$ in process of determining the positive component of the consensus. Hence, this is the optimal positive component of consensus! ((a) is satisfied).

# 4 Proposed algorithm for determining consensus

## 4.1 Algorithm

Based on our proposed theorems in the previous section, we introduce an algorithm for determining the consensus $x^* = (x^{*+}, x^{*-})$ for profile $\mathbf{X} \in \prod((\mathrm{Conj}(\mathbf{L})))$ as **Algorithm 1**.
**Input:** Profile X ∈ Π(Conj(L)), X = {(xᵢ⁺, xᵢ⁻), i = 1, 2, ..., n},
xᵢ⁺ ∩ xᵢ⁻ = ∅ ∀i = 1, 2, ..., n.

**Output:** Consensus x* ∈ Conj(L) satisfies one or more postulates in {P4, P1, P2, P3, P5}.

begin

$$
\mathbf{Z}^{+} := \bigcup_{x \in \mathbf{X}} x^{+}; \quad \mathbf{Z}^{-} := \bigcup_{x \in \mathbf{X}} x^{-};
$$

foreach $z \in \mathbb{Z}^+$ do

$$
\lfloor f^{+}(z) := \mathrm{card}\{x \in \mathbf{X} \mid x^{+} \ni z\};
$$

foreach $z \in \mathbb{Z}^-$ do

$$
\lfloor f^{-}(z) := \mathrm{card}\{x \in \mathbf{X} \mid x^{-} \ni z\};
$$

(a)
$$x^+ := \{z \in \mathbb{Z}^+ | f^+(z) \ge \frac{n}{2}\};$$

$$
x^{-} := \{z \in \mathbb{Z}^{-} | f^{-}(z) \geq \frac{n}{2}\};
$$

if $(x^+ \cup x^- \neq \emptyset)$ then

(b) foreach $z \in x^+ \cap x^-$ do

if $d_{\Lambda}((x^+ \setminus \{z\}, x^-), X) < d_{\Lambda}((x^+, x^- \setminus \{z\}), X)$ then

$$
x^+ := x^+ \setminus \{z\};
$$

else

$$
\lfloor x^{-} := x^{-} \setminus \{z\};
$$

else

(c) if $(\mathbb{Z}^+ \cap \mathbb{Z}^- = \emptyset)$ then
$$ | x^* := (\mathbb{Z}^+, \mathbb{Z}^-); $$

else

(d) $x^* := x_1;$
for $i := 2$ to $n$ do

if $d_{\Lambda}(x^*, X) > d_{\Lambda}(x, X)$ then

$$
\lfloor x^* := x_i
$$

**Algorithm 1:** Determine consensus for profile of conjunctions

As shown in **Algorithm 1**, we start by finding the consensus satisfying
postulate P5 (step (a)). After that:

(i) If both positive and negative of the P5-consensus are empty, the algorithm will find the consensus satisfying postulate P3 (step (c)) if X is consistent. In case of X is inconsistent, as step (d), the algorithm will choose from X an element which has minimum sum of distances to others elements in X. The consensus in this case satisfies postulate P4 (because $x_i^+ \cap x_i^- = \emptyset$, $\forall i = 1, 2, ..., n$).

(ii) If in step (a), the positive or negative component is not empty, we refine them for satisfying postulate P4, and also ensure that the sum of distances to elements in X is minimal.

Beside that, in all cases of the two above branches (i) and (ii), we construct $x^{*+}$ (respectively $x^{*-}$) from $\mathbf{Z}^{+}$ (respectively $\mathbf{Z}^{-}$). Therefore, the consensus
always satisfies postulate P2. The consensus also satisfies postulate P1 because it construct from consensus which satisfies postulate P5, after that, elements which are removed because of their occurrences are smaller than $\frac{n}{2}$.

The computational complexity of **Algorithm 1** is $O(n.m^2)$, where *n* is the number of elements in X, $m = \max\{card(\bigcup_{x \in X} x^+), card(\bigcup_{x \in X} x^-)\}$.

## 4.2 Example

Let's assume that, to specify the property *hasSpouse* in an ontology, an agent can use a conjunction in *Conj(L)* where *L* = {*t*₁, *t*₂, *t*₃, *t*₄}. These symbols represent the following facts:

* *t*₁: *hasSpouse* is symmetric.

* *t*₂: *hasSpouse* is reflexive.

* *t*₃: *hasSpouse* is functional.

* *t*₄: *hasSpouse* is a subproperty of *hasRelationshipWith*.

6 agents *a*₁, *a*₂, ..., *a*₆ express their opinions as **Table 1**:

<table><caption>**Table 1.** Knowledge states for example</caption><thead><tr><th colspan="2">Agent Knowledge state</th></tr></thead><tbody><tr><td>a<sub>1</sub></td><td>t<sub>1</sub> ∧ ¬t<sub>2</sub> ∧ t<sub>3</sub> ∧ t<sub>4</sub></td></tr><tr><td>a<sub>2</sub></td><td>t<sub>1</sub> ∧ ¬t<sub>3</sub> ∧ ¬t<sub>4</sub></td></tr><tr><td>a<sub>3</sub></td><td>t<sub>1</sub> ∧ ¬t<sub>3</sub></td></tr><tr><td>a<sub>4</sub></td><td>t<sub>1</sub> ∧ ¬t<sub>3</sub> ∧ ¬t<sub>4</sub></td></tr><tr><td>a<sub>5</sub></td><td>¬t<sub>1</sub> ∧ t<sub>3</sub> ∧ ¬t<sub>4</sub></td></tr><tr><td>a<sub>6</sub></td><td>t<sub>3</sub></td></tr></tbody></table>

We will use **Algorithm 1** to determine consensus from opinions of the above 6 agents. Firstly, we formalize the profile X:

$$X = \{ (\{t_1, t_3, t_4\}, \{t_2\}), 2 * (\{t_1\}, \{t_3, t_4\}), (\{t_1\}, \{t_3\}), (\{t_3\}, \{t_1\}), (\{t_3\}, \emptyset) \}.$$

After step (a) of the algorithm, we have $x^{*+} = \{t_1, t_3\}$ and $x^{*-} = \{t_3, t_4\}$.

Because $x^{*+} \cup x^{*-} \neq \emptyset$, we have to find a way to remove common literal(s) of the two components (as step (b)): With $x^{*+} \cap x^{*-} = \{t_3\}$, we compare two sums of distances $d_{\wedge}((\{t_1\}, \{t_3, t_4\}), X)$ and $d_{\wedge}((\{t_1, t_3\}, \{t_4\}), X)$. We easily have

$$\bullet d_{\wedge}((\{t_1\}, \{t_3, t_4\}), X) = \frac{15}{8},$$
$$ \bullet d_{\wedge}((\{t_1, t_3\}, \{t_4\}), X) = \frac{13}{8}. $$

Hence, consensus of X is $(\{t_1, t_3\}, \{t_4\})$, or $t_1 \wedge t_3 \wedge \neg t_4$.

# 5 Conclusion

In this paper, we formalised a method to determine the consensus of knowledge states presented as conjunctions of literals. We defined a distance between two conjunctions, proved relevant theorems for dependencies of postulates. Based on these theorems, we proposed a novel algorithm for determining the consensus for a profile of conjunctions.

As future work, we would like to analyse opportunities of using the more complex structure for presenting knowledge state than the conjunction or dis-junction of literals. We also would like to apply the **Algorithm 1** to determining consensus axioms in process of the ontological engineering in a wiki-based environment [5, 6] such as collaborative ontology development or ontological annotation.

**Acknowledgement** This work was partly supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (NRF-2014R1A2A2A05007154).

# References

1. Ferilli, S., Biba, M., Di Mauro, N., Basile, T.M.A., Esposito, F.: Plugging Taxonomic Similarity in First-Order Logic Horn Clauses Comparison. AI* IA 2009: Emergent Perspectives in Artificial Intelligence 5883, 131–140 (2009)

2. Ferilli, S., Di Mauro, N., Biba, M., Esposito, F.: Similarity-Guided Clause Generalization. In: AI* IA 2007: Artificial Intelligence and Human-Oriented Computing, pp. 278–289. Springer (2007)

3. Huang, Z., van Harmelen, F.: Using semantic distances for reasoning with inconsistent ontologies. In: The Semantic Web - ISWC 2008. pp. 178–194. Springer (2008)

4. Nguyen, N.T.: Advanced Methods for Inconsistent Knowledge Management (Advanced Information and Knowledge Processing). Springer (2007), http://dx.doi.org/10.1007/978-1-84628-889-0

5. Tudorache, T., Noy, N.F., Tu, S., Musen, M.A.: Supporting Collaborative Ontology Development in Protege, vol. 5318. Springer (2008), http://www.springerlink.com/index/uu1453660t047775.pdf

6. Tudorache, T., Nyulas, C., Noy, N.F., Musen, M.A.: WebProtege: A collaborative ontology editor and knowledge acquisition tool for the web. Semantic Web 4(1), 89–99 (2013)

7. Van Nguyen, T., Huu Hoang, H.: A Consensus-Based Method for Solving Concept-Level Conflict in Ontology Integration. In: ICCCI 2014, LNAI 8733. pp. 414–423. Springer (2014)