Complexity of Reasoning

Cambridge University Press. Description Logic Handbook, page 96--136 - 2003
Download the publication : donini-chap3.pdf [642Ko]  
We present lower bounds on the computational complexity of satisfiability and subsumption in several description logics. We interpret these lower bounds as coming from different ``sources of complexity", which we isolate one by one. We consider both reasoning with simple concept expressions and with an underlying TBox. We discuss also complexity of instance check in simple ABoxes. We tried to enhance clarity and ease of presentation, sometimes sacrificing exhaustiveness for lack of space.

BibTex references

author = {Francesco M. Donini},
title = "Complexity of Reasoning",
chapter = "3",
series = "Description Logic Handbook",
pages = "96--136",
year = "2003",
publisher = "Cambridge University Press",
url = ""

Other publications in the database

SisInf Lab - Information Systems Laboratory

Research group of Politecnico di Bari
Edoardo Orabona St, 4 Bari, Italy