Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Subsumption of Concepts in FL_0 for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE-complete

MPG-Autoren
/persons/resource/persons44749

Kazakov,  Yevgeny
Programming Logics, MPI for Informatics, Max Planck Society;

/persons/resource/persons44298

de Nivelle,  Hans
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Kazakov, Y., & de Nivelle, H. (2003). Subsumption of Concepts in FL_0 for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE-complete. In 2003 International Workshop on Description Logics (DL-03) (pp. 56-64). Aachen, Germany: CEUR.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-2E3F-5
Zusammenfassung
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.