Paper Info
Title
On the Complexity of Counting in Description Logics
Abstract
Many Description Logics (DLs) allow for counting expressions of various forms that are important in many applications, e.g., for reasoning with seman- tic 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 is decidable in PSPACE even if binary coding of numbers in the input is assumed. (2) We prove that TBox consistency for with cardinality re- strictions is NE XPTIME-complete.
Year
Venue
Keywords
1999
Description Logics
description logic,data model,satisfiability
Field
DocType
Citations 
T-norm fuzzy logics,Computer science,Description logic,Theoretical computer science,Monoidal t-norm logic
Conference
1
PageRank 
References 
Authors
0.38
12
1
Name
Order
Citations
PageRank
Stephan Tobies11599158.86