W3C home > Mailing lists > Public > www-webont-wg@w3.org > June 2003

Re: RDFS closures, polite discourse

From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
Date: Fri, 06 Jun 2003 18:13:30 -0400 (EDT)
Message-Id: <20030606.181330.01427671.pfps@research.bell-labs.com>
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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:58:00 GMT