PSpace Reasoning for DLs with Qualifying Number Restrictions

Stephan TobiesStephan Tobies

Datei:Tobies-LTCS-99-11.ps.gz

Download

Stephan Tobies
PSpace Reasoning for DLs with Qualifying Number Restrictions
Technical Report, LuFG Theoretical Computer Science, RWTH Aachen, volume LTCS-99-11, 1999. LTCS-Report

Details
Bibtex

KurzfassungAbstract
The description logic ALCQI extends the ``standard description logic ALC by qualifying number restrictions and converse roles. We show that concept satisfiability for this DL is still decidable in polynomial space. The presented algorithm combines techniques from [PSPACE Algorithm for Graded Modal Logic] to deal with qualifying number restrictions and from [Reasoning for Description Logics with Functional Restrictions, Inverse and Transitive Roles, and Role Hierarchies] to deal with converse roles. Additionally, we extend the result to ALCQIR which extends ALCQI by role intersections.
Bemerkung: Note: See http://www-lti.informatik.rwth-aachen.de/Forschung/Papers.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ Tobies-LTCS-99-11,
  address = {Germany},
  author = {S. {Tobies}},
  institution = {LuFG Theoretical Computer Science, RWTH Aachen},
  note = {See http://www-lti.informatik.rwth-aachen.de/Forschung/Papers.html.},
  number = {LTCS-99-11},
  title = {{PSpace} Reasoning for {DLs} with Qualifying Number Restrictions},
  type = {LTCS-Report},
  year = {1999},
}