Subsumption of concepts in DL FL0 for (cyclic) terminologies with respect to descriptive semantics is PSPACE−complete
Yevgeny Kazakov and Hans de Nivelle
Abstract
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
Address
Stuhlsatzenhausweg 85‚ 66123 Saarbrücken‚ Germany
Institution
Max−Planck−Institut für Informatik
ISSN
0946−011X
Month
April
Number
MPI−I−2003−2−003
Year
2003