W3C home > Mailing lists > Public > semantic-web@w3.org > February 2006

Re: OWL complexity (WRT FOPL)

From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
Date: Fri, 03 Feb 2006 17:47:31 -0500 (EST)
Message-Id: <20060203.174731.82112531.pfps@research.bell-labs.com>
To: matthew.williams@cancer.org.uk
Cc: pellet-users@lists.mindswap.org, jena-dev@yahoogroups.com, semantic-web@w3.org

From: Matt Williams <matthew.williams@cancer.org.uk>
Subject: OWL complexity (WRT FOPL)
Date: Fri, 03 Feb 2006 20:30:48 +0000

> Dear List,
> My apologies for such a random question (and for cross-posting - I'm not 
> sure who might best answer this): I'm trying to tie down the 
> expressibility of OWL.
> I had generally thought that DLs were _less_ expressive than FOPL (see 
> for example, {A.Borginda AI(82) 1996} . However, I had a nagging thought 
> that this wasn't always true, and sure enough, I found something from 
> the DL-handbook (chap. 4):
> "In contrast, the expressive power of a Description Logic including the 
> transitive closure of roles goes beyond first order logic: First, it is 
> easy to see that expressing transitivity (?+ (x, y ) ? ?+ (y , z )) ?
> ?+ (x, z ) involves at least three variables. To express that a relation 
> ?+ is the transitive closure of ?, we first need to enforce that ?+ is a 
> transitive relation including ? which can easily be axiomatized in first 
> order predicate logic. Secondly, we must enforce that ?+ is the smallest 
> transitive relation including ? which, as a consequence of the 
> Compactness Theorem, cannot be expressed in first order logic."
> Now, I have little idea what much of what the last few sentences mean, 
> but the suggestion is that a DL with transitive roles is beyond FOPL. In 
> that case, is OWL? As I understand it, OWL has transitive closure, and 
> so should be.

OWL does not have transitive *closure*.  It does have transitive roles, but
that is a different kettle of fish.

> If anyone can clarify this, I would be _most_ grateful.
> The refs. were both from Franconi's DL site.
> Thanks a lot,
> Matt

Of course, OWL Full has some aspects that are not what one might call
first-order but OWL DL eliminates these aspects.

Peter F. Patel-Schneider
Bell Labs Research
Received on Friday, 3 February 2006 22:47:52 UTC

This archive was generated by hypermail 2.4.0 : Tuesday, 5 July 2022 08:44:55 UTC