- 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>
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 UTC