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"><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 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

Details

Book Title

Description Logics
Series

CEUR Workshop Proceedings
Volume

81
Year

2003

Links

BibTeX

Link (pdf)

Related pages

People

Yevgeny Kazakov

Activities

Knowledge Representation and Reasoning