W3C home > Mailing lists > Public > semantic-web@w3.org > October 2006

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

From: Pierre-Antoine Champin <swlists-040405@champin.net>
Date: Mon, 02 Oct 2006 11:18:28 +0200
Message-ID: <4520D964.3090302@champin.net>
To: Yoshio Fukushige <fukushige.yoshio@jp.panasonic.com>
CC: semantic-web@w3.org

Yoshio Fukushige a écrit :
> 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."

Short answer: (2), because RDFS is decidable, and definitely allows
ClassA to be an instance as well.

Long answer: "OWL FULL is undecidable" is actually a short (and
unprecise) for "the problem of entailment is undecidable in OWL FULL",
i.e. there is no algorithm which can tell us *for sure* (i.e. sound and
complete) whether an arbitrary OWL FULL graph is a consequence of
another arbitrary OWL FULL graph.

That does not mean that it is impossible to do anything with OWL FULL.
Pellet is able to make some inferences whith OWL FULL ontologies; there
is just no guarantee on that. This can neverthess be useful in some

Note also that extended expressiveness (like the ability to make a class
an instance of another class) is not the only/main reason of the
undecidability of OWL FULL: another problem is that some expressions in
OWL FULL have *no* formal semantics at all. E.g.

  [ a owl:Restriction ;
    owl:onProperty :child ;
    owl:minCardinality 2 ;
    owl:minCardinality 4 ]

is valid in OWL FULL. Reject the intuition telling you that it is the
class of things having between 2 and 4 children, because it is *not*
what that means. It could as well mean that any instance having at least
2 children is entailed to also have at most 4 children (because the two
possible restrictions described by that construct are then bound to be
So there are several possible intuitive meanings to that, the editors of
OWL didn't choose any.

 hope this helps

Received on Monday, 2 October 2006 09:18:42 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 07:41:53 UTC