Extended RDF: Computability and complexity issues
Pages 267 - 334
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.
References
[1]
Alferes, J.J., Damásio, C.V., Pereira, L.M.: Semantic web logic programming tools. In: International Workshop on Principles and Practice of Semantic Web Reasoning (PPSWR-2003), pp. 16---32 (2003)
[2]
Analyti, A., Antoniou, G., Damásio, C.V.: A formal theory for modular ERDF ontologies. In: 3rd International Conference Web Reasoning and Rule Systems (RR-2009), pp. 212---226 (2009)
[3]
Analyti, A., Antoniou, G., Damásio, C.V.: MWeb: a principled framework for modular web rule bases and its semantics. ACM Trans. Comput. Log. 12(2) (2011)
[4]
Analyti, A., Antoniou, G., Damasio, C.V., Pachoulakis, I.: A framework for modular ERDF ontologies. Ann. Math. Artif. Intell. 67(3-4), 189---249 (2013)
[5]
Analyti, A., Antoniou, G., Damásio, C.V., Wagner, G.: Negation and negative information in the W3C resource description framework. Ann. Math. Comput. Teleinformatics (AMCT) 1(2), 25---34 (2004)
[6]
Analyti, A., Antoniou, G., Damásio, C.V., Wagner, G.: Extended RDF as a semantic foundation of rule markup languages. J. Artif. Intell. Res. (JAIR) 32, 37---94 (2008)
[7]
Analyti, A., Antoniou, G., Damásio, C. V., Wagner, G.: On the computability and complexity issues of extended RDF. In: 10th Pacific Rim International Conference on Artificial Intelligence (PRICAI-2008), pp. 5---16 (2008)
[8]
Antoniou, G., Bikakis, A., Wagner, G.: A System for nonmonotonic rules on the web. In: 3rd International Workshop on Rules and Rule Markup Languages for the Semantic Web (RULEML-2003), pp. 23---36 (2004)
[9]
Bassiliades, N., Antoniou, G., Vlahavas, I. P.: DR-DEVICE: a defeasible logic system for the semantic Web. In: 2nd International Workshop on Principles and Practice of Semantic Web Reasoning (PPSWR-2004), pp. 134---148 (2004)
[10]
Berger, R.: The Undecidability of the Dominoe Problem. Mem Am. Math. Soc. 66, 1---72 (1966)
[11]
Berners-Lee, T.: Design issues - architectual and philosophical points. Personal notes. Available at http://www.w3.org/DesignIssues (1998)
[12]
Berners-Lee, T., Connolly, D., Kagal, L., Scharf, Y., Hendler, J.: N3Logic: a logical framework for the world wide web. Theory Pract. Log. Program. (TPLP) 8(3), 249---269 (2008)
[13]
Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92---103 (2011)
[14]
Bry, F., Ley, C., Linse, B., RDFLog, B. Marnette.: It's like datalog for RDF. In: 22nd Workshop on (Constraint) Logic Programming (WLP-2008), co-located with JELIA-2008 (2008)
[15]
Chen, W., Kifer, M., Warren, D.S.: HILOG: a foundation for higher-order logic programming. J. Log. Program. 15(3), 187---230 (1993)
[16]
Damásio, C.V., Analyti, A., Antoniou, G.: Embeddings of simple modular extended RDF. In: P. Hitzler, T. Lukasiewicz (eds.) 4th International Conference on Web Reasoning and Rule Systems (RR-2010), pp. 204---212 (2010)
[17]
Donini, F. M., Lenzerini, M., Nardi, D., Schaerf, A.: A¿$\mathcal {A}\mathcal {L}$-log: integrating datalog and description logics. J. Intell. Inf. Syst. 10(3), 227---252 (1998)
[18]
Drabent, W., Maluszynski, J.: Well-founded semantics for hybrid rules. In: First International Conference on Web Reasoning and Rule Systems (RR-2007), pp. 1---15 (2007)
[19]
Eiter, T., Faber, W., Fink, M., Woltran, S.: Complexity results for answer set programming with bounded predicate arities and implications. Ann. Math. Artif. Intell. 51(2-4), 123---165 (2007)
[20]
Eiter, T., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer Set programming with description logics for the semantic web. In: 9th International Conference on Principles of Knowledge Representation and Reasoning (KR-2004), pp. 141---151 (2004)
[21]
Eiter, T., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Well-founded semantics for description logic programs in the semantic web. In: 3rd International Workshop on Rules and Rule Markup Languages for the Semantic Web (RuleML-2004), pp. 81---97 (2004)
[22]
Ferraris, P., Lee, J., Lifschitz, V.: Stable models and circumscription. Artif. Intell. 175(1), 236---263 (2011)
[23]
Furche, T.: Exploring and taming existence in rule-based RDF queries. REWERSE Deliverable I4-D14. Available at http://rewerse.net/deliverables/m42/i4-d14.pdf (2007)
[24]
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer set solving in practice. Morgan & Publishers (2012)
[25]
Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set solving. In: 20th International Joint Conference on Artificial Intelligence (IJCAI-2007), pp. 386---392 (2007)
[26]
Gelder, A.V., Ross, K.A., Schlipf, J.S.: Unfounded sets and well-founded semantics for general logic programs. In: 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-1988), pp. 221---230 (1988)
[27]
Gelder, A. V., Ross, K. A., Schlipf, J. S.: The well-founded semantics for general logic programs. J. ACM 38(3), 620---650 (1991)
[28]
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: 5th International Conference on Logic Programming (ICLP-1988), pp. 1070---1080 (1988)
[29]
Gelfond, M., Lifschitz, V.: Logic programs with classical negation. In: 7th International Conference on Logic Programming, pp. 579---597 (1990)
[30]
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9(3/4), 365---386 (1991)
[31]
Hayes, P.: RDF Semantics. W3C Recommendation, 10 February 2004. Available at http://www.w3.org/TR/2004/REC-rdf-mt-20040210/ (2004)
[32]
Herre, H., Jaspars, J., Wagner, G.: Partial logics with two kinds of negation as a foundation of knowledge-based reasoning. In: D. M. Gabbay, H. Wansing (eds.) What Is Negation? Kluwer Academic Publishers, Norwell (1999)
[33]
Hitzler, P., Krotzsch, M., Parsia, B., Patel-Schneider, P. F., Rudolph, S.: OWL 2 Web Ontology Language Primer (Second Edition). W3C Recommendation 11 December 2012. Available at http://www.w3.org/TR/owl2-primer/ (2012)
[34]
Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible SROIQ. In: 10th International Conference on Principles of Knowledge Representation and Reasoning (KR-2006), pp. 57---67 (2006)
[35]
Horrocks, I., Patel-Schneider, P.F., Boley, H., Tabet, S., Grosof, B., Dean, M.: SWRL: a semantic web rule language combining OWL and RuleML. W3C Member Submission, 21 May 2004. Available at http://www.w3.org/Submission/2004/SUBM-SWRL-20040521/ (2004)
[36]
Ianni, G., Martello, A., Panetta, C., Terracina, G.: Efficiently querying RDF(S) ontologies with answer set programming. J. Log. Comput. 19(4), 671---695 (2009)
[37]
Klyne, G., Carroll, J.J.: Resource description framework (RDF): concepts and abstract syntax. W3C Recommendation, 10 February 2004. Available at http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/ (2004)
[38]
Knorr, M., Alferes, J.J., Hitzler, P.: A coherent well-founded Model for hybrid MKNF knowledge bases. In: 18th European Conference on Artificial Intelligence (ECAI-2008), pp. 99---103 (2008)
[39]
Krötzsch, M., Rudolph, S., Hitzler, P.: Description logic rules. In: 18th European Conference on Artificial Intelligence (ECAI-2008), pp. 80---84 (2008)
[40]
Lee, J., Meng, Y.: First-order stable model semantics and first-order loop formulas. J. Artif. Intell. Res. (JAIR) 42, 125---180 (2011)
[41]
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log. 7(3), 499---562 (2006)
[42]
Levy, A.Y., Rousset, M.: Combining horn rules and description logics in CARIN. Artif. Intell. 104(1-2), 165---209 (1998)
[43]
Lifschitz, V.: Nonmonotonic databases and epistemic queries. In: 12th International Joint Conference on Artificial Intelligence (IJCAI-1991), pp. 381---386 (1991)
[44]
Lifschitz, V.: Answer set programming and plan generation. Artif. Intell. 138(1-2), 39---54 (2002)
[45]
Lifschitz, V.: What Is Answer Set Programming? . In: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, (AAAI-2008), pp. 1594---1597 (2008)
[46]
Lloyd, J.W.: Foundations of logic programming, (2). Springer-Verlag, Berlin Heidelberg (1987)
[47]
Lukasiewicz, T.: A novel combination of answer set programming with description logics for the semantic web. In: 4th European Semantic Web Conference (ESWC-2007), pp. 384---398 (2007)
[48]
Marek, V., Truszczyski, M.: Stable models and an alternative logic programming paradigm. In: The Logic Programming Paradigm: a 25-Year Perspective, pp. 375---398. Springer-Verlag, Berlin Heidelberg (1999)
[49]
McCarthy, J.: Applications of circumscription to formalizing common-sense knowledge. Artif. Intell. 28(1), 89---116 (1986)
[50]
Mei, J., Lin, Z., Boley, H.: A¿C¿u$\mathcal {A}\mathcal {L}\mathcal {C}^{u}_{\mathbb {P}}$ :an integration of description logic and general rules. In: First International Conference on Web Reasoning and Rule Systems (RR-2007), pp. 163---177 (2007)
[51]
Motik, B., Rosati, R.: A faithful integration of description logics with logic programming. In: 20th International Joint Conference on Artificial Intelligence (IJCAI-2007), pp. 477---482 (2007)
[52]
Motik, B., Rosati, R.: Reconciling description logics and rules. J. ACM 57(5) (2010)
[53]
Motik, B., Sattler, U., Studer, R.: Query answering for OWL-DL with rules. In: 3rd International Semantic Web Conference (ISWC-2004), pp. 549---563 (2004)
[54]
Muñoz, S., Pérez, J., Gutiérrez, C.: Minimal deductive systems for RDF. In: 4th European Semantic Web Conference (ESWC-2007), pp. 53---67 (2007)
[55]
Niemela¿, I.: Logic programs with stable model semantics as a constraint programming paradigm. Ann. Math. Artif. Intell. 25(3-4), 241---273 (1999)
[56]
Niemelä, I., Simons, P.: Smodels - an implementation of the stable model and well-founded semantics for normal LP. In: 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-1997), pp. 421---430 (1997)
[57]
Papadimitriou, C.M.: Computational complexity. Addison-Wesley, MA (1994)
[58]
Pérez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM Trans. Database Syst. 34(3), Article 16 (45 pages) (2009)
[59]
Prud'hommeaux, E., Seaborne, A.: SPARQL query language for RDF. W3C Recommendation, 15 January 2008. Available at http://www.w3.org/TR/rdf-sparql-query/ (2008)
[60]
Rosati, R.: Towards expressive KR systems integrating datalog and description logics: preliminary report. In: Proceedings of the 1999 Description Logic Workshop (DL-1999), pp. 160---164 (1999)
[61]
Rosati, R.: On the decidability and complexity of integrating ontologies and rules. J. Web Semant. 3, 61---73 (2005)
[62]
Rosati, R.: DL+log: tight integration of description logics and disjunctive datalog. In: 10th International Conference on Principles of Knowledge Representation and Reasoning (KR-2006) (2006)
[63]
Schenk, S., Staab, S.: Networked graphs: a declarative mechanism for SPARQL rules, SPARQL views and RDF data integration on the web. In: 17th International Conference on World Wide Web (WWW-2008), pp. 585---594 (2008)
[64]
Sintek, M., Decker, S.: TRIPLE - a query, inference, and transformation language for the semantic web. In: 1st International Semantic Web Conference (ISWC-2002), pp. 364---378. Springer-Verlag, Berlin Heidelberg (2002)
[65]
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: preliminary report. In: Fifth Annual ACM Symposium on Theory of Computing (STOC-1973), pp. 1---9 (1973)
[66]
ter Horst, H. J.: Extending the RDFS entailment lemma. In: 3rd International Semantic Web Conference (ISWC-2004), pp. 77---91 (2004)
[67]
ter Horst, H.J.: Completeness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary. J. Web Semant. 3 (2-3), 79---115 (2005)
[68]
Yang, F., Chen, X.: D¿clog$\mathcal {D}\mathcal {L}clog$: a hybrid system integrating rules and description logics with circumscription. In: 2007 International Workshop on Description Logics (DL-2007) (2007)
[69]
Yang, G., Kifer, M., Zhao, C.: Flora-2: A Rule-based knowledge representation and inference infrastructure for the semantic web. In: 2nd International Conference on Ontologies, DataBases, and Applications of Semantics for Large Scale Information Systems (ODBASE'03), pp. 671---688 (2003)
- Extended RDF: Computability and complexity issues
Recommendations
On the Computability and Complexity Issues of Extended RDF
PRICAI '08: Proceedings of the 10th Pacific Rim International Conference on Artificial Intelligence: Trends in Artificial IntelligenceERDF 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 ...
Why-provenance information for RDF, rules, and negation
The provenance (i.e., origins) of derived information on the Web is crucial in many applications to allow information quality assessment, trust judgments, accountability, as well as understanding the temporal and spatial status of the information. On ...
Tightly integrated probabilistic description logic programs for representing ontology mappings
Creating mappings between ontologies is a common way of approaching the semantic heterogeneity problem on the Semantic Web. To fit into the landscape of Semantic Web languages, a suitable, logic-based representation formalism for mappings is needed. We ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2015 Springer International Publishing Switzerland.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 December 2015
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in