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: 5475
Download times: 2676
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.
keywords:knowledge representation  inconsistency measurement  multi-valued logic  computational complexity  algorithm
View Full Text  View/Add Comment  Download reader

 

 

more>>  
Visitor:3139686
Top Paper  |  E-mail Alert  |  Publication Ethics  |  New Version

© Copyright by Institute of Software, the Chinese Academy of Sciences
京ICP备05046678号-5

京公网安备 11040202500065号