- From: Markus Krötzsch <markus.kroetzsch@cs.ox.ac.uk>
- Date: Mon, 18 Jul 2011 12:21:01 +0100
- To: Cristiano Longo <longo@dmi.unict.it>
- CC: semantic-web@w3.org
On 18/07/11 11:52, Cristiano Longo wrote:
> 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.
I only skimmed through the paper but my impression was that your DL is
not defined as a fragment of other DLs or of first-order logic, but that
you define a new model theory instead. Descriptive or not, this may
require reasoning methods that are different from the ones that are used
for FOL-based DLs.
Markus
>>
>>>
>>> [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.
>>>
>>>
>>
>>
>
>
--
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, 18 July 2011 11:21:27 UTC