- From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
- Date: Fri, 06 Jun 2003 18:13:30 -0400 (EDT)
- To: connolly@w3.org
- Cc: welty@us.ibm.com, www-webont-wg@w3.org, phayes@ai.uwf.edu
From: Dan Connolly <connolly@w3.org>
Subject: Re: RDFS closures, polite discourse
Date: 06 Jun 2003 15:03:56 -0500
>
> On Fri, 2003-06-06 at 14:01, Christopher Welty wrote:
> > Dan,
> >
> > I find Peter's comments useful and directly to the point. RDFS not
> > decidable.
>
> No? What makes you think not?
>
> > I don't believe I've ever heard Pat claim otherwise.
>
> Yes, he has. to wit...
>
> "RDFS Entailment Lemma. S rdfs-entails E iff the rdfs-closure of S
> simply entails E."
>
> -- RDF Semantics
> W3C Working Draft 23 January 2003
> Editor:
> Patrick Hayes
> http://www.w3.org/TR/2003/WD-rdf-mt-20030123/#prf
Well, this does not show that entailment in RDFS is decidable.
Computing the rdfs-closure of an RDF graph might be undecidable. It might
even be impossible. Actually, it is impossible to compute the rdfs-closure
of an RDF graph, as the rdfs-closure of an RDF graph is infinite in size,
and thus uncomputable. Computing a representation of the closure might be
decidable, however.
Simple entailment might be undecidable.
All this, of course, doesn't show that RDFS entailment is undecidable
either. However, it is not self-evident that RDFS entailment is
decidable. Even showing that the rdfs-closure of an RDF graph is finite
would not suffice for that.
peter
PS: I'm pretty sure that RDFS entailment *is* decidable, the above
notwithstanding.
Received on Friday, 6 June 2003 18:14:04 UTC