| Computational Complexity and Anytime Algorithm for Inconsistency Measurement |
| Received:July 15,2009 Revised:February 19,2010 Download PDF |
| Yue Ma,Guilin Qi,Guohui Xiao,Pascal Hitzler,Zuoquan Lin. Computational Complexity and Anytime Algorithm for Inconsistency Measurement. International Journal of Software and Informatics, 2010,4(1):3~21 |
| Hits: 467 |
| Download times: 170 |
| Author | Institution | | Yue Ma | Institute LIPN, Universit?e Paris 13-CNRS, France | | Guilin Qi | School of Computer Science and Engineering, Southeast University, Nanjing 210096, China | | Guohui Xiao | Department of Information Science, Peking University, Beijing 100871, China; Institut f?ur Informationssysteme, Technische Universit?at Wien, Austria | | Pascal Hitzler | Kno.e.sis Center, Wright State University, Dayton, OH, USA | | Zuoquan Lin | Department of Information Science, Peking University, Beijing 100871, China |
|
| Fund:This work is sponsored by the the Quaero Programme, funded by OSEO, French State agency for
innovation (for Yue Ma). Guilin Qi is partially supported by Excellent Youth Scholars Program of
Southeast University under Grant No.4009001011 and National Science Foundation of China under
Grant No.60903010. Zuoquan Lin and Guohui Xiao are supported by the National Natural Science
Foundation of China under Grant No.60973003. |
|
| Abstract:Measuring inconsistency degrees of inconsistent knowledge bases is an important
problem as it provides context information for facilitating inconsistency handling. Many
methods have been proposed to solve this problem and a main class of them is based on
some kind of paraconsistent semantics. In this paper, we consider the computational aspects
of inconsistency degrees of propositional knowledge bases under 4-valued semantics. We
ˉrst give a complete analysis of the computational complexity of computing inconsistency
degrees. As it turns out that computing the exact inconsistency degree is intractable, we then
propose an anytime algorithm that provides tractable approximations of the inconsistency
degree from above and below. We show that our algorithm satisˉes some desirable properties
and give experimental results of our implementation of the algorithm. |
| KeyWord::knowledge representation inconsistency measurement multi-valued logic computational complexity algorithm |
|
|
|
| Abstract:Measuring inconsistency degrees of inconsistent knowledge bases is an important
problem as it provides context information for facilitating inconsistency handling. Many
methods have been proposed to solve this problem and a main class of them is based on
some kind of paraconsistent semantics. In this paper, we consider the computational aspects
of inconsistency degrees of propositional knowledge bases under 4-valued semantics. We
ˉrst give a complete analysis of the computational complexity of computing inconsistency
degrees. As it turns out that computing the exact inconsistency degree is intractable, we then
propose an anytime algorithm that provides tractable approximations of the inconsistency
degree from above and below. We show that our algorithm satisˉes some desirable properties
and give experimental results of our implementation of the algorithm. |
| keywords:knowledge representation inconsistency measurement multi-valued logic computational complexity algorithm |
| View Fulltext View/Add Comment Download reader |
|
|
|
