[DL] Decision problems of DL vs. FOL

Steve W s.wong.731 at gmail.com
Wed Jun 2 14:46:04 CEST 2010


If I understand correctly, DL handles only unary and binary predicates -- is
that supposed to be a limitation? Any n-ary predicates can be encoded as
binary ones, e.g., F(a,G(b,c)), right?

On Wed, Jun 2, 2010 at 8:33 AM, Thomas Schneider <schneidt at cs.man.ac.uk>wrote:

> The reason is that most DLs can be embedded into FOL.
>
>
But, can any FOL formula be translated to DL?

Thanks for the pointer.
Steve


> 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
>
>
>
>
>
>
>
>
> ---
> **  You received this mail via the description logic mailing list; for more
>  **
> **  information, visit the description logic homepage at http://dl.kr.org/.
>  **
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.informatik.uni-bremen.de/pipermail/dl/attachments/20100602/c94daf40/attachment.html>


More information about the dl mailing list