Thomas Schneider

  1. The Complexity of Satisfiability for Sub-Boolean Fragments of ALC.

    Authors: Arne Meier, Thomas Schneider
    Subjects: Logic in Computer Science
    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.

Syndicate content