×

zbMATH — the first resource for mathematics

Extended RDF: computability and complexity issues. (English) Zbl 1347.68316
Summary: 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.

MSC:
68T27 Logic in artificial intelligence
68T30 Knowledge representation
PDF BibTeX XML Cite
Full Text: DOI
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) · Zbl 1182.68157
[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) · Zbl 1351.68272
[4] Analyti, A; Antoniou, G; Damasio, CV; Pachoulakis, I, A framework for modular ERDF ontologies, Ann. Math. Artif. Intell., 67, 189-249, (2013) · Zbl 1271.68217
[5] Analyti, A; Antoniou, G; Damásio, CV; Wagner, G, Negation and negative information in the W3C resource description framework, Ann. Math. Comput. Teleinformatics (AMCT), 1, 25-34, (2004)
[6] Analyti, A; Antoniou, G; Damásio, CV; Wagner, G, Extended RDF as a semantic foundation of rule markup languages, J. Artif. Intell. Res. (JAIR), 32, 37-94, (2008) · Zbl 1182.68157
[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) · Zbl 1192.68128
[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) · Zbl 0787.68017
[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) · Zbl 0799.68045
[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, 249-269, (2008) · Zbl 1139.68010
[13] Brewka, G; Eiter, T; Truszczynski, M, Answer set programming at a glance, Commun. ACM, 54, 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) · Zbl 1139.68010
[15] Chen, W; Kifer, M; Warren, DS, HILOG: a foundation for higher-order logic programming, J. Log. Program., 15, 187-230, (1993) · Zbl 0787.68017
[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, FM; Lenzerini, M; Nardi, D; Schaerf, A, \(\mathcal{A}\mathcal{L}\)Aℒ-log: integrating Datalog and description logics, J. Intell. Inf. Syst., 10, 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, 123-165, (2007) · Zbl 1138.68017
[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) · Zbl 1183.68595
[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) · Zbl 1234.68247
[22] Ferraris, P; Lee, J; Lifschitz, V, Stable models and circumscription, Artif. Intell., 175, 236-263, (2011) · Zbl 1227.68103
[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) · Zbl 1251.68060
[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) · Zbl 1149.68332
[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, AV; Ross, KA; Schlipf, JS, The well-founded semantics for general logic programs, J. ACM, 38, 620-650, (1991) · Zbl 0799.68045
[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) · Zbl 1182.68157
[30] Gelfond, M; Lifschitz, V, Classical negation in logic programs and disjunctive databases, New Gener. Comput., 9, 365-386, (1991) · Zbl 0735.68012
[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) · Zbl 0982.03016
[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, 671-695, (2009) · Zbl 1192.68128
[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) · Zbl 0735.68012
[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) · Zbl 1234.68247
[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, 499-562, (2006) · Zbl 1367.68308
[42] Levy, AY; Rousset, M, Combining Horn rules and description logics in CARIN, Artif. Intell., 104, 165-209, (1998) · Zbl 0908.68166
[43] Lifschitz, V.: Nonmonotonic databases and epistemic queries. In: 12th International Joint Conference on Artificial Intelligence (IJCAI-1991), pp. 381-386 (1991) · Zbl 0747.68086
[44] Lifschitz, V, Answer set programming and plan generation, Artif. Intell., 138, 39-54, (2002) · Zbl 0995.68020
[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) · Zbl 0668.68004
[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, 89-116, (1986)
[50] Mei, J., Lin, Z., Boley, H.: \(\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) · Zbl 1271.68217
[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) · Zbl 1327.68257
[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] Niemelȧ, I, Logic programs with stable model semantics as a constraint programming paradigm, Ann. Math. Artif. Intell., 25, 241-273, (1999) · Zbl 0940.68018
[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) · Zbl 0833.68049
[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) · Zbl 1048.68910
[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) · Zbl 0359.68050
[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, HJ, Completeness, decidability and complexity of entailment for RDF schema and a semantic extension involving the OWL vocabulary, J. Web Semant., 3, 79-115, (2005)
[68] Yang, F., Chen, X.: \(\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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.