Re: Question on DL negation

Michael

Your BTW3 really intrigues me.  You say that "disjointness" increases the 
"complexity" of a DL, presumably a "bad" thing.

In real-world concept formation, all species of a genus are disjoint,
and I believe this is a "good" thing -- a major factor contributing to the
"simplicity" and the "power"of hierarchical classification.
Perhaps it's only partial disjointness that is "bad"?
I consider any intersection between species to be "bad".

Dick McCullough
mKE do enhance od "Real Intelligence" done;
knowledge := man do identify od existent done;
knowledge haspart proposition list;
http://mKRmKE.org/


----- Original Message ----- 
From: "Michael Schneider" <m_schnei@gmx.de>
To: <bparsia@cs.man.ac.uk>
Cc: <matthew.williams@cancer.org.uk>; <semantic-web@w3.org>; 
<public-owl-dev@w3.org>
Sent: Tuesday, March 06, 2007 1:41 PM
Subject: Re: Question on DL negation


>
> Hi, Bijan!
>
> It took me some time to work through your last answer. :) And there are 
> still open points, which I do not completely understand. Perhaps, you can 
> help me again. First this one:
>
>> In addition to Uli's wise words,
>
> Hm, did I overlook a mail? Who is Uli, and what were his words of wisdom? 
> :)
>
>> I, as usual, recommend the  description logic complexity navigator:
>> http://www.cs.man.ac.uk/~ezolin/logic/complexity.html
> > You can see by playing around with combinations of the role
> > constructors the effects on complexity.
>
> Thanks a lot, I really did not know this site. This is really an expert 
> tool. I, by far, do not understand everything there, but at least, I 
> should now be able to answer myself my original question by marking the 
> respectively checkboxes on this form.
>
>   1) hitting the "OWL1.1" button in the RBox cell
>
> Ok, as expected, "the ABox consistency problem" is "decidable".
>
>   2) checking "role intersection", "role union" and "role complement"
>      in the "Role constructors" cell
>
> Now, for every combination of those three role constructors, I get a 
> complexity "NExpTime-hard". Probably bad from a complexity point of view, 
> but at least still decidable, right? The question is, what this result 
> means for practical ontologies, because all those complexity 
> classifications always only regard worst case scenarios.
>
> BTW1: Why is the complexity classification for the combination "OWL1.1 
> plus role constructors" more specific ("NExpTime-hard") than for OWL1.1 
> alone (just "decidable")? OWL1.1 is a sublanguage of the 
> OWL1.1+constructors language, so OWL1.1 should have "NExpTime-hard" as an 
> upper bound.
>
> BTW2: There is a "role chain" entry in the "Role constructors" cell. 
> Shouldn't it be getting checked, when I press the "OWL1.1" button? That's 
> one of the new features of OWL1.1, AFAIK. Currently, this checkbox keeps 
> unchecked. When I check it manually, the complexity again changes to 
> "NExpTime-hard".
>
> BTW3: I cannot see a feature "disjointness", neither for concepts, nor for 
> roles. Doesn't the addition of disjointness adds significantly to the 
> complexity of a DL? I thought that at least it would, when adding concept 
> disjointness to OWL-Lite. Or can disjointness be expressed in terms of the 
> other mentioned features? At least, I do not see how this were possible 
> for /role/ disjointness, when only having the features of OWL1.0.
>
>> Remember that all this is just (a fragment of) FOL (well, except if  you 
>> add transitive closure per se), so all the constructors are just  normal 
>> propositional (for the most part) connectives on binary  predicates.
>>
>> Expressive role constructors are associated with propositional  dynamic 
>> logic (and converse propositional dynamic logic).
>
> I haven't dealt with "dynamic logic" so far, so I am not able to 
> understand this. But I am going to read about it, when I find the time (I 
> see Wikipedia has an article).
>
>> It's also instructive to see how arbitrary concept negation is 
>> difficult. You can see in the tractable fragments document that most  of 
>> them allow concept (i.e., restricted) disjointness:
>> <http://www.cs.man.ac.uk/~ezolin/logic/complexity.html>
>
> Is this the correct link? This is the same as above (the DL complexity 
> tool), but you said something about a "tractable fragments document".
>
>> Lots of recent work (e.g., on modularity, the EL family, and ABox 
>> summarization) suggests strongly that unrestricted universal 
>> quantification and negation make things difficult. If you can control 
>> them in a number of ways (either by analysis or by linguistic 
>> restrictions) you can get better behavior.
>
> I do not understand this last paragraph.
>
> Anyway, thanks for citing the above really cool tool. I probably will play 
> around with it again. Hopefully, this will keep me from reading a complete 
> boring book on description logics! ;-)
>
>
> Cheers,
> Michael
>
>
Dick McCullough
mKE do enhance od "Real Intelligence" done;
knowledge := man do identify od existent done;
knowledge haspart proposition list;
http://mKRmKE.org/

Received on Tuesday, 6 March 2007 23:45:05 UTC