W3C home > Mailing lists > Public > semantic-web@w3.org > July 2011

Re: Reasoning

From: Cristiano Longo <longo@dmi.unict.it>
Date: Mon, 18 Jul 2011 12:52:06 +0200
Message-ID: <4E241056.40901@dmi.unict.it>
To: Markus Krötzsch <markus.kroetzsch@cs.ox.ac.uk>
CC: semantic-web@w3.org
Since I discovered a description logic in which the consistency problem
>> in NP-complete (cf. [1]), and I wander if this teoretical property is
>> relevant in the real world, considering that non-deterministic
>> computations cannot take place with the hardware that is actually
>> available.
>
> There are already a number of DLs where consistency checking is 
> polynomial. So an NP-complete logic would be somewhere in between the 
> tractable and the highly expressive. Since you have a new unusual 
> semantics for DLs, you will probably have to invent new algorithms too.
>
> Markus
Of course, I think I'll take a look to the open source existing reasoner.

Thank You,
Cristiano Longo

PS: the semantics of the description logic mentioned in the paper is the 
usual descriptive one.
>
>>
>> [1] Domenico Cantone, Cristiano Longo, and Antonio Pisasale. Comparing
>> Description Logics
>> with Multi-level Syllogistics: the Description Logic DL <MLSS^{×}_{2,m}>
>> . In 6th Workshop on
>> Semantic Web Applications and Perspectives (SWAP), 2010.
>>
>>
>
>
Received on Monday, 18 July 2011 10:52:46 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 07:42:29 UTC