On the Computability and Complexity Issues of Extended RDF

Anastasia Analyti, Grigoris Antoniou, Carlos Viegas Damásio, Gerd Wagner

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)

Abstract

ERDF stable model semantics is a recently proposed semantics for ERDF ontologies and a faithful extension of RDFS semantics on RDF graphs. In this paper, we elaborate on the computability and complexity issues of the ERDF stable model semantics. We show that decidability under this semantics cannot be achieved, unless ERDF ontologies of restricted syntax are considered. Therefore, we propose a slightly modified semantics for ERDF ontologies, called ERDF #n-stable model semantics. We show that entailment under this semantics is in general decidable and it also extends RDFS entailment. An equivalence statement between the two semantics and various complexity results are provided.

Original languageEnglish
Title of host publicationPRICAI 2008
Subtitle of host publicationTrends in Artificial Intelligence - 10th Pacific Rim International Conference on Artificial Intelligence, Proceedings
EditorsTu-Bao Ho, Zhi-Hua Zhou
Place of PublicationBerlin
PublisherSpringer-Verlag Berlin Heidelberg
Pages5-16
Number of pages12
Volume5351 LNCS/LNAI
ISBN (Electronic)9783540891970
ISBN (Print)354089196X, 9783540891963
DOIs
Publication statusPublished - 24 Nov 2008
Externally publishedYes
Event10th Pacific Rim International Conference on Artificial Intelligence - Hanoi, Viet Nam
Duration: 15 Dec 200819 Dec 2008
Conference number: 10

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer-Verlag Berlin Heidelberg
Volume5351 LNCS/LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Pacific Rim International Conference on Artificial Intelligence
Abbreviated titlePRICAI 2008
CountryViet Nam
CityHanoi
Period15/12/0819/12/08

Fingerprint Dive into the research topics of 'On the Computability and Complexity Issues of Extended RDF'. Together they form a unique fingerprint.

Cite this