%0 Journal Article %J ACM Trans. Comput. Log. %D 2013 %T Complexities of Horn Description Logics %A Markus Krötzsch %A Sebastian Rudolph %A Pascal Hitzler %K computational complexity %K description logics %K Horn logic %X Description Logics (DLs) have become a prominent paradigm for representing knowledge bases in a variety of application areas. Central to leveraging them for corresponding systems is the provision of a favourable balance between expressivity of the knowledge representation formalism on the one hand, and runtime performance of reasoning algorithms on the other. Due to this, Horn description logics (Horn DLs) have attracted attention since their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large sets of instance data (ABoxes). However, the natural question whether Horn DLs also provide advantages for schema (TBox) reasoning has hardly been addressed so far. In this paper, we therefore provide a thorough and comprehensive analysis of the combined complexities of Horn DLs. While the combined complexity for many Horn DLs studied herein turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning. We also provide convenient normal forms for Horn DLs. %B ACM Trans. Comput. Log. %V 14 %P 2 %G eng %U http://doi.acm.org/10.1145/2422085.2422087 %R 10.1145/2422085.2422087 %0 Journal Article %J International Journal of Software and Informatics %D 2010 %T Computational Complexity and Anytime Algorithm for Inconsistency Measurement %A Yue Ma %A Guilin Qi %A Guohui Xiao %A Pascal Hitzler %A Zuoquan Lin %K algorithm %K computational complexity %K inconsistency measurement %K Knowledge representation %K multi-valued logic %X

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 first 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 satisfies some desirable properties and give experimental results of our implementation of the algorithm

%B International Journal of Software and Informatics %V 4 %P 3–21 %G eng %U http://www.ijsi.org/ch/reader/view_abstract.aspx?file_no=i41&flag=1