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

On Feb 3, 2006, at 7:12 PM, Bernardo Cuenca Grau wrote:

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

[snip]
Other operators, greatest and least fixed point (which allow you to 
define transclosure), and various nonmonotonic extensions (including 
default rules and the K and A operators).

One thing that may be confusing you is the word "beyond". They authors 
did not mean to suggest that an arbitrary DL + transclos has *all* the 
expressivity of FOL and then some more. Rather, the addition of such 
operators allows those DLs to express things which cannot be expressed 
in FOL (but there's plenty of things that FOL can express that they, 
even so juiced up, cannot).

Another way to think of it is that such DLs are a subset of (FOL + the 
addition non-first order expressivity).

Cheers,
Bijan.

Received on Saturday, 4 February 2006 03:04:38 UTC