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
April 2003, 12 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-2003-2-003.ps (277 KBytes)
URL to this document: https://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},
}