Re: complexity of sroiq

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].



[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     

Received on Monday, 21 November 2011 10:25:36 UTC