MPI-INF Logo
Publications

Server    halma.mpi-inf.mpg.de

Proceedings Article, Paper


@InProceedings
Beitrag in Tagungsband, Workshop
Author, Editor
Author(s):
Kazakov, Yevgeny
de Nivelle, Hans		dblp
dblp
Editor(s):
Calvanese, Diego
De Giacomo, Giuseppe
Franconi, Enrico		dblp
dblp
dblp
Not MPII Editor(s):
Calvanese, Diego
De Giacomo, Giuseppe
Franconi, Enrico
BibTeX cite key*:
Kazakov03SubsumptionFLzero
Title, Booktitle
Title*:
Subsumption of Concepts in $FL_0$ for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE-complete
SubDL.pdf (153.57 KB)
Booktitle*:
2003 International Workshop on Description Logics (DL-03)
Event, URLs
Conference URL::
http://www.dis.uniroma1.it/~dl03/
Downloading URL:
Event Address*:
Rome, Italy
Language:
English
Event Date*
(no longer used):
September 5-7, 2003
Organization:
University of Rome "La Sapienza" and Free University of Bolzano/Bozen
Event Start Date:
5 September 2003
Event End Date:
7 September 2003
Publisher
Name*:
CEUR
URL:
http://CEUR-WS.org/
Address*:
Aachen, Germany
Type:
Vol, No, Year, pp.
Series:
CEUR Workshop Proceedings
Volume:
81
Number:
Month:
September
Pages:
56-64
Year*:
2003
VG Wort Pages:
9
ISBN/ISSN:
1613-0073
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Keywords:
Description Logics, Automata Theory
HyperLinks / References / URLs:
http://www.dis.uniroma1.it/~dl03/
http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-81/
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Audience:
popular
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort, CCL bibliography



BibTeX Entry:
@INPROCEEDINGS{Kazakov03SubsumptionFLzero,
AUTHOR = {Kazakov, Yevgeny and de Nivelle, Hans},
 EDITOR = {Calvanese, Diego and De Giacomo, Giuseppe and Franconi, Enrico},
 TITLE = {Subsumption of Concepts in ${FL_0}$ for (Cyclic) Terminologies with Respect to Descriptive Semantics is {PSPACE-complete}},
 BOOKTITLE = {2003 International Workshop on Description Logics (DL-03)},
 PUBLISHER = {CEUR},
 YEAR = {2003},
 ORGANIZATION = {University of Rome "La Sapienza" and Free University of Bolzano/Bozen},
 VOLUME = {81},
 PAGES = {56--64},
 SERIES = {CEUR Workshop Proceedings},
 ADDRESS = {Rome, Italy},
 MONTH = {September},
 ISBN = {1613-0073},
}

Entry last modified by Uwe Waldmann, 01/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Yevgeny Kazakov		Created
01/22/2004 08:27:11 PM
Revisions
7.
6.
5.
4.
3.		Editor(s)
Uwe Waldmann
Sabine Krott
Anja Becker
Christine Kiesel
Christine Kiesel		Edit Dates
03/23/2005 09:53:26 PM
22.06.2004 10:20:12
21.06.2004 16:53:00
16.06.2004 15:58:39
01/29/2004 10:56:37 AM

File Attachment Icon
SubDL.pdf