Practical reasoning for expressive description logics. (English) Zbl 0947.68134
Ganzinger, Harald (ed.) et al., Logic for programming and automated reasoning. 6th international conference, LPAR ’99, Tbilisi, Georgia, September 6-10, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1705, 161-180 (1999).
This paper examines a particular class of knowledge representation formalisms, namely description logics. Specifically, several extensions and variants of a classical example, \(\mathcal ALC\), introduced in 1991 by M. Schmidt-Schauss and G. Smolka [J. Artif. Intell. 48, No. 1, 1-26 (1991; Zbl 0712.68095)] are studied. It was shown that deciding coherence and subsumption for \(\mathcal ALC\) are PSPACE-complete problems in linear space. The present paper examines satisfiability and subsumption of the examined variants and proves, among others, that these problems are still in PSPACE. This conference version contains only selected proofs; the authors refer to technical reports, published at their institutions, for full details.
For the entire collection see [Zbl 0921.00037].
For the entire collection see [Zbl 0921.00037].
Reviewer: Heribert Vollmer (Würzburg)
MSC:
68T27 | Logic in artificial intelligence |
03B25 | Decidability of theories and sets of sentences |
68T30 | Knowledge representation |
03B70 | Logic in computer science |