zbMATH — the first resource for mathematics

Complexity of terminological reasoning revisited. (English) Zbl 0949.03030
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, 181-200 (1999).
Summary: TBoxes in their various forms are key components of knowledge representation systems based on description logics (DLs) since they allow for a natural representation of terminological knowledge. Largely due to a classical result given by B. Nebel [Artif. Intell. 43, No. 2, 235-249 (1990; Zbl 0717.68089)], complexity analyses for DLs have, until now, mostly failed to take into account the most basic form of TBoxes, so-called acyclic TBoxes. In this paper, we concentrate on DLs for which reasoning without TBoxes is PSPACE-complete, and show that there exist logics for which the complexity of reasoning remains in PSPACE if acyclic TBoxes are added and also logics for which the complexity increases. This demonstrates that it is necessary to take acyclic TBoxes into account for complexity analyses.
For the entire collection see [Zbl 0921.00037].

03B70 Logic in computer science
68T30 Knowledge representation
68T27 Logic in artificial intelligence
68Q25 Analysis of algorithms and problem complexity