W3C home > Mailing lists > Public > public-owl-wg@w3.org > February 2008

Re: completeness

From: Bijan Parsia <bparsia@cs.man.ac.uk>
Date: Thu, 21 Feb 2008 17:36:37 +0000
Message-Id: <8CB87C2D-DD2E-4B1C-80B4-D292D086802C@cs.man.ac.uk>
Cc: Ulrike Sattler <sattler@cs.man.ac.uk>, OWL Working Group WG <public-owl-wg@w3.org>
To: "Michael Schneider" <schneid@fzi.de>

BTW, I suspect the most common form of RDFS incompleteness is in  
BNode handling. Full variables semantics is expensive even in RDF and  
Pd* (non-ground entailment is NP-complete). When I was working with  
some folks trying to do RDFS on a rules system, the first ignored  
thing is the BNode entailment rules ;)

(I would think that ground graphs on the rhs would be sufficient to  
avoid NP completeness. OTOH, if you treat BNodes as names instead of  
variables, then all graphs are effectively ground.)

For an excellent paper on RDFS reasoning in the ground setting see:
	http://www2.ing.puc.cl/~jperez/papers/minimal-rdf-camera-ready-ext.pdf

Cheers,
Bijan.
Received on Thursday, 21 February 2008 17:34:45 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Thursday, 21 February 2008 17:34:46 GMT