A PSpace-algorithm for ALCQI-satisfiability

Stephan TobiesStephan Tobies

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

Download

Stephan Tobies
A PSpace-algorithm for ALCQI-satisfiability
Technical Report, LuFG Theoretical Computer Science, RWTH Aachen, volume LTCS-99-09, 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.
Bemerkung: Note: See http://www-lti.informatik.rwth-aachen.de/Forschung/Papers.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ Tobies-LTCS-99-09,
  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-09},
  title = {A {PSpace}-algorithm for {ALCQI}-satisfiability},
  type = {LTCS-Report},
  year = {1999},
}