Re: OWL complexity (WRT FOPL)

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