Generalized Satisfiability for the Description Logic ALC

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 unrestricted axioms. Several fragments of ALC, notably logics in the FL, EL, and DL-Lite families, have an easier satisfiability problem; sometimes it is even tractable. We classify the complexity of the standard satisfiability problems for all possible Boolean and quantifier fragments of ALC in the presence of general axioms.

Technical Report with complete Proofs, Conference Version appeared in TAMC2011

References in corpus (4)

• The DL-Lite Family and Relations
• The Complexity of Propositional Implication
• The Complexity of Satisfiability for Fragments of Hybrid Logic -- Part I
• The Complexity of Satisfiability for Sub-Boolean Fragments of ALC

Cited by in corpus (2)

• Generalized Complexity of ALC Subsumption
• On the complexity of the clone membership problem