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. JeremyReceived 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