A {PSpace}-algorithm for {ALCQI}-satisfiability

S. TobiesS. Tobies

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

Download

S. 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 <A HREF=http://www-lti.informatik.rwth-aachen.de/Forschung/Papers-1999.html#Tobies-CADE-99>A PSPACE Algorithm for Graded Modal Logic</A> to deal with qualifying number restrictions and from <A HREF=http://www-lti.informatik.rwth-aachen.de/Forschung/Papers-1999.html#HorrocksSattlerTobies-M4M-99>Practical Reasoning for Description Logics with Functional Restrictions, Inverse and
Transitive Roles, and Role Hierarchies</A> 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},
}