Skip to main content
Springer Nature Link
Log in

Extended RDF: Computability and complexity issues

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  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)

    MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    MATH  MathSciNet  Google Scholar 

  13. Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92–103 (2011)

    Article  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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.: \(\mathcal {A}\mathcal {L}\)-log: integrating datalog and description logics. J. Intell. Inf. Syst. 10(3), 227–252 (1998)

    Article  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    MATH  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    MATH  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  42. Levy, A.Y., Rousset, M.: Combining horn rules and description logics in CARIN. Artif. Intell. 104(1-2), 165–209 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Book  MATH  Google Scholar 

  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)

    Article  Google Scholar 

  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)

  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. Niemelȧ, I.: Logic programs with stable model semantics as a constraint programming paradigm. Ann. Math. Artif. Intell. 25(3-4), 241–273 (1999)

    Article  MathSciNet  Google Scholar 

  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)

    MATH  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  Google Scholar 

  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)

Download references

Author information

Authors and Affiliations

  1. Institute of Computer Science, FORTH-ICS, Heraklion, Greece

    Anastasia Analyti & Grigoris Antoniou

  2. CENTRIA, Departamento de Informatica, Faculdade de Ciencias e Tecnologia, Universidade Nova de Lisboa, 2829-516, Caparica, Portugal

    Carlos Viegas Damásio

  3. Department of Informatics, University of Huddersfield, Huddersfield, UK

    Grigoris Antoniou

Authors
  1. Anastasia Analyti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlos Viegas Damásio
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Grigoris Antoniou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anastasia Analyti.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Analyti, A., Damásio, C.V. & Antoniou, G. Extended RDF: Computability and complexity issues. Ann Math Artif Intell 75, 267–334 (2015). https://doi.org/10.1007/s10472-015-9451-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10472-015-9451-0

Keywords

Mathematics Subject Classification (2010)

Search

Navigation