Re: Question on DL negation

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