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@[205.160.76.189]>
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.

Pat

-- 
---------------------------------------------------------------------
IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
phayes@ai.uwf.edu 
http://www.coginst.uwf.edu/~phayes
Received on Friday, 5 October 2001 11:12:02 EDT

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