Generalized Satisfiability for the Description Logic A.CC (Extended Abstract)

摘要

The standard reasoning problem, concept satisfiability, in the basic description logic ACC is PSPACE-complete, and it is EXPTIME-complete in the presence of unrestricted axioms. Several fragments of ALC, notably logics in the FL, εL, and DL-Lite families, have an eas ier satisfiability problem; sometimes it is even tractable. We classify the complexity of the standard satisfiability problems for all possible Boolean and quantifier fragments of ACC in the presence of general axioms.