DL FL0 for (cyclic) terminologies with respect to descriptive semantics is PSPACE−complete"/> Department of Computer Science, University of Oxford: Publication - Subsumption of concepts in <span style="font-family: serif">DL</span> <span style="font-family: serif"><span style="font-family: cursive; text-transform: uppercase; font-style: italic">FL</span><sub style="font-style: normal">0</sub></span> for (cyclic) terminologies with respect to descriptive semantics is PSPACE−complete
University of Oxford Logo University of OxfordDepartment of Computer Science - Home

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

Details

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

Links

BibTeX

Related pages

People

Yevgeny Kazakov

Activities

Knowledge Representation and Reasoning