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

OWL complexity (WRT FOPL)

From: Matt Williams <matthew.williams@cancer.org.uk>
Date: Fri, 03 Feb 2006 20:30:48 +0000
Message-ID: <43E3BD78.1050504@cancer.org.uk>
To: Pellet <pellet-users@lists.mindswap.org>, jena-dev@yahoogroups.com, Semantic Web <semantic-web@w3.org>

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.

If anyone can clarify this, I would be _most_ grateful.

The refs. were both from Franconi's DL site.

Thanks a lot,
Matt

-- 
Dr. M. Williams MRCP(UK)
Clinical Research Fellow,
Cancer Research UK
+44 (0)7834 899570
Received on Friday, 3 February 2006 20:46:28 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 07:41:49 UTC