Re: Readings on OWL's (un)decidability?

[I'm replying directly to the initial message instead of including some of
the replies, but I will address some of the information there as well.]

OWL FULL is undecidable (as stated by Pierre-Antoine Champin this is an
imprecise gloss of something like "entailment in OWL Full is undecidable")
for a number of reasons.  One of these comes from the Description Logic
used in OWL Full.  Another comes from RDF(S).

More formally, there is no way of building a machine that correctly and
always and finitely answers questions like:

	Does an OWL ontology (i.e., an RDF document) imply (in the OWL Full
	semantics) that one class is a subclass of another?

The "question" can be one of many similar questions, including whether an
OWL ontology is consistent and an individual is a member of a class.

I don't like the wording in the initial message for several reasons,
including the unusual use of "system".  It is much better to say something
like 

	There are many OWL Full ontologies that are "decidable" - i.e.,
	any question of interest to that ontology can be answered.  This
	includes all OWL Full ontologies that don't mention any OWL
	vocabulary.

Note that it is possible to ask undecidable questions about most OWL
ontologies.  Consider an empty ontology and asking questions that use
complex OWL descriptions instead of just names of classes in the ontology.
This is an undecidable problem.


Note also that given any particular OWL Full ontology *is* possible to
build a machine that correctly answers all questions like

	Is class A a subclass of class B.

where A and B are classes mentioned in the ontology.  Why?  Because there
are only a finite number of such questions and thus this can simply be done
by table lookup.  Now it is *not* possible to build this table in general,
but for any particular ontology the table does exist and thus there is some
machine that can do the right thing.  (Yes, this is being a bit pedantic,
but one does have to be careful to state things correctly when talking
about decidability and related issues.)


I recommend reading the paper 

	Boris Motik
	On the Properties of Metamodeling in OWL
	ISWC2005
	http://www.cs.man.ac.uk/~bmotik/publications/papers/motik05metamodeling.pdf

as it has a discussion of some of the sources of undecidability in OWL
Full.

Peter F. Patel-Schneider
Bell Labs Research


PS: It is the case that any RDF document has a formal meaning in OWL Full
(i.e., the RDF compatiable semantics in
http://www.w3.org/TR/owl-semantics/rdfs.html).  However this formal meaning
may be rather strange for RDF documents that do unusual things.  The
example in the message from Pierre-Antoine Champin is actually a very
benign example - one where there actually is a fairly intuitive semantics.


From: "Yoshio Fukushige" <fukushige.yoshio@jp.panasonic.com>
Subject: Readings on OWL's (un)decidability?
Date: Mon, 2 Oct 2006 01:27:15 -0500

> 
> Hello, 
> 
> I've seen many documents saying "OWL FULL is undecidable" ... (a)
> 
> But which of the following does (a) mean?:
> 
> (1) "There is no system which is decidable where there is a Class, say
> ClassA,
> that is an instance of another Class."
> 
> or
> 
> (2)"There is at least one system which is undecidable where/because
> there is a Class, say ClassA,
> that is an instance of another Class.
> i.e. Not every system with a vocabulary in OWL FULL is decidable."
> 
> What do you recommend me to read for the proof of (a)?
> (A (short) article on the Web is preferred to a whole book ^_^;)
> 
> Best,
> Yoshio 
> 
> -- 
> Yoshio Fukushige <fukushige.yoshio@jp.panasonic.com>
> Network Development Center,
> Matsushita Electric Industrial Co., Ltd.
> 
>

Received on Tuesday, 3 October 2006 16:28:17 UTC