EUVIMEDEUVIMED entdecken
Crossref

On the Complexity of Measuring Disagreement with Interpolants

Jandson Santos Ribeiro Santos, Viorica Sofronie-Stokkermans, Matthias Thimm

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →