Re: Reasoning

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     

Received on Monday, 18 July 2011 11:21:27 UTC