An algorithmic study of kernel contraction in EL

Kernel contraction is an interesting problem that can be considered a step towards belief revision. Kernels were introduced as a tool to determine why a given belief is accepted by the knowledge base. The aim of using kernels is to invalidate the reasons why that given belief is accepted, and hence rejecting that belief. We use Description Logic EL for two reasons: it is used in some large knowledge base applications, and it has a polynomial-time reasoning algorithm. In this study we introduce an algorithm that performs kernel contraction by reduction to the network-flow problem. We evaluate the rationality of the algorithm by applying postulates that govern kernel contraction. We also explain two heuristics: localization and specificity, that can be used to arrive at more reasonable and common-sense solutions. We will also be focusing on the complexity of the algorithms as an indicator of their feasibility.