On the Complexity of Counting in Description Logics

From International Center for Computational Logic

Toggle side column

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
  • 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},
}