Journal Article

PSpace Reasoning with the Description Logic AℒCF(D)

Carsten Lutz

in Logic Journal of the IGPL

Volume 10, issue 5, pages 535-568
Published in print September 2002 | ISSN: 1367-0751
Published online September 2002 | e-ISSN: 1368-9894 | DOI: http://dx.doi.org/10.1093/jigpal/10.5.535
PSpace Reasoning with the Description Logic AℒCF(D)

Show Summary Details

Preview

Description Logics (DLs), a family of formalisms for reasoning about conceptual knowledge, can be extended with concrete domains to allow an adequate representation of “concrete qualities” of real-worlds entities such as their height, temperature, duration, and size. In this paper, we study the complexity of reasoning with the basic DL with concrete domains AℒC(D) and its extension with so-called feature agreements and disagreements AℒCF(D). We show that, for both logics, the standard reasoning tasks concept satisfiability, concept subsumption, and ABox consistency are PSpace-complete if the concrete domain D satisfies some natural conditions.

Keywords: Description Logics, Concrete Domains, Feature (Dis)Agreements, Computational Complexity

Journal Article.  0 words. 

Subjects: Logic

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.