From: Michael Schneider <schneid@fzi.de>

Date: Mon, 25 Feb 2008 10:46:29 +0100

Message-ID: <0EF30CAA69519C4CB91D01481AEA06A07510A2@judith.fzi.de>

To: "Bijan Parsia" <bparsia@cs.man.ac.uk>

Cc: "OWL Working Group WG" <public-owl-wg@w3.org>

Date: Mon, 25 Feb 2008 10:46:29 +0100

Message-ID: <0EF30CAA69519C4CB91D01481AEA06A07510A2@judith.fzi.de>

To: "Bijan Parsia" <bparsia@cs.man.ac.uk>

Cc: "OWL Working Group WG" <public-owl-wg@w3.org>

On Friday, 2008-02-22, I answered to Bijan: >>(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.) > >And the pD* paper [20] confirms your assumption: The paper's >introduction explains (and it is later proven) that >NP-completeness can already be shown for Simple Entailment, >the smallest semantics which treats bNodes as existentials. >The amazing thing is: It doesn't get worse for RDFS and even >for pD*! It is shown in the paper (though I haven't checked >yet) that entailment checking is NP-complete for pD* in >general, but polynomial, if there are no (existentially >interpreted) bNodes in the regarded graphs. I now see that I was imprecise in my last mail. It is really as you said above: It suffices to have only the /RHS/ of an entailment to be ground in order to be in P. This has the important consequence that for pD* the consistency problem is in P (w.r.t. the size of the regarded RDF graph), even if the graph contains existentially interpreted bNodes (Theorem 5.15 of the pD* paper [20]). The reason is that in order to decide whether some RDF graph G is consistent or not, one only has to do polynomially many entailment checks, where all involved RHS graphs are ground, and are of constant-bound size. Cheers, Michael [20] <http://linkinghub.elsevier.com/retrieve/pii/S1570826805000144> -- Dipl.-Inform. Michael Schneider FZI Forschungszentrum Informatik Karlsruhe Abtl. Information Process Engineering (IPE) Tel : +49-721-9654-726 Fax : +49-721-9654-727 Email: Michael.Schneider@fzi.de Web : http://www.fzi.de/ipe/eng/mitarbeiter.php?id=555 FZI Forschungszentrum Informatik an der Universität Karlsruhe Haid-und-Neu-Str. 10-14, D-76131 Karlsruhe Tel.: +49-721-9654-0, Fax: +49-721-9654-959 Stiftung des bürgerlichen Rechts Az: 14-0563.1 Regierungspräsidium Karlsruhe Vorstand: Rüdiger Dillmann, Michael Flor, Jivka Ovtcharova, Rudi Studer Vorsitzender des Kuratoriums: Ministerialdirigent Günther LeßnerkrausReceived on Monday, 25 February 2008 09:46:43 UTC

*
This archive was generated by hypermail 2.3.1
: Tuesday, 6 January 2015 21:42:02 UTC
*