Subsumption of Concepts in FL0 for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE−complete.
Yevgeny Kazakov and Hans de Nivelle
We close the gap in the complexity classification of subsumption in the simple description logic \cal FL_0, which allows for conjunctions and universal value restriction only. We prove that the subsumption problem in \cal FL_0 is PSPACE-complete for descriptive semantics when cyclic definitions are allowed. Our proof uses automata theory and as a by-product we establish the PSPACE-completeness of a certain decision problem for regular languages