W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > June 2003

RE: blank nodes out the wazoo

From: Jeremy Carroll <jjc@hplb.hpl.hp.com>
Date: Tue, 17 Jun 2003 10:40:24 +0200
To: "pat hayes" <phayes@ihmc.us>
Cc: <w3c-rdfcore-wg@w3.org>
Message-ID: <BHEGLCKMOHGLGNOKPGHDOELOCBAA.jjc@hpl.hp.com>

Pat:
> It means that being a lean graph is potentially a very costly
> property to check, whereas I thought it was fairly trivial. Which
> means that in general, checking non-entailment between two graphs is
> potentially expensive.
>

Agreed - simple entailment is probably NP complete

(I am not absolutely sure: the subgraph isomorphism problem (which is NP) is
closely related, but I do not have an exact embedding).

The result for conceptual graphs (irredunancy is NP complete) is probably
applicable to RDFS entailment, but again it is real work to show this.

Jeremy
Received on Tuesday, 17 June 2003 04:40:33 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:57:55 EDT