On the Relative Expressiveness of Description Logics and Predicate Logics

Borgida

first order logic description complexity decidability two-variable

@article{borgida:aij-1996,
  title={On the Relative Expressiveness of Description Logics and Predicate Logics},
  author={Borgida, A.},
  journal={Artificial Intelligence},
  volume={82},
  number={1-2},
  pages={353--367},
  year={1996}
}

Even for more expressive DLs, only encompasses fragment of first order logic expressible in three variables

• Providing a clear boundary on the limits of their expressiveness---they cannot express all things

Example of non-atomic role: grandsons \equiv compose[children, restrict[children, MALE]]

Core expressiveness results:

• The description logic language DL consists of top, nothing, and, or, not, all, some, at-least, at-most, at-least-c, at-most-c, same-as, subset, not-same-as, fills, one-of, top-role, identity, role-and, role-or, role-not, inverse, restrict, compose, product, trans
• The description logic language DL-{trans, compos,; at-least, at-most} and L^2 are equivalent
• The description logic language DL-{trans, at-least, at-most,} and L^3 are equivalent

Corollaries

• Cannot express 4-clique
• compose cannot be constructed from other language elements
• Subsumption is decidable for DL without trans, compos, at-least, at-most
• Undecidable for DL without trans, at-least, at-most
• DL-{trans,compose} is equivalent to L^2_{CNT}
  • Which is decidable, correct?
• DL-{trans} is equivalent to L^3_{CNT}

Alternate proof path: ALC is equivalent to a modal logic, which in turn can be expressed in L2, which can in turn be expressed in a modal logic

• These are not necessarily the same modal logics

There are applications requiring terminological reasoning which DL constructors simply cannot represent

DLs are likely insufficient as query languages over a database, etc. since they have limited expressiveness

• Even the least powerful query languages are more expressive and decidability
  • Due to operating over finite model?