Re: About OWL and SWRL

On 20/01/2011 13:55, Cristiano Longo wrote:
> Combining OWL with SWRL leads to undecidability? May you give me some
> pointer about that, please?

The claim is "officially" made in the SWRL member submission already, so 
this is what you would cite for the result. Below is some further 
explanation.

SWRL is a full-fledged language with many features (e.g. built-ins) but 
undecidability of reasoning already follows from the most basic features 
of its rules. So one can forget about most of the more technical aspects 
of SWRL for proving this. Likewise, OWL DL is based on Description 
Logics (DLs) and only this "logical core" of OWL is necessary to show 
undecidability (so, again, most of the technical details of the W3C 
standard can be neglected).

Now showing that reasoning with DLs + rules is undecidable can be done 
in many ways. The SWRL submission cites one such way based on a proof 
that showed the undecidability of reasoning for a DL extended with role 
value maps (today known as unrestricted property chains), noting that 
the proof works as well if these role value maps are replaced by SWRL 
rules. A fully self-contained direct proof can be found, e.g., in my 
dissertation [1, Fact 4.2.2]. This dissertation also discusses more 
generally how this problem is caused, and which proposals have been made 
to overcome it.

Regards,

Markus

[1] http://korrekt.org/page/Description_Logic_Rules_%28monograph%29

-- 
Dr. Markus Krötzsch
Oxford  University  Computing  Laboratory
Room 306, Parks Road, Oxford, OX1 3QD, UK
+44 (0)1865 283529    http://korrekt.org/

Received on Thursday, 20 January 2011 16:43:54 UTC