- From: Richard H. McCullough <rhm@PioneerCA.com>
- Date: Tue, 6 Mar 2007 15:37:37 -0800
- To: "Michael Schneider" <m_schnei@gmx.de>, <bparsia@cs.man.ac.uk>
- Cc: <matthew.williams@cancer.org.uk>, <semantic-web@w3.org>, <public-owl-dev@w3.org>
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