The AGM paradigm is the most used framework in Belief Revision. Among its various operations, a revision occurs when a rational agent receives a new information inconsistent with its epistemic state and has to revise it in order to accomodate the new belief in a consistent way. However, this new information may come as a set of beliefs (instead of a single one), a problem known as Multiple Revision. There may be two approaches to this operation: to accomodate the whole new set of beliefs or to incorporate only a subset of it. In the second case, the agent has to be able to determine which part of the set will be added to its state. In this project, we are particularly interested in this last case. In addition to that, the agent may deal with di erent kinds of belief. Thus, the purpose of this research plan is to de ne how to operate a multiple revision and, more speci cally, how to do this in non-classical logics.
The problem of Knowledge Representation is one of the central areas in Arti cial
Intelligence. With the advancement of technology, it became clear that we need
to enable computers to e ciently represent information regarding a domain in
order to be able to proceed with other tasks. In this context, ontologies came
out as a valuable option. Among the formalisms that were coined to represent
ontologies formally we have Description Logics (DLs)[
However, according to Gardenfors[
In the AGM paradigm, given a set of beliefs, there are three possible changes in relation to a new belief: expansion, contraction and revision. Expansion occurs when the base simply absorbs the information without loss. A contraction consists in retracting beliefs from the base until the speci ed information is not derivable from it anymore. Finally, revision happens when the new belief is added in a consistent way, possibly demanding a repair in order to eliminate inconsistency. In this project, we are particularly interested in this last operation.
In the original framework, the new belief is assumed to be represented by a single formula. Nevertheless, there are situations in which the information by which we are going to revise a set of beliefs comes in block. This generalized operation is called Multiple Belief Revision. It is not the same as applying revision in an iterated way, since in Multiple Revision it is assumed that there is no preference over the input sentences, which means that all of them have equal priority and should be processed at the same time.
However, when you consider the described scenario, there may be two ways to achieve the goal. On the one hand the intention may be to absorb the new sentences completely, which is called package. On the other hand, it may be enough to incorporate a subset of the new sentences, which is called choice. In this research project we are going to explore this last option in more detail.
From [
Combining this and the need to change ontologies, we investigate in this work how to apply Belief Revision in a multiple context, especially for Description Logics, with a particular attention to OWL ontologies.
This proposal is structured as follows. In the next section, we provide a background in Belief Revision and Ontologies. In Section 3, we detail the goals, objectives and methodology of this proposal. Finally, in Section 4 we organize the tasks according to the remaining semesters.
In the AGM paradigm, the revision operation is de ned from contraction via
the Levi Identity [
Besides establishing properties which the operations should obbey (known as
postulates), constructions were elaborated to give means of executing the desired
procedures. Among them, we highlight two: Partial Meet[
Within the Belief Change area, the operations, properties and constructions were initially de ned thinking of the initial beliefs as being a belief set, i.e., a set of beliefs closed under logical consequence. However, since sets conceived this way are usually in nite, there are some disadvantages with this approach, especially for computational purposes. Considering this problem, instead of working with belief sets, some authors began to work also with belief bases, which are knowledge bases not necessarily closed. For practical purposes in change operations it is much more convenient and is of particular interest for us. 2.2
In [
Now, the package revision operation can be de ned via a generalized version
of the Levi Identity using package contraction: K p A = (K p :A) + A, where
:A = f: : 2 Ag. By this approach, the properties of a package revision
operation become dictated by the ones of the package contraction operation.
Nevertheless, considering that some logics lack negation, it would be interesting
to study the de nition of revision operations in a direct way, i.e., without using
contraction as an intermediate step. This is one of the main goals of the work
developed in [
Still about the generalized Levi Identity, we have in [
In multiple operations, one of the questions that emerge is whether it is
possible to reduce them to operations by singletons. For the revision case, the
following result for nite sets was obtained in [
In [
In [
In [
With these tools in mind, it is possible to construct a model for selective revision. Let K be a belief set, a partial meet revision for K and f a transformation function. The selective revision , based on and f , is the operation such that for all sentences , K = K f ( ).
However, it is not suitable neither for belief bases (given that it depends on a postulate of closure) nor for Description Logics (once some properties of the transformation function apply negation, disjunction and conjunction of sentences and DLs are not closed under any of these operators). 1 In the original article, Package Revision is called Prioritized Change, in the sense that all the sentences from A should be present in the new belief base. Then, for the constructions, the names originally given were Prioritized Multiple Kernel Revision and Prioritized Multiple Partial Meet Revision. 2.4
An ontology provides a description of individuals, their aspects (attributes) and restrictions, how they can be categorized (classes) and how they interact with each other (relations), in relation to a given domain.
Ontologies can be used in a growing range of applications, such as medical diagnosis, biological and biomedical research. In Arti cial Intelligence, we can see ontologies in the modeling of Natural Languages and also in Knowledge Representation, being useful for robotic path planning.
As a main language used for describing ontologies, we can cite OWL (Web Ontology Language), part of the standards de ned by the World Wide Web Consortium (W3C) to represent ontologies and organize data2.
The theoretical basis both for OWL and for the pro les associated to it are formed by Description Logics (DLs), which are structured subsets of First Order Logic and have a well de ned formal semantics.
Due to the dynamics of knowledge, it is important to know how to modi
cate an ontology when there is a need for change (a new information, changes
dictated by an ontology engineer, etc). As ontologies are usually huge and
intricate structures, this problem is of considerable importance, what gives rise
to the ontology change issue[
Our main goal with this project is to propose postulates, constructions, theorems and algorithms that make it possible to perform operations of Multiple Belief Revision, especially in Description Logics. We detail below the speci c objectives, pointing, when relevant, what has already been done or is in progress.
In order to develop this research plan, we are going to apply a formal mathematical analysis. To accomplish this, our bases will be previous works on Multiple Contraction, Multiple Revision, Merging and on the problems of the Levi identity in non-classical logics, aiming to analyze and extract mathematical formalisms already developed in the area to conduct our steps. 3.1
Before going deeper in the project, we searched for all the works that had already been developed in the area of Multiple Revision. Along the process, it came to us the need to systematize the theories developed, organizing and comparing them.
Then, we have started to produce a survey on the topic, using as main
references the works in [
https://www.w3.org/TR/owl2-overview/ 3.2
Firstly, we want to identify and establish all the limitations of the existing theory for Multiple Belief Revision when it comes do DLs, more speci cally through the choice approach. After that, we have to de ne all the postulates needed to make feasible the compatibility between Multiple Revision and DLs.
One of the rst steps is to analyze and compare the aspects studied in works
such as [
Using Partial Meet and Kernel approaches, it will be possible to create constructions capable of executing (Multiple) Choice Belief Revision in DLs. With these resources in hand, we will be able to propose and demonstrate representation theorems that prove the validity of the connection between the postulates de ned and the constructions created.
Regarding this topic, after studying the limitations, it was possible to identify
the incompatibilities presented in [
A valuable resource can be obtained analyzing and comparing the properties
and constructions used in the development of the theories about Multiple
Belief Contraction[
When we compare the choice approach of Multiple Revision and the operation of Selective Revision it is possible to identify some similarities. Although this last one has been developed to singleton inputs, it shares with choice the property of selecting a part of the incoming information to incorporate. It could be a possible way to perform multiple choice revision. Then, we aim to explore the Selective Revision operation in order to study the possibility of extending it to the multiple case and, more speci cally, to Description Logics. 3.4
Regarding the practical aspects of the theory to be developed, we plan to develop algorithms that correspond to the constructions studied and proposed, in order to pave the way for implementation of the theory developed. In addition, it will be possible to compare, in this context, the Partial Meet and Kernel approaches in relation to the computational complexity of the operations.
In order to get closer to what has already been developed in the eld, we
intend to analyze the algorithms for singleton Belief Revision[
In relation to Package Revision, following the approach presented in [
Due to the non-prioritized nature of Multiple Choice Revision, i.e., the possibility of partial acceptance in relation to the input beliefs, there may be a correlation between this operation and the merging operators.
Merging is also a type of non-prioritized change that happens when you need to harmonize multiple sources of information. Depending on the entrenchment of the beliefs you already have and on the integrity constraints required to the operation, the input knowledge base may be partly or totally discarded, although there is no precedence established to the di erent sources, i.e., previous and new beliefs have symmetric roles during the process.
Therefore, we intend to study it more deeply to understand what are the
di erences between the operations and also the similarities, especially if some
properties can be shared. For more details about the operation, its properties
and constructions, see [
So far, the student has already accomplished the requisites from the post-graduate program: the mandatory courses and the approval in the qualifying exam. Our research plan is scheduled as follows:
{ Survey of the eld; { Proposal of the postulates for Multiple Choice Revision; { Development of Partial Meet and Kernel constructions for Multiple Choice
Revision; { Proposal and proof of representation theorems between the constructions and the postulates;
{ Development and proof of the Partial Meet and Kernel algorithms for Choice
Revision; { Analysis of the complexity of the algorithms developed; { Implementation and testing of the algorithms developed; { Identi cation of the limitations of Selective Revision for Description Logics; { Analysis of the Selective Revision operation in order to extend it to the multiple case;