- From: Markus Krötzsch <markus.kroetzsch@cs.ox.ac.uk>
- Date: Mon, 21 Nov 2011 10:25:08 +0000
- To: Cristiano Longo <longo@dmi.unict.it>
- CC: semantic-web@w3.org
On 20/11/11 20:54, Cristiano Longo wrote: > Hi, I had a look to the Horrocks' paper about SROIQ. However, I need > information about the computational complexity of the knowledge base > consistency in this language. All standard inference tasks for SROIQ are N2ExpTime-complete, where the second exponential blow-up is due to the RBox (property chains) and thus tends to be small in practice (since complex property chains are rare in today's ontologies). Inclusion follows already from the paper you mention. The hardness result is due to Kazakov [1]. Cheers, Markus [1] Yevgeny Kazakov: RIQ and SROIQ Are Harder than SHOIQ. KR 2008 -- Dr. Markus Krötzsch Department of Computer Science, University of Oxford Room 306, Parks Road, OX1 3QD Oxford, United Kingdom +44 (0)1865 283529 http://korrekt.org/
Received on Monday, 21 November 2011 10:25:36 UTC