02117nas a2200145   4500008004100000245007000041210006900111300001600180490000700196520167700203100001201880700001501892700002001907856004401927       2011                        eng d00aComputing Inconsistency Measure based on Paraconsistent Semantics0 aComputing Inconsistency Measure based on Paraconsistent Semantic  a1257–12810 v213 a<p class="rtejustify">Measuring inconsistency in knowledge bases has been recognized as an important problem in several research areas. Many methods have been proposed to solve this problem and a main class of them is based on some kind of paraconsistent semantics. However, existing methods suffer from two limitations: 1) They are mostly restricted to propositional knowledge bases; 2) Very few of them discuss computational aspects of computing inconsistency measures. In this paper, we try to solve these two limitations by exploring algorithms for computing an inconsistency measure of first-order knowledge bases. After introducing a four-valued semantics for first-order logic, we define an inconsistency measure of a first-order knowledge base, which is a sequence of inconsistency degrees. We then propose a precise algorithm to compute our inconsistency measure. We show that this algorithm reduces the computation of the inconsistency measure to classical satisfiability checking. This is done by introducing a new semantics, named S[n]-4 semantics, which can be calculated by invoking a classical SAT solver. Moreover, we show that this auxiliary semantics also gives a direct way to compute upper and lower bounds of inconsistency degrees. That is, it can be easily revised to compute approximating inconsistency measures. The approximating inconsistency measures converge to the precise values if enough resources are available. Finally, by some nice properties of the S[n]-4 semantics, we show that some upper and lower bounds can be computed in P-time, which says that the problem of computing these approximating inconsistency measures is tractable.</p>
1 aMa, Yue1 aQi, Guilin1 aHitzler, Pascal  uhttp://dx.doi.org/10.1093/logcom/exq053