TY - JOUR
T1 - Extended RDF
T2 - Computability and complexity issues
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
AN - SCOPUS:84925400814
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 -