Description Logics and the Two-Variable Fragment

Carsten LutzCarsten Lutz, Ulrike SattlerUlrike Sattler, Frank WolterFrank Wolter

Datei:LutzSattlerWolter-DL2001.ps.gz

Download

Carsten Lutz, Ulrike Sattler, Frank 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},
}