[DL] Decision problems of DL vs. FOL

[Thomas Schneider]

Hi Steve,

you're right that each standard decision problem in DL is a special  
case of some decision problem in FOL. The reason is that most DLs can  
be embedded into FOL. What the article means with "more efficient" is  
the following. While, for instance, the satisfiability problem in FOL  
is undecidable, it is decidable in standard DLs. For most of them it  
is still of high complexity, so the word "efficient" seems a bit  
problematic in that sentence. However, there are DLs for which the  
standard decision problems are efficiently decidable in a stronger  
sense, e.g., for the EL and DL-Lite family which correspond to the OWL  
fragments EL and QL.

You can find more information about the relation between DLs and FOL,  
and about the complexity of reasoning in Sections 2.2.1.3, 3, 4.2 of  
[1].

[1] F. Baader et al., The Description Logic Handbook, 2nd edition,  
Cambridge University Press, 2007.

Cheers

Thomas

On 30 May 2010, at 02:38, Steve W wrote:

> Hi all,
>
> According to the Wikipedia article on DL, it says that the decision  
> problems are more efficient than those of FOL. Are DL decision  
> problems not equivalent to those in FOL? For example, isn't  
> subsumption checking equivalent to checking implication? Is instance  
> checking not equivalent to evaluating the truth value of a predicate  
> given a constant? Assuming what I said is correct, then do all  
> decision problems of DL have an equivalent form in FOL? Which  
> problems of FOL are not supported by DL?
>
> Thanks for any input.
>
> Cheers,
> Steve
> ---
> **  You received this mail via the description logic mailing list;  
> for more  **
> **  information, visit the description logic homepage at http://dl.kr.org/ 
> .  **

+----------------------------------------------------------------------+
|  Dr Thomas Schneider                    schneider (at) cs.man.ac.uk  |
|  School of Computer Science       http://www.cs.man.ac.uk/~schneidt  |
|  Kilburn Building, Room 2.114                 phone +44 161 2756136  |
|  University of Manchester                                            |
|  Oxford Road                                             _///_       |
|  Manchester M13 9PL                                      (o~o)       |
+-----------------------------------------------------oOOO--(_)--OOOo--+

Prague (vb.)
   To declaim loudly and pompously upon any subject about which the
   speaker has less knowledge than at least one other person at the
   table.

                   Douglas Adams, John Lloyd: The Deeper Meaning of Liff







-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 203 bytes
Desc: This is a digitally signed message part
URL: <http://mailman.zih.tu-dresden.de/pipermail/dl/attachments/20100602/9717561d/attachment.sig>