Paper Info
Title
Generalized Complexity of ALC Subsumption
Abstract
The subsumption problem with respect to terminologies in the description logic ALC is EXPTIME-complete. We investigate the computational complexity of fragments of this problem by means of allowed Boolean operators. Hereto we make use of the notion of clones in the context of Post's lattice. Furthermore we consider all four possible quantifier combinations for each fragment parameterized by a clone. We will see that depending on what quantifiers are available the classification will be either tripartite or a quartering.
Year
Venue
Field
2012
arXiv: Logic in Computer Science
Discrete mathematics,Parameterized complexity,Lattice (order),Algorithm,Description logic,Boolean algebra,Mathematics,Computational complexity theory
DocType
Volume
Citations 
Journal
abs/1205.0722
0
PageRank 
References 
Authors
0.34
12
1
Name
Order
Citations
PageRank
Arne Meier112619.00