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 12:02:30 -0500
Message-Id: <p05101029b7e8dc5afe62@[205.160.76.193]>
To: jos.deroo.jd@belgium.agfa.com
Cc: w3c-rdfcore-wg@w3.org
>  >>> 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 EDT

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