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

Received on Tuesday, 6 March 2007 21:41:48 UTC