{\sc PSpace} Reasoning with the Description Logic $\mathcal{ALCF}(\mathcal{D})$

C. LutzC. Lutz

Datei:Lutz-IGPL02.ps.gz

Download

C. Lutz
{\sc PSpace} Reasoning with the Description Logic $\mathcal{ALCF}(\mathcal{D})$
Logic Journal of the IGPL, 10(5):535--568, 2002

Details
Bibtex

KurzfassungAbstract
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 ALC(D) and its extension with so-called feature agreements and disagreements ALCF(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.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ Lutz-IGPL02,
  author = {C. {Lutz}},
  journal = {Logic Journal of the IGPL},
  number = {5},
  pages = {535--568},
  title = {{\sc PSpace} Reasoning with the Description Logic $\mathcal{ALCF}(\mathcal{D})$},
  volume = {10},
  year = {2002},
}