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

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

From: <jos.deroo.jd@belgium.agfa.com>
Date: Tue, 9 Oct 2001 12:07:59 +0100
To: phayes@ai.uwf.edu
Cc: w3c-rdfcore-wg@w3.org
Message-Id: <OF04670859.00581997-ON41256AE0.0038B52E@bayer-ag.com>


>>> A:
>>>
>>>  <uri> <pred> <uri2> .
>>>  <uri> <pred> <uri2> .
>>>
>>> B:
>>>
>>>  <uri> <pred> <uri2> .
>>>
>>> C:
>>>
>>>  <uri> <pred> <uri2> .
>>>  <uri> <pred> _:bnode .
>>>
>>> D:
>>>
>>>  <uri> <pred> <uri2> .
>>>  <uri> <pred> _:bnode .
>>>  _:bnode <pred> _:bnode2 .
>>>
>>(after some bug corrections) we currently find that
>>   A simple-entails A
>>   A simple-entails B
>>   A simple-entails C
>>   B simple-entails A
>>   B simple-entails B
>>   B simple-entails C (follows from B --> A --> C)
>>   C simple-entails A
>>   C simple-entails B (follows from C --> A --> B)
>>   C simple-entails C
>>   D simple-entails A
>>   D simple-entails B (follows from D -->A -->B, and similarly for rest)
>>   D simple-entails C
>>   D simple-entails D
>>and we *fail* to find that
>>   A simple-entails D
>>   B simple-entails D
>>   C simple-entails D
>
>I am *extremely* pleased to hear that, Jos :-)

;-)

>Now could you also try E:
>
>  <uri> <pred> <uri2> .
>  <uri> <pred> _:bnode .
> _:bnode2 <pred> _:bnode .
>
> Which ought to be simple-equivalent to (entail and entailed by) all
> of A, B and C (but you really only need to check one of them :-)

(again after a bug correction http://www.agfa.com/w3c/euler/#28.009)
we indeed find that
  A simple-entails E
  E simple-entails A
  etc...
and again *fail* to find that
  E simple-entails D

--
Jos

PS1 also thanks to Jeremy for those nice testcases!
PS2 what about the Constraint* stuff in RDFS
    I mean are we keeping/dropping that?
Received on Tuesday, 9 October 2001 06:08:29 EDT

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