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 11:09:17 +0100
Message-ID: <4E24064D.609@cs.ox.ac.uk>
To: Cristiano Longo <longo@dmi.unict.it>
CC: semantic-web@w3.org
On 18/07/11 10:48, Cristiano Longo wrote:
> On 18/07/2011 11:24, Markus Krötzsch wrote:
>> On 18/07/11 08:27, Cristiano Longo wrote:
>>> Morning all,
>>> in the far future I planned to implement a description logic reasoner.
>>> May you give me some hints or pointers about the pratical (I yet know
>>> the algorithm) for implementing such a reasoner?
>> Dear Christian,
>> description logics come in various flavours to match different
>> application areas. These different logics also match different
>> profiles of OWL: OWL EL, OWL QL, OWL RL, and OWL DL (there is also OWL
>> Full but its semantics is not description logics based though both are
>> compatible to some extent).
>> EL, QL, RL are more lightweight for better scalability (for example
>> OWL RL has been implemented in distributed settings with billions of
>> assertions; and EL has been used to classify ontologies with hundreds
>> of thousands of classes in a few seconds; QL is meant for
>> ontology-based data access to large databases). OWL DL provides the
>> full modelling support of all DL features that OWL has. Lightweight
>> languages are genermayally easier to implement but any efficient
>> implementation will need a lot of engineering. Just implementing an
>> algorithm from a research paper will not lead to good results.
>> So before you can start, you really need to decide which description
>> logic/OWL profile you want to support. This is closely related to
>> another important questions: why do you want to implement your own
>> tool instead of just using an existing one?
>> Regards
>> Markus
> 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.


> [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 10:09:53 UTC

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