Comparison of SAT-based and ASP-based Algorithms for Inconsistency Measurement
This work addresses inconsistency measurement in knowledge bases, which is important for AI and logic-based systems, but it is incremental as it compares existing algorithmic approaches without introducing new methods.
The paper tackled the problem of determining inconsistency degrees in propositional knowledge bases by comparing SAT-based and ASP-based algorithms for six inconsistency measures, finding that ASP-based approaches outperformed SAT-based ones in runtime across all measures.
We present algorithms based on satisfiability problem (SAT) solving, as well as answer set programming (ASP), for solving the problem of determining inconsistency degrees in propositional knowledge bases. We consider six different inconsistency measures whose respective decision problems lie on the first level of the polynomial hierarchy. Namely, these are the contension inconsistency measure, the forgetting-based inconsistency measure, the hitting set inconsistency measure, the max-distance inconsistency measure, the sum-distance inconsistency measure, and the hit-distance inconsistency measure. In an extensive experimental analysis, we compare the SAT-based and ASP-based approaches with each other, as well as with a set of naive baseline algorithms. Our results demonstrate that overall, both the SAT-based and the ASP-based approaches clearly outperform the naive baseline methods in terms of runtime. The results further show that the proposed ASP-based approaches perform superior to the SAT-based ones with regard to all six inconsistency measures considered in this work. Moreover, we conduct additional experiments to explain the aforementioned results in greater detail.