- From: Michael Schneider <m_schnei@gmx.de>
- Date: Tue, 06 Mar 2007 22:41:40 +0100
- To: bparsia@cs.man.ac.uk
- CC: matthew.williams@cancer.org.uk, semantic-web@w3.org, public-owl-dev@w3.org

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:46 UTC