On the Complexity of Measuring Disagreement with Interpolants
Journal of Artificial Intelligence Research · 19.11.2026 · 87
DOI: 10.1613/jair.1.22972 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 19.11.2026. Verfasst von Jandson Santos Ribeiro Santos und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Santos, J. S. R., Sofronie-Stokkermans, V., & Thimm, M. (2026). On the Complexity of Measuring Disagreement with Interpolants. Journal of Artificial Intelligence Research, 87. https://doi.org/10.1613/jair.1.22972
Vancouver
Santos JSR, Sofronie-Stokkermans V, Thimm M. On the Complexity of Measuring Disagreement with Interpolants. Journal of Artificial Intelligence Research. 2026;87. doi:10.1613/jair.1.22972
BibTeX
@article{Santos2026,
author = {Santos, Jandson Santos Ribeiro and Sofronie-Stokkermans, Viorica and Thimm, Matthias},
title = {On the Complexity of Measuring Disagreement with Interpolants},
journal = {Journal of Artificial Intelligence Research},
year = {2026},
volume = {87},
doi = {10.1613/jair.1.22972}
}
EUVIMED