Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.dis.uniroma1.it/~dl03/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
SubDL.pdf