Conference item
Subsumption of Concepts in FL0 for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE−complete.
- 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
Actions
Access Document
- Files:
-
-
(Preview, pdf, 153.6KB, Terms of use)
-
Authors
- Host title:
- Description Logics
- Volume:
- 81
- Publication date:
- 2003-01-01
- UUID:
-
uuid:e1dffaad-5598-4ec3-92a7-ac635e4d109e
- Local pid:
-
cs:885
- Deposit date:
-
2015-03-31
- ARK identifier:
Terms of use
- Copyright date:
- 2003
If you are the owner of this record, you can report an update to it here: Report update to this record