Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases

Research output: Contribution to journalArticle (Academic Journal)peer-review

22 Citations (Scopus)
254 Downloads (Pure)

Abstract

There is extensive theoretical work on measures of inconsistency for arbitrary formulae in knowledge bases. Many of these are defined in terms of the set of minimal inconsistent subsets (MISes) of the base. However, few have been implemented or experimentally evaluated to support their viability, since computing all MISes is intractable in the worst case. Fortunately, recent work on a related problem of minimal unsatisfiable sets of clauses (MUSes) offers a viable solution in many cases. In this paper, we begin by drawing connections between MISes and MUSes through algorithms based on a MUS generalization approach and a new optimized MUS transformation approach to finding MISes. We implement these algorithms, along with a selection of existing measures for flat and stratified knowledge bases, in a tool called mimus. We then carry out an extensive experimental evaluation of mimus using randomly generated arbitrary knowledge bases. We conclude that these measures are viable for many large and complex random instances. Moreover, they represent a practical and intuitive tool for inconsistency handling.
Original languageEnglish
Pages (from-to)1659-1693
Number of pages35
JournalInternational Journal of Approximate Reasoning
Volume55
Issue number8
Early online date27 Jun 2014
DOIs
Publication statusPublished - 1 Nov 2014

Keywords

  • Inconsistency measures
  • Minimal inconsistent subsets
  • Minimal unsatisfiable subformulae
  • SAT
  • Random SAT

Cite this