Skip to main content

Subsumption of Concepts in FL0 for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE−complete.

Yevgeny Kazakov and Hans de Nivelle

Abstract

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

Book Title
Description Logics
Series
CEUR Workshop Proceedings
Volume
81
Year
2003