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

Re: Reasoning

From: Markus Krötzsch <markus.kroetzsch@cs.ox.ac.uk>
Date: Mon, 18 Jul 2011 12:21:01 +0100
Message-ID: <4E24171D.6030907@cs.ox.ac.uk>
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.


>>> [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

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