W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > October 2001

Re: A proposal for entailment tests

From: Pat Hayes <phayes@ai.uwf.edu>
Date: Fri, 5 Oct 2001 10:12:02 -0500
Message-Id: <p05101011b7e37d882598@[]>
To: jos.deroo.jd@belgium.agfa.com, jjc@hplb.hpl.hp.com
Cc: w3c-rdfcore-wg@w3.org
>>  One note: the current "equality" tests are computational less expensive than
>>  an rdf entailment test. Technically it is the difference between Graph
>>  Isomorphism and SubGraph Isomorphism. GI is thought to be strictly between P
>>  and NP where SubGraph Iso is known to be NP. For these reason it may be
>>  desirable to either:
>>  + add rdfEquivalent and rdfsEqualivalent predicates
>>  or make sure we use cycles, and suggest that users of the test cases should
>>  search for such cycles if they have a GI algorithm available.
>i lean more towards the cycles...
>but can live with equivalent

I also prefer to stick with cycles for now. Even if we allow 
rdfEquivalent, we would still need to check for the cycles in any 
case (no way to mandate against a valid inference); and I don't think 
these graphs are going to get so big that the complexity is really 
going to hurt anyone.


IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
Received on Friday, 5 October 2001 11:12:02 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 20:24:05 UTC