de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44749

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44298

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

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

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.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2E3F-5
##### 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.