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

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
situations.

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
equivalent).
So there are several possible intuitive meanings to that, the editors of
OWL didn't choose any.

 hope this helps

  pa

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