Re: Explaining undecidability for RDF-based Semantics

On 04/09/2015 17:18, Ignazio Palmisano wrote:
<snip>
> I'm no expert on the topic but I've spotted the following:
>
> http://www.w3.org/2009/12/rdf-ws/papers/ws16
>
> A one sentence explanation of undecidability is included: given that
> the definition of entailment says that the RDFS container membership
> triples must be included in the entailment graphs, and the set of
> container membership triples is infinite, the entailment graphs have
> infinite size.
>
> As I understand from other articles as well (can't find the full text
> for them though), this undecidability can be avoided (by skipping the
> infinitely many triples whose property does not appear in the actual
> graph under examination, i.e., all rdf:_i properties such that there
> is no collection with an ith element in the graph are discarded.).

Thanks Ignazio! Unfortunately, this refers only to the computability of 
the closure ... i.e., to materialising all the entailments. Also I think 
the RDF-Based Semantics of OWL doesn't include the container membership 
properties of RDFS (for obvious reasons ;)) ... but in any case, there 
are many other reasons why writing down all the entailments of an OWL 
ontology would be problematic. For example, a class defined with a 
max-cardinality of 2 on property p would be entailed to be a sub-class 
of the class with max-cardinality 3, 4, 5, 6 ... on the same property.

This is of course something I could mention, but since OWL 2 
Full/RDF-Based Semantics and OWL 2 DL/Direct Semantics suffer the same 
problem with respect to materialising all entailments, it does not help 
to motivate the need so much for OWL 2 DL/Direct Semantics (though it 
may be useful to motivate the profiles that have useful algorithms based 
on materialisation).

Instead I'm interested in the decidability of the entailment problem: 
given two OWL ontologies O1 and O2, I'm looking for a nice 
proof/argument as to why checking if O1 entails O2 wrt. the OWL 
RDF-Based Semantics is undecidable. (Such a check can be done without 
having to materialise all the entailments.)

> This is just one example of an avoidable undecidability :-) I reckon I
> would have enjoyed such a presentation in my student days.

I hope my students will share your enthusiasm. :)

Cheers,
Aidan


>>
>> Any pointers or ideas would be great. The target audience would be
>> undergrads who may not have taken a logic or complexity course. The goal is
>> to establish the undecidability of entailment for OWL 2 Full in as
>> accessible a manner as possible.
>>
>> Best,
>> Aidan
>>
>

Received on Friday, 4 September 2015 21:33:29 UTC