Related resources
Search for item elsewhere
University researcher(s)
Academic department(s)
The Complexity of Satisfiability for Sub-Boolean Fragments of ALC
A. Meier and T. Schneider
In: DL 2010; Waterloo, Ontario, Canada. 2010.
Access to files
-
FULL-TEXT.PDF (pdf)
-
SUPPLEMENTARY-1.PDF (pdf)
Abstract
The standard reasoning problem, concept satisfiability, in the basic description logic ALCis 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.All these fragments restrict the use of Boolean operators in one way or another.We look at systematic and more general restrictionsof the Boolean operators and establish the complexity of the concept satisfiability problemin the presence of axioms. We separate tractable from intractable cases.