- From: Cristiano Longo <longo@dmi.unict.it>
- Date: Mon, 18 Jul 2011 12:52:06 +0200
- 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