Description Logics and the Two-Variable Fragment

C. LutzC. Lutz, U. SattlerU. Sattler, F. WolterF. Wolter

Datei:LutzSattlerWolter-DL2001.ps.gz

Download

C. Lutz, U. Sattler, F. Wolter
Description Logics and the Two-Variable Fragment
In D.L. {McGuiness} and P.F. {Pater-Schneider} and C. {Goble} and R. {Möller}, eds., Proceedings of the 2001 International Workshop in Description Logics {(DL-2001)}, 66--75, 2001

Details
Bibtex

KurzfassungAbstract
We present a description logic L that is as expressive as the two-variable
fragment of first-order logic and differs from other logics with this property in that it encompasses solely standard role- and concept-forming operators. The description logic L is obtained from ALC by adding full Boolean operators on roles, the inverse operator on roles and an identity role. It is proved that L has the same expressive power as the two-variable fragment FO^2 of first-order logic by presenting a translation from FO^2-formulae into equivalent L-concepts (and back). Additionally, we discuss an interesting complexity phenomenon: both L and FO^2 are NExpTime-complete and so is the restriction of FO^2 to finitely many relation symbols; astonishingly,
the restriction of L to a bounded number of role names is in ExpTime.
Bemerkung: Note: Proceedings online available from {http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/}
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ LutzSattlerWolter-DL2001,
  address = {Stanford, California, USA},
  author = {C. {Lutz} and U. {Sattler} and F. {Wolter}},
  booktitle = {Proceedings of the 2001 International Workshop in Description Logics {(DL-2001)}},
  editor = {D.L. {McGuiness} and P.F. {Pater-Schneider} and C. {Goble} and R. {M{\"o}ller}},
  note = {Proceedings online available from {http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/}},
  pages = {66--75},
  title = {Description Logics and the Two-Variable Fragment},
  year = {2001},
}