RE: blank nodes out the wazoo

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