Extended RDF: Computability and complexity issues

Anastasia Analyti, Carlos Viegas Damásio, Grigoris Antoniou

Research output: Contribution to journalArticle

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. Based on the undecidability result of ERDF stable model semantics, 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 also extends RDFS entailment. Equivalence statements between the two semantics are provided. Additionally, we provide algorithms that compute the ERDF #n-stable models of syntax-restricted and general ERDF ontologies. Further, we provide complexity results for the ERDF #n-stable model semantics on syntax-restricted and general ERDF ontologies. Finally, we provide complexity results for the ERDF stable model semantics on syntax-restricted ERDF ontologies.

LanguageEnglish
Pages267-334
Number of pages68
JournalAnnals of Mathematics and Artificial Intelligence
Volume75
Issue number3-4
DOIs
Publication statusPublished - 1 Dec 2015

Fingerprint

Computability
Semantics
Stable Models
Ontology
Computability and decidability
Undecidability
Decidability
Faithful
Equivalence

Cite this

Analyti, Anastasia ; Damásio, Carlos Viegas ; Antoniou, Grigoris. / Extended RDF : Computability and complexity issues. In: Annals of Mathematics and Artificial Intelligence. 2015 ; Vol. 75, No. 3-4. pp. 267-334.
@article{127493549fbf4190b929a17b4079b60f,
title = "Extended RDF: Computability and complexity issues",
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. Based on the undecidability result of ERDF stable model semantics, 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 also extends RDFS entailment. Equivalence statements between the two semantics are provided. Additionally, we provide algorithms that compute the ERDF #n-stable models of syntax-restricted and general ERDF ontologies. Further, we provide complexity results for the ERDF #n-stable model semantics on syntax-restricted and general ERDF ontologies. Finally, we provide complexity results for the ERDF stable model semantics on syntax-restricted ERDF ontologies.",
keywords = "Complexity, Extended RDF ontologies, Negation, Rules, Semantic web",
author = "Anastasia Analyti and Dam{\~A}¡sio, {Carlos Viegas} and Grigoris Antoniou",
year = "2015",
month = "12",
day = "1",
doi = "10.1007/s10472-015-9451-0",
language = "English",
volume = "75",
pages = "267--334",
journal = "Annals of Mathematics and Artificial Intelligence",
issn = "1012-2443",
publisher = "Springer Netherlands",
number = "3-4",

}

Extended RDF : Computability and complexity issues. / Analyti, Anastasia; Damásio, Carlos Viegas; Antoniou, Grigoris.

In: Annals of Mathematics and Artificial Intelligence, Vol. 75, No. 3-4, 01.12.2015, p. 267-334.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Extended RDF

T2 - Annals of Mathematics and Artificial Intelligence

AU - Analyti, Anastasia

AU - Damásio, Carlos Viegas

AU - Antoniou, Grigoris

PY - 2015/12/1

Y1 - 2015/12/1

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. Based on the undecidability result of ERDF stable model semantics, 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 also extends RDFS entailment. Equivalence statements between the two semantics are provided. Additionally, we provide algorithms that compute the ERDF #n-stable models of syntax-restricted and general ERDF ontologies. Further, we provide complexity results for the ERDF #n-stable model semantics on syntax-restricted and general ERDF ontologies. Finally, we provide complexity results for the ERDF stable model semantics on syntax-restricted ERDF ontologies.

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. Based on the undecidability result of ERDF stable model semantics, 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 also extends RDFS entailment. Equivalence statements between the two semantics are provided. Additionally, we provide algorithms that compute the ERDF #n-stable models of syntax-restricted and general ERDF ontologies. Further, we provide complexity results for the ERDF #n-stable model semantics on syntax-restricted and general ERDF ontologies. Finally, we provide complexity results for the ERDF stable model semantics on syntax-restricted ERDF ontologies.

KW - Complexity

KW - Extended RDF ontologies

KW - Negation

KW - Rules

KW - Semantic web

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

U2 - 10.1007/s10472-015-9451-0

DO - 10.1007/s10472-015-9451-0

M3 - Article

VL - 75

SP - 267

EP - 334

JO - Annals of Mathematics and Artificial Intelligence

JF - Annals of Mathematics and Artificial Intelligence

SN - 1012-2443

IS - 3-4

ER -