The complexity of satisfiability for sub-boolean fragments of ALC

Arne Meier, Thomas Schneider

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    25 Downloads (Pure)

    Abstract

    The standard reasoning problem, concept satisfiability, in the basic description logic ALC is PSPACE-complete, and it is EXPTIMEcomplete 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 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.
    Original languageEnglish
    Title of host publicationCEUR Workshop Proceedings|CEUR Workshop Proc.
    Pages279-290
    Number of pages11
    Volume573
    Publication statusPublished - 2010
    Event23rd International Workshop on Description Logics, DL 2010 - Waterloo, ON
    Duration: 1 Jul 2010 → …

    Conference

    Conference23rd International Workshop on Description Logics, DL 2010
    CityWaterloo, ON
    Period1/07/10 → …

    Fingerprint

    Dive into the research topics of 'The complexity of satisfiability for sub-boolean fragments of ALC'. Together they form a unique fingerprint.

    Cite this