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

>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 UTC