On the Complexity of Measuring Disagreement with Interpolants

Main Article Content

Viorica Sofronie-Stokkermans
Matthias Thimm

Abstract

We consider the problem of quantitatively assessing the conflict between knowledge bases in knowledge merging scenarios. Using the notion of Craig interpolation we define a series of disagreement measures and analyse their compliance with properties proposed in previous work by Potyka. We then focus on a study of computational complexity of various problems that occur when measuring disagreement. In particular, we shed some new lights on the complexity of dealing with interpolants in propositional logic, such as deciding whether a given formula is an interpolant and whether it is a (semantically) strongest or weakest interpolant. We also consider functional problems (determining strongest/weakest interpolants) and counting problems.

Article Details

Section
Articles