On the Complexity of Counting in Description Logics
From International Center for Computational Logic
On the Complexity of Counting in Description Logics
Stephan TobiesStephan Tobies
Stephan Tobies
On the Complexity of Counting in Description Logics
In P. Lambrix and A. Borgida and M. Lenzerini and R. Möller and P. Patel-Schneider, eds., Proceedings of the International Workshop on Description Logics 1999 (DL'99), CEUR-WS, 1999. Linköping University
On the Complexity of Counting in Description Logics
In P. Lambrix and A. Borgida and M. Lenzerini and R. Möller and P. Patel-Schneider, eds., Proceedings of the International Workshop on Description Logics 1999 (DL'99), CEUR-WS, 1999. Linköping University
- KurzfassungAbstract
Many Description Logics (DLs) allow for counting expressions of various forms that are important in many applications, e.g., for reasoning with semantic data models and for applications concerned with the configuration of technical systems. We present two novel complexity results for DLs that contain counting constructs: (1) We prove that concept satisfiability for ALCQI is decidable in PSPACE even if binary coding of numbers in the input is assumed. (2) We prove that TBox consistency for ALCQI with cardinality restrictions is NEXPTIME-complete. - Bemerkung: Note: Proceedings online available from http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-22/
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Tobies-DL-1999,
address = {Sweden},
author = {S. {Tobies}},
booktitle = {Proceedings of the International Workshop on Description Logics 1999 (DL'99)},
editor = {P. {Lambrix} and A. {Borgida} and M. {Lenzerini} and R. {M{\"o}ller} and P. {Patel-Schneider}},
note = {Proceedings online available from {http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-22/}},
number = {22},
publisher = {Link{\"o}ping University},
series = {CEUR-WS},
title = {On the Complexity of Counting in Description Logics},
year = {1999},
}
