# Subsumption of concepts in DLFL0 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