Re: [Pellet-Users] OWL complexity (WRT FOPL)

> 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):

 Typically DLs are indeed proper fragments of FOL. OWL-DL is a fragment of
FOL. However, some DLs include operators that are not first order, such as
transitive closure, as you mention in the quote below.

>
> "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.

 No, transitive closure is more expressive than transitive roles. What the
quote above is saying is that defining a relation as transitive can be
done in FOL. For example, ``locatedIn'': if Paris is located in France and
France is located in Europe, then Paris is located in Europe. This is the
kind of transitivity that is available in OWL-DL

 However, the transitive closure of a role is the SMALLEST transitive
relation including R. It is the ``smallest'' condition that is not
expressible in FOL. FOr example:

 queen = woman \and (\forall child.(prince \or \princess)) \and (\forall
child^+ noble)

 where child^+ is the transitive closure of the ``child'' relation. The
above axiom defines a queen as a woman whose children are princes or
princesses and whose descendants are nobles. This cannot be expressed if
we used the transitive role ``descendants'' instead of child^+, since
we cannot distinguish between different levels of ``depth'' in the
parental hierarchy.


 Hope this helps

 Bernardo

>
> 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
> _______________________________________________
> Pellet-Users mailing list
> Pellet-Users@lists.mindswap.org
> http://lists.mindswap.org/mailman/listinfo/pellet-users
>

Received on Saturday, 4 February 2006 00:12:39 UTC