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

SAT-based Algorithms for Inconsistency Measurement

[go to overview]
Anna Gessler

Inconsistency measurement is the study of quantitatively assessing the severity of inconsistency in a given knowledge base. This is useful for comparing different inconsistent sets and for determining which parts of a knowledge base are the cause of the inconsistency. Many inconsistency measures have been proposed, but relatively few works have studied the algorithmic complexity and practical feasibility of inconsistency measures. Several inconsistency measures can be reduced to the satisfiability problem of propositional logic (SAT), for which many high-performance solvers have been developed already. My master’s thesis concerns itself with the development of SAT encodings for a number of inconsistency measures in order to use the existing solvers. The resulting algorithms were implemented and tested on datasets of different sizes and complexities in comparison to baseline brute-force implementations. In this talk, I will present an overview of inconsistency measurement and SAT encodings, explain the general idea behind the algorithms that were developed, and discuss the results of the evaluation.

18.01.21 - 10:15
via Big Blue Button