On the Computability and Complexity Issues of Extended RDF

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

doi:10.1007/978-3-540-89197-0_5

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 proceeding › Conference contribution › peer-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 language	English
Title of host publication	PRICAI 2008
Subtitle of host publication	Trends in Artificial Intelligence - 10th Pacific Rim International Conference on Artificial Intelligence, Proceedings
Editors	Tu-Bao Ho, Zhi-Hua Zhou
Place of Publication	Berlin
Publisher	Springer-Verlag Berlin Heidelberg
Pages	5-16
Number of pages	12
Volume	5351 LNCS/LNAI
ISBN (Electronic)	9783540891970
ISBN (Print)	354089196X, 9783540891963
DOIs	https://doi.org/10.1007/978-3-540-89197-0_5
Publication status	Published - 24 Nov 2008
Externally published	Yes
Event	10th Pacific Rim International Conference on Artificial Intelligence - Hanoi, Viet Nam Duration: 15 Dec 2008 → 19 Dec 2008 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer-Verlag Berlin Heidelberg
Volume	5351 LNCS/LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th Pacific Rim International Conference on Artificial Intelligence
Abbreviated title	PRICAI 2008
Country/Territory	Viet Nam
City	Hanoi
Period	15/12/08 → 19/12/08

Access to Document

10.1007/978-3-540-89197-0_5Licence: Unspecified

Cite this

Analyti, A., Antoniou, G., Damásio, C. V., & Wagner, G. (2008). On the Computability and Complexity Issues of Extended RDF. In T-B. Ho, & Z-H. Zhou (Eds.), PRICAI 2008: Trends in Artificial Intelligence - 10th Pacific Rim International Conference on Artificial Intelligence, Proceedings (Vol. 5351 LNCS/LNAI, pp. 5-16). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5351 LNCS/LNAI). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-540-89197-0_5

Analyti, Anastasia ; Antoniou, Grigoris ; Damásio, Carlos Viegas et al. / On the Computability and Complexity Issues of Extended RDF. PRICAI 2008: Trends in Artificial Intelligence - 10th Pacific Rim International Conference on Artificial Intelligence, Proceedings. editor / Tu-Bao Ho ; Zhi-Hua Zhou. Vol. 5351 LNCS/LNAI Berlin : Springer-Verlag Berlin Heidelberg, 2008. pp. 5-16 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e8725e7e42d448fd998dbe292732fb93,

title = "On the Computability and Complexity Issues of Extended RDF",

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.",

keywords = "Complexity, Extended RDF ontologies, Negation, Rules, Semantic Web",

author = "Anastasia Analyti and Grigoris Antoniou and Dam{\'a}sio, {Carlos Viegas} and Gerd Wagner",

year = "2008",

month = nov,

day = "24",

doi = "10.1007/978-3-540-89197-0_5",

language = "English",

isbn = "354089196X",

volume = "5351 LNCS/LNAI",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "5--16",

editor = "Ho, {Tu-Bao } and Zhi-Hua Zhou",

booktitle = "PRICAI 2008",

address = "Germany",

note = "10th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2008 ; Conference date: 15-12-2008 Through 19-12-2008",

}

Analyti, A, Antoniou, G, Damásio, CV & Wagner, G 2008, On the Computability and Complexity Issues of Extended RDF. in T-B Ho & Z-H Zhou (eds), PRICAI 2008: Trends in Artificial Intelligence - 10th Pacific Rim International Conference on Artificial Intelligence, Proceedings. vol. 5351 LNCS/LNAI, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5351 LNCS/LNAI, Springer-Verlag Berlin Heidelberg, Berlin, pp. 5-16, 10th Pacific Rim International Conference on Artificial Intelligence, Hanoi, Viet Nam, 15/12/08. https://doi.org/10.1007/978-3-540-89197-0_5

On the Computability and Complexity Issues of Extended RDF. / Analyti, Anastasia; Antoniou, Grigoris; Damásio, Carlos Viegas et al.

PRICAI 2008: Trends in Artificial Intelligence - 10th Pacific Rim International Conference on Artificial Intelligence, Proceedings. ed. / Tu-Bao Ho; Zhi-Hua Zhou. Vol. 5351 LNCS/LNAI Berlin : Springer-Verlag Berlin Heidelberg, 2008. p. 5-16 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5351 LNCS/LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the Computability and Complexity Issues of Extended RDF

AU - Analyti, Anastasia

AU - Antoniou, Grigoris

AU - Damásio, Carlos Viegas

AU - Wagner, Gerd

N1 - Conference code: 10

PY - 2008/11/24

Y1 - 2008/11/24

N2 - 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.

AB - 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.

KW - Complexity

KW - Extended RDF ontologies

KW - Negation

KW - Rules

KW - Semantic Web

UR - http://www.scopus.com/inward/record.url?scp=58349085878&partnerID=8YFLogxK

UR - https://www.springer.com/gp/book/9783540891963

U2 - 10.1007/978-3-540-89197-0_5

DO - 10.1007/978-3-540-89197-0_5

M3 - Conference contribution

AN - SCOPUS:58349085878

SN - 354089196X

SN - 9783540891963

VL - 5351 LNCS/LNAI

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 5

EP - 16

BT - PRICAI 2008

A2 - Ho, Tu-Bao

A2 - Zhou, Zhi-Hua

PB - Springer-Verlag Berlin Heidelberg

CY - Berlin

T2 - 10th Pacific Rim International Conference on Artificial Intelligence

Y2 - 15 December 2008 through 19 December 2008

ER -

Analyti A, Antoniou G, Damásio CV, Wagner G. On the Computability and Complexity Issues of Extended RDF. In Ho T-B, Zhou Z-H, editors, PRICAI 2008: Trends in Artificial Intelligence - 10th Pacific Rim International Conference on Artificial Intelligence, Proceedings. Vol. 5351 LNCS/LNAI. Berlin: Springer-Verlag Berlin Heidelberg. 2008. p. 5-16. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-89197-0_5

On the Computability and Complexity Issues of Extended RDF

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this