Extended RDF: Computability and complexity issues

Anastasia Analyti, Carlos Viegas Damásio, Grigoris Antoniou

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)267-334
Number of pages68
JournalAnnals of Mathematics and Artificial Intelligence
Issue number3-4
Early online date24 Mar 2015
Publication statusPublished - 1 Dec 2015


Dive into the research topics of 'Extended RDF: Computability and complexity issues'. Together they form a unique fingerprint.

Cite this