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

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