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

Great, and many thanks for checking it. However this example has 
pointed out a bug in the MT document that I hadnt noticed. The 
interpolation lemma uses a slightly different notion of 'instance' 
than the one defined in the text. According to the text definition, 
all the instances of E must have three arcs, so none of them are a 
subgraph of A. I need to introduce a notion of a 'tidy instance', ie 
what you get by instantiating *and then tidying* the graph. I bet 
that is what Euler currently does automatically,  in effect, right?

>PS2 what about the Constraint* stuff in RDFS
>     I mean are we keeping/dropping that?

If its in the language, it ought to be in the model theory; but is it 
going to be in the language?? Not my call. I await instructions.

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 13:02:32 UTC