The Complexity of Satisfiability for Sub-Boolean Fragments of ALC
Preprint
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 family, have an easier satisfiability problem; sometimes it is even tractable. All these fragments restrict the use of Boolean operators in one way or another. We look at systematic and more general restrictions of the Boolean operators and establish the complexity of the concept satisfiability problem in the presence of axioms. We separate tractable from intractable cases.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- The Complexity of Generalized Satisfiability for Linear Temporal Logic2007
- EXPtime tableaux for ALCArtificial Intelligence, 2000
- Using automata theory for characterizing the semantics of terminological cyclesAnnals of Mathematics and Artificial Intelligence, 1996
- The complexity of existential quantification in concept languagesArtificial Intelligence, 1992
- Attributive concept descriptions with complementsArtificial Intelligence, 1991
- Terminological reasoning is inherently intractableArtificial Intelligence, 1990
- Automata-theoretic techniques for modal logics of programsJournal of Computer and System Sciences, 1986
- Satisfiability problems for propositional calculiTheory of Computing Systems, 1979
- A practical decision method for propositional dynamic logic (Preliminary Report)1978
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)1942