- From: Bijan Parsia <bparsia@cs.man.ac.uk>
- Date: Mon, 5 Mar 2007 16:36:44 +0000
- To: Michael Schneider <m_schnei@gmx.de>
- Cc: matthew.williams@cancer.org.uk, semantic-web@w3.org, public-owl-dev@w3.org
In addition to Uli's wise words, 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. 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). 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> 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. Cheers, Bijan.
Received on Monday, 5 March 2007 16:36:16 UTC