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

Thank you Pierre-Antoine, for the response.



On Mon, 02 Oct 2006 11:18:28 +0200
Pierre-Antoine Champin <swlists-040405@champin.net> wrote:

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

So what is meant is
"It is not possible to build a machine M that can answer any question
written with any OWL FULL vocabulary",
right?

Then what is the condition on a vocabulary V for the system with V
to be decidable?

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

Hmm, per OWL Reference [1], 

---
A restriction class should have exactly one triple linking the restriction to a particular property, using the owl:onProperty property. The restriction class should also have exactly one triple that represents the value constraint c.q. cardinality constraint on the property under consideration, e.g., that the cardinality of the property is exactly 1.
---

Is the construct above valid in OWL?

(and I wonder if the second owl:minCardinality is meant to be
owl:maxCardinality...)

[1] http://www.w3.org/TR/owl-ref/#Restriction

Best,
Yoshio

-- 
Yoshio FUKUSHIGE <fukushige.yoshio@jp.panasonic.com>
Network Development Center,
Matsushita Electric Industrial Co., Ltd.

Received on Monday, 2 October 2006 15:18:11 UTC