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

"An Algorithm for the Contension Inconsistency Measure using Reductions to Answer Set Programming" won the Best Student Paper Award at the SUM 2020 conference

[go to overview]

The paper “An Algorithm for the Contension Inconsistency Measure using Reductions to Answer Set Programming” by Isabelle Kuhlmann and Matthias Thimm won the Best Student Paper Award at the 14th International Conference on Scalable Uncertainty Management (SUM) 2020.

Paper summary:

When data is collected from different sources, conflicts (inconsistencies) cannot be avoided. The field of inconsistency measurement offers a quantitative-analytical perspective on this issue. An inconsistency measure maps a knowledge base to a non-negative number. A higher inconsistency value indicates a more severe inconsistency than a lower value. This allows the identification of problems and the comparison of alternative formalizations. Although a lot of research is concerned with the development of new inconsistency measures or the comparison of existing measures, the development of efficient algorithms receives little attention. Nevertheless, the problem of calculating inconsistency values is a difficult one from the perspective of complexity theory. Consequently, it is crucial for the application of inconsistency measurements that practically feasible algorithms are developed.

In this paper, an algorithm is presented which determines the so-called contension inconsistency measure by means of reductions to answer set programming.More precisely, the decision problem whether a given value represents an upper bound for the contension inconsistency value with respect to a given knowledge base is encoded as an answer set program. Since the set of possible inconsistency values is known and furthermore consists of natural numbers, the exact contension inconsistency value can be determined by binary search.In an experimental evaluation we showed that the presented algorithm clearly surpasses the state of the art.

Link to the paper:

SUM 2020 conference:


Contact for inquiries: