[DL] Decision problems of DL vs. FOL

Peter Frederick Patel-Schneider pfps at research.bell-labs.com
Tue Jun 1 20:17:58 CEST 2010

It probably would be better to say "easier" decision problems than FOL,
and, even then, provide caveats, or, better, to rewrite the entire
introductory part of the page.   Most description logics have decidable
inference, and thus are decidably easier than FOL.

However, the beauty of Wikipedia is that anyone can make improvements to
most pages.  Feel free to do so.


From: Steve W <s.wong.731 at gmail.com>
Subject: [DL] Decision problems of DL vs. FOL
Date: Sat, 29 May 2010 20:38:31 -0500

> 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

More information about the dl mailing list