Mary likes all Cats

C. LutzC. Lutz, U. SattlerU. Sattler

Datei:LutzSattler-DL-2000.ps.gz

Download

C. Lutz, U. 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},
}