Institute for Web Science and Technologies · Universität Koblenz - Landau
Institute WeST

Kernel Contraction and Epistemic Choices

[go to master theses]

Open Master Thesis - Contact a supervisor for more details!

Rational agents should autonomously maintain their knowledge base up-to-date. Information is not static, and over time they might become obsolete. The area of Belief Change studies how an autonomous agent should rationally modify its knowledge when facing a piece of information. The choice an agent makes when relinquishing a piece of information is rationalised by an epistemic preference relation on an agent’s beliefs that reveals a reliability preference between its beliefs. An agent then, removes only the least entrenched information, keeping the most significant ones intact. The foremost construction of belief contraction, known as Kernel contraction [2], is produced by the following recipe. Given a knowledge base K and an undesirable formula phi to be relinquished: (1) find all the minimal subsets of K that entail phi, known as kernels; (2) for each of the kernels, remove at least one formula of it. Some partial implementations of Kernel contraction have been used to perform removal of inconsistencies in ontologies, see [4, 3]. The issue with these approaches is that they remove inconsistencies in a purely heuristic fashion to avoid computing all the kernels. Although this strategy reduces computational time, it disregards the epistemic preferences of the agent.

In this thesis, you will implement a version of the Kernel Contraction for belief base. The idea is to use the current heuristics to avoid calculating all the kernels, and use some specific epistemic preference relation, such as the Dalal distance [1], to give a complete implementation of Kernel contraction. A complete evaluation of the implemented methods will be carried out.


[1] Mukesh Dalal. “Investigations into a Theory of Knowledge Base Revision”. In: Proceedings of the 7th National Conference on Artificial Intelligence, 1988. Ed. by Howard E. Shrobe, Tom M. Mitchell, and Reid G. Smith. AAAI Press / The MIT Press, 1988, pp. 475–479.

[2] Sven Ove Hansson. “Kernel contraction”. In: Journal of Symbolic Logic (1994), pp. 845–859.

[3] Ulrich Junker. “Quickxplain: Conflict detection for arbitrary constraint propagation algorithms”. In: IJCAI’01 Workshop on Modelling and Solving problems with constraints. Vol. 4. 2001.

[4] Aditya Kalyanpur et al. “Finding All Justifications of OWL DL Entailments”. In: The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC, 2007. Vol. 4825. Lecture Notes in Computer Science. Springer, 2007, pp. 267–280.


  • Scientific Employee
  • B 110
  • +49 261 287-2756