Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434528 | Theoretical Computer Science | 2013 | 19 Pages |
Abstract
The standard reasoning problem, concept satisfiability, in the basic description logic ALC is PSpace-complete, and it is ExpTime-complete in the presence of general concept inclusions. Several fragments of ALC, notably logics in the FL, EL, and DL-Lite families, have an easier satisfiability problem; for some of these logics, satisfiability can be decided in polynomial time. We classify the complexity of the standard variants of the satisfiability problem for all possible Boolean and quantifier fragments of ALC with and without general concept inclusions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics