- From: Bijan Parsia <bparsia@cs.man.ac.uk>
- Date: Mon, 5 Mar 2007 18:20:47 +0000
- To: pratt@cs.stanford.edu
- Cc: public-owl-dev@w3.org, semantic-web@w3.org

On 5 Mar 2007, at 17:21, Vaughan Pratt wrote: > Bijan Parsia wrote: >> 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> > > The difficulty with negation arises when passing from predicates to > classes. I don't see that at all. I'm not sure what you mean by "predicates" and "classes" here. In DLs, classes generally refer to one place predicates (consider the obvious model theoretic intepretation). > The negation of a predicate simply complements its truth value. Er... \forall(x)(C(x) \leftarrow \neg D(x)). The predicate doesn't have a truth value. > Lifting logical connectives to the status of operations on sets > and classes is a delicate business. I don't know why you put it this way. That is, I don't see any additional insight and some confusion. General negation is powerful and thus difficult. Having it allows for some nice interdefinability. > An early step to take when making that move is to trust relative > complement but not absolute complement of a set or class. "Trust" is strong, but in any case, I still fail to see that you've said anything different except, to my mind, in more confusing terms. > In the standard (Fischer-Ladner) semantics of propositional dynamic > logic, propositional negation of P is interpreted as the complement > of the set of worlds in which P holds *relative to* a specified > *set* W of all possible worlds constituting the underlying set of > the Kripke structure. If your semantics has that form then you are > on safe ground with negation. If however it just has the intuitive > meaning of "everything else" then you leave yourself wide open to > the problems of impredicativity such as Russell's Paradox. Uh, I'm very skeptical about this last bit, though I'm no PDL person. <http://www.springerlink.com/content/cf40guhq1m5t6lpu/> <http://www.sciencedirect.com/science? _ob=MImg&_imagekey=B6WJ0-4B55K9J- G-5&_cdi=6864&_user=494590&_orig=browse&_coverDate=04%2F30% 2F1979&_sk=999819997&view=c&wchp=dGLbVlb- zSkzS&md5=e6986bd20377ddee8f055be2886a8368&ie=/sdarticle.pdf> <http://www.csc.liv.ac.uk/~dirk/paper/mthesis-dirkwalther.pdf> PDL with arbitrary negation of programs (i.e., arbitrary negation of role expressions) is undecidable, but that's hardly the same thing as allowing for paradoxes. I'd be interested in your construction of the Russell's paradox in PDL^-. Atomic negation, on the other hand, seems ok. But restriction to atomic negation and restriction to disjointness are not quite the same thing. Ok, this is a distraction now :) Cheers, Bijan.

Received on Monday, 5 March 2007 18:21:17 UTC