From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>

Date: Tue, 19 Feb 2002 09:20:53 -0500

To: phayes@ai.uwf.edu

Cc: dieter@cs.vu.nl, www-webont-wg@w3.org

Message-Id: <20020219092053D.pfps@research.bell-labs.com>

Date: Tue, 19 Feb 2002 09:20:53 -0500

To: phayes@ai.uwf.edu

Cc: dieter@cs.vu.nl, www-webont-wg@w3.org

Message-Id: <20020219092053D.pfps@research.bell-labs.com>

Here is my reply to Pat's comments that the restriction I presented does not indicate a paradox in the same-syntax extension layering of OWL on top of RDF. The Same-Syntax Extension Paradox Here is a more-detailed derivation of the paradox that I see when producing same-syntax extensions of RDF. There are two roads to a paradox. One of these roads uses features that are not in DAML+OIL, but exist in some DLs. The other, longer, more complicated road uses only features that are in DAML+OIL. The basic methodology here is to extract the properties of a same-syntax extension building on the new RDF model theory. This is mostly done by determining what entailments (or derivations, if you like) are needed and seeing what constraints this places on OWL (or OWL+, a more-powerful version of OWL) interpretations. I've tried to stay as close to the terminology in the new RDF model theory as possible. The summary of all this is that if you want to be a same-syntax extension of the RDF model theory and you have a) rdf:type as a property; b) defined classes, like DAML+OIL restrictions; c) some sort of complement or negation; and d) self reference then you have a semantic paradox. The first requirement, of course, is satisfied by RDF itself. 1/ First, consider classes defined as intersections. If John is in both A and B, then John is in the (an) intersection of A and B. <John, rdf:type, A>, <John, rdf:type, B> |= <John, rdf:type, :_1>, <:_1, owl:intersectionOf, :_2 >, <:_2, owl:first, A>, <:_2, owl:rest, :_3>, <:_3, owl:first, B>, <:_3, owl:rest, owl:nil>, This is only a valid entailment if all satisfying OWL interpretations of the first two statements contain an intersection class for A and B. This example motivates the inclusion of lots of things that must be in OWL interpretations. In particular, if A and B are classes, then there must be a list whose members are A and B, in that order, and there must be a class that is the intersection of this list. Note that I have not shown that there has to be a unique list consisting of A and B in that order, just that there must be at least one. Nor have I shown that there has to be a unique class that is the intersection of this list, just that there must be at least one. Also, there are lists and classes that have to be in all OWL interpretations. For example, in all OWL interpretations there must be at least one list whose sole member is the denotation of rdfs:Class and there must be a class that is the intersection of this list. 2/ Now, consider classes that are finite sets. rdfs:Class is always in the class consisting of rdfs:Class |= <rdfs:Class, rdf:type, :_1>, <:_1, owl:oneOf, :_2 >, <:_2, owl:first, rdfs:Class>, <:_2, owl:rest, owl:nil> This example motivates the existence of finite sets in OWL interpretations. In particular, if i is an object, then there must a list whose sole member is i, and there must be a class that is the oneOf of this list. Some of these classes must be in all OWL interpretations. For example, there must be a class in all OWL interpretations that is the oneOf of a list whose sole member is the denotation of rdfs:Class. 3/ Next consider DAML+OIL restrictions. If John has a child that is a Person, then John belongs to the Restriction that requires that its members have a child that is a Person. <John, child, Joe>, <Joe, rdf:type, Person> |= <John, rdf:type, :_1>, <:_1, rdf:type, owl:Restriction>, <:_1, owl:onProperty, child>, <:_1, owl:hasClass, Person> This is only a valid entailment if all satisfying OWL interpretations of the first two statements contain a restriction of the above form. This example motivates the inclusion of lots of restrictions in OWL interpretations. In particular, if p is a property and c is a class, then there must be a restriction on p having class c. Again I have not shown that there must be a unique restriction of this form, just that there has to be at least one. So, in general if the objects mentioned in a restriction exist in an OWL interpretation then there must be such a restriction in the interpretation. As above, there are restrictions that have to be in all OWL interpretations. In particular, in all OWL interpretations there must be a restriction on the denotation of rdf:type having class the denotation of rdfs:Class. Now there are two roads that can be pursued. The easier road is to go outside of the expresssive power of DAML+OIL, allowing an identity property and local relationships between properties. I'll call this more-powerful version of OWL OWL+. 4/ A restriction that consists of those objects where rdf:type is not a superproperty of the identity property can be constructed using the above features. There is no syntax for this, but one way might be <:_1 rdf:type owl:Restriction> <:_1 owl+:onProperty owl+:identity> <:_1 owl+:notSuperProperty rdf:type> This is the Russel set, as an object belongs to this restriction if and only if it is not related to itself by the rdf:type property. More fully, is this restriction related to itself by the rdf:type property? Well if it is, then it is not an instance of itself because it violates the conditions in the restriction, and thus it is not related to itself by the rdf:type property. However, if it isn't, then it is an instance of itself because it satisfies the conditions in the restriction, and thus it is related to itself by the rdf:type property. So rdf:type is ill-defined on this restriction and thus it has no satisfying OWL+ interpretations. However, this restriction only mentions objects that exist in all OWL+ interpretations. Therefore a restriction of this form exists in all OWL+ interpretations. Therefore all OWL+ interpretations are ill-formed, so OWL+ has a semantic paradox. The harder road stays within DAML+OIL, using circular or self references instead of an identity property. 5/ First, a simple kind of self-reference. If John is in a restriction C whose p's all belong to C, then John is in some restriction whose p's all belong to it. If Bill has no p's, then then Bill is in some restriction whose p's all belong to it. <John, rdf:type, C>, <C, rdf:type, owl:Restriction>, <C, owl:onProperty, p>, <C, owl:toClass, C> |= <John, rdf:type, :_1>, <:_1, rdf:type, owl:Restriction>, <:_1, owl:onProperty, p>, <:_1, owl:toClass, :_1> This is a valid entailment, showing that restrictions can point back to themselves. 6/ Now, a self-referential restriction that is entailed by statements that are not self referential. If John has no p's, then John is in some restriction whose p's all belong to it. <John, rdf:type, :_1>, <:_1, rdf:type, owl:Restriction>, <:_1, owl:onProperty, p>, <:_1, owl:maxCardinality, "0"> |= <John, rdf:type, :_2>, <:_2, rdf:type, owl:Restriction>, <:_2, owl:onProperty, p>, <:_2, owl:toClass, :_2> From the previous entailment, restrictions that point back to themselves are allowed. Given that they are allowed, the above entailment is mandated, John is a member of any restriction whose c's all belong to it because he has no c's. Therefore, OWL interpretations must include self-referential restrictions. In particular, is c is a property, then there must be a restriction that is all c's belong to itself. Again, restrictions of this form exist in all OWL interpretations. In particular, all OWL interpretations must contain restrictions whose condition is that all rdf:type's belong to the restriction. 7/ Next, a more complex self-referential restriction. If John has no c's, then John is in some restriction that has no c's that are the restriction itself. <John, rdf:type, :_1>, <:_1, rdf:type, owl:Restriction>, <:_1, owl:onProperty, c>, <:_1, owl:maxCardinality, "0"> |= <John, rdf:type, :_2>, <:_2, rdf:type, owl:Restriction>, <:_2, owl:onProperty, c>, <:_2, owl:maxCardinalityQ, "0">, <:_2, owl:hasClassQ, :_3>, <:_3, owl:oneOf, :_4>, <:_4, owl:first, :_2>, <:_4, owl:rest, owl:nil> This is just a combination of previous stuff. In particular, if c is a property then there must be a restriction that whose condition is that no c's belong to the oneOf of itself. From the above, a restriction like <:_2, rdf:type, owl:Restriction>, <:_2, owl:onProperty, rdf:type>, <:_2, owl:maxCardinalityQ, "0">, <:_2, owl:hasClassQ, :_3>, <:_3, owl:oneOf, :_4>, <:_4, owl:first, :_3>, <:_4, owl:rest, owl:nil> must be in all OWL interpretations that have rdf:type as a property. But this is all OWL interpretations. Now is this restriction related to itself by rdf:type? If it is, then it is not; but if it is not, then it is. Thus any OWL interpretation containing this restriction is ill-formed. But this is all OWL interpretations, so OWL has a semantic paradox.Received on Tuesday, 19 February 2002 09:21:38 GMT

*
This archive was generated by hypermail 2.2.0+W3C-0.50
: Monday, 7 December 2009 10:57:47 GMT
*