Re: Question on DL negation

Hi, Dick!

Richard H. McCullough wrote on Tue, 6 Mar 2007:

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

I wrote:

>> 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.

By "complexity", I really meant /computational/ complexity, in the sense 
of:

   http://en.wikipedia.org/wiki/Computational_complexity_theory

This is a general runtime (or space) measure for a given computational 
problem.

The complexity navigator at

   http://www.cs.man.ac.uk/~ezolin/logic/complexity.html

which Bijan pointed me to, shows the computational complexity (if 
already known) for the (computational) problem of deciding, if a given 
ontology is satisfiable or not. You can choose the different language 
features of the description logic you are interested in, and then you 
can see how the complexity class changes.

Adding some language feature to a given language, for instance the 
feature "class disjointness" to OWL-Lite, always has the /potential/ to 
increase the computational complexity of the satisfiability problem, 
because every reasoner for the augmented language (OWL-Lite+disj) now 
has to solve this problem for all possible ontologies of the old 
language (OWL-Lite) PLUS all those ontologies which contain the 
additional language feature (disjointness axioms). But such an increase 
in complexity doesn't always happen, I just /supposed/ that this was the 
case for the step from OWL-Lite to OWL-Lite+disjointness.

Unluckily, I cannot check this with the navigator, because there is no 
such "concept disjointness" checkbox. It seems that all I can do is 
comparing the complexity classes of OWL-Lite and OWL-DL, which is an 
upper-language of OWL-Lite+disj:

    * Complexity( OWL-Lite )  = ExpTime (complete)
    * Complexity( OWL-DL )    = NExpTime (complete)

And according to

    http://en.wikipedia.org/wiki/EXPTIME

it is currently unknown if ExpTime and NExpTime are different or not 
(most probably different, so this approach does not really provide me 
much help).

Anyway, you see now that I had a very specific (and very technical) 
notion of "complexity" in mind.

> 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".

But you can use DLs like OWL to model whatever you want, not only 
"natural species". And when comparing two general concepts, you cannot 
simply assume disjointness (it would often be wrong), you instead have 
to explicitly demand it, by adding a disjointness axiom. But, perhaps, I 
misunderstood, what you meant here?

Cheers,
Michael

Received on Wednesday, 7 March 2007 14:24:06 UTC