Re: Question on DL negation

On Mar 8, 2007, at 8:16 AM, Michael Schneider wrote:

> Bijan Parsia wrote on Wed, 7 Mar 2007 at 22:41:
>
>> On Mar 7, 2007, at 10:10 PM, Michael Schneider wrote:
>>> Bijan's 'complementOf' construction only works in OWL-DL,
>> Sigh. I think you miss the point. Adding disjointWith to a  
>> language  that can simulate it directly or via complementOf  
>> doesn't increase  the expressiveness (in the sense of altering the  
>> worst case  complexity).
>
> You are right, I missed the point here, but only because I have  
> missed it already before:

Aha! It all becomes clear (from below)

> In my previous mail to you, Ulrike and Evgeny, I misunderstood the  
> example construct that you cited in another mail.
>
> I wrote:
>
> > Bijan Parsia wrote on Wed, 7 Mar 2007 at 15:00:
>> It stays EXPTIME-complete since you can polynomially encode class   
>> disjointness in OWL-Lite.
>> [...]
>>> """ > > [1] An example construct, which Jeremy credits to Ian   
>>> Horrocks, is as follows.
>>>  > > >
>>>  > > > Given a definition of a class C:
>>>  > > >    Class(C complete <expr1>)
>>>  > > >
>>>  > > > The let P be a property which is not used elsewhere and  
>>> define:
>>>  > > >    Class(C complete restriction(minCardinality(P, 1))
>>>  > > >    Class(C-co complete restriction(maxCardinality(P, 0))"""
>> Ok, "C-co" here is the "other" class, which can also have some  
>> definition elsewhere:
>>    Class(C-co complete <expr2>)
>> The latter two number restriction (re)definitions are obviously  
>> disjoint.
>
> As you can see, I wrongly thought that this was an example for  
> expressing /disjointness/ of the classes "C" and "C-co". But it  
> actually turns out to be an example on how to define the / 
> complement/ of a given class C within OWL-Lite!
>
> I did not expect that this was possible at all (we were just  
> talking about /disjointness/ all the time). But it works, and I  
> have to admit that this really amazes me (hey, I am just an  
> ordinary OWL user :))! And then, of course, getting disjointness  
> from this result is just a corollary.
[snip]
I'll take some unclarity blame here. I just presumed that it was  
obvious that the disjointness construction was going via complement.  
Sorry about that.

Yes, OWL Lite is *not* a helpful subset if you are thinking about  
thinks from the overall expressivity or complexity view. It is a very  
expressive logic (i.e., roughly SHIF) and yet it lacks many of the  
constructors we normally associate with such a logic.

Moral: If you want to define (computational) subsets of a logic, you  
have to take care that your restrictions *really restrict*.

This is one of the motivations, in the OWL 1.1 submission, of the  
tractable fragments document. There, the syntactic restrictions  
really do result in less complex logics (from the worst case view).

(Of course, SH and SHI are both EXPTIME logics, but I would say that  
SHI is harder to reason with. Not, obviously from a worst case pov,  
but just in that it is easier to state things that are harder to  
reason with in SHI. So, perhaps OWL Lite makes it harder to state  
difficult things (I'ma bit skeptical there).)

Cheers,
Bijan.

Received on Thursday, 8 March 2007 08:28:39 UTC