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

RE: NP completeness & rdf entailment, graph identity, MT etc.

From: Pat Hayes <phayes@ai.uwf.edu>
Date: Tue, 9 Oct 2001 11:15:15 -0500
Message-Id: <p05101026b7e8d252a460@[205.160.76.193]>
To: "Jeremy Carroll" <jjc@hplb.hpl.hp.com>
Cc: w3c-rdfcore-wg@w3.org
>Jeremy:
>>  >+ equivalence of RDF graphs is NP complete
>Pat:
>>  Presume you mean semantic equivalence, ie A equivalent B means: A
>>  entails B and B entails A (?)
>
>Yes.
>
>
>Jeremy:
>>  >So the "graphs are sets?!" thread was triggered by my observation that an
>>  >ntriple file with two identical triples
>>  >
>  > >A:
>>  >
>>  ><uri> <pred> <uri2> .
>>  ><uri> <pred> <uri2> .
>>  >
>>  >was equivalent to one with only one:
>>  >
>>  >B:
>>  >
>>  ><uri> <pred> <uri2> .
>
>Pat:
>>  They are certainly equivalent in the sense that each entails the
>>  other. I thought what we were discussing was whether we even want to
>>  allow the first one as a well-formed graph.
>>
>
>It *is* a well-formed N-Triples file.
>

Yes, true. What I meant was, whether we want to allow a graph with 
two identical arcs between the same two nodes as a well-formed graph, 
or if on the other hand we want to say that those two documents 
describe the same graph. Right now there is nothing to rule out such 
a duplicate-arc graph, according to our definitions.

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 Tuesday, 9 October 2001 12:15:16 EDT

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