Mary likes all Cats

Carsten Lutz, Ulrike Sattler
Mary likes all Cats
In F. Baader and U. Sattler, eds., Proceedings of the 2000 International Workshop in Description Logics (DL2000), CEUR-WS, 213-226, August 2000. RWTH Aachen

Details
Bibtex

KurzfassungAbstract
We investigate the complexity of ALC with boolean operators on roles. Tight complexity bounds are given for all logics between ALC with role negation and ALC with full boolean operators on accessibility relations (also considering restrictions to atomic role negation). More precisely, our main results are tight bounds for
(1) ALC with role negation (which turns out to be ExpTime-complete), (2) ALC with atomic role negation and role intersection (which turns out to be NExpTime-complete, just like ALC with all boolean operators on roles).
Moreover, in order to demonstrate the generality of our results, we show that the automata based techniques that were employed to obtain the upper bound for (1) can be extended to obtain the same result for ALC extended with both transitive roles and negation of roles.
Bemerkung: Note: Proceedings online available from http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-33/
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ LutzSattler-DL-2000,
  address = {Aachen, Germany},
  author = {C. {Lutz} and U. {Sattler}},
  booktitle = {Proceedings of the 2000 International Workshop in Description Logics {(DL2000)}},
  editor = {F. {Baader} and U. {Sattler}},
  month = {August},
  note = {Proceedings online available from {http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-33/}},
  number = {33},
  pages = {213--226},
  publisher = {RWTH Aachen},
  series = {CEUR-WS},
  title = {Mary likes all Cats},
  year = {2000},
}

Mary likes all Cats

Mary likes all Cats

Carsten LutzCarsten Lutz, Ulrike SattlerUlrike Sattler