Explaining undecidability for RDF-based Semantics

Hi all,

I'm teaching some Semantic Web stuff and I was looking for as 
simple/intuitive/direct an explanation as possible as to why (e.g.) 
entailment checking under OWL 2 RDF-Based Semantics is undecidable, and 
why it thus may be desirable to define a restricted semantics/language.


I know, for example, that there are reductions from the Domino Tiling 
problem using features in OWL (2) Full such as metamodelling involving 
the OWL vocabulary itself, or complex roles in number restrictions:

Boris Motik:
On the Properties of Metamodeling in OWL. J. Log. Comput. 17(4): 617-637 
(2007)

I. Horrocks, U. Sattler, and S. Tobies.
Practical Reasoning for Very Expressive Description Logics. Logic 
Journal of the IGPL, 8(3):239–263, 2000.

... but again, I'm hoping (if possible) to find something much more 
simple/didactic, perhaps exploiting some other well-known decidability 
restriction that OWL 2 Full misses and/or a reduction from an even 
"simpler" undecidable problem. (It is quite possible I'm missing 
something obvious.)


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 19:53:46 UTC