MPI-I-2003-2-003

Subsumption of concepts in $DL$ $\cal FL_0$ for (cyclic) terminologies with respect to descriptive semantics is PSPACE-complete

Kazakov, Yevgeny and de Nivelle, Hans

MPI-I-2003-2-003. April 2003, 12 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We prove the PSPACE-completeness of the subsumption problem for(cyclic) terminologies with respect to descriptive semantics in a simple Description Logic ${\cal FL}_0$, which allows for conjunctions and universal value restrictions only, thus solving the problem which was open for more than ten years.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	277 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-2-003

BibTeX
@TECHREPORT{KazakovNivelle2003, AUTHOR = {Kazakov, Yevgeny and de Nivelle, Hans}, TITLE = {Subsumption of concepts in $DL$ ${\cal FL}_0$ for (cyclic) terminologies with respect to descriptive semantics is PSPACE-complete}, TYPE = {Research Report}, INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik}, ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany}, NUMBER = {MPI-I-2003-2-003}, MONTH = {April}, YEAR = {2003}, ISSN = {0946-011X},}