From: Vaughan Pratt <pratt@cs.stanford.edu>

Date: Mon, 05 Mar 2007 09:21:39 -0800

Message-ID: <45EC51A3.5080001@cs.stanford.edu>

CC: semantic-web@w3.org, public-owl-dev@w3.org

Date: Mon, 05 Mar 2007 09:21:39 -0800

Message-ID: <45EC51A3.5080001@cs.stanford.edu>

CC: semantic-web@w3.org, public-owl-dev@w3.org

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. The negation of a predicate simply complements its truth value. Lifting logical connectives to the status of operations on sets and classes is a delicate business. An early step to take when making that move is to trust relative complement but not absolute complement of a set or class. 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. Vaughan PS. I'm very much enjoying the fractal discussion, but have been resisting the strong temptation to participate.Received on Monday, 5 March 2007 17:22:04 UTC

*
This archive was generated by hypermail 2.3.1
: Tuesday, 6 January 2015 20:58:14 UTC
*