{PSpace} Reasoning for {DLs} with Qualifying Number Restrictions

S. TobiesS. Tobies

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

Download

S. 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 <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. 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},
}