External sources of knowledge and value invention in logic programming. (English) Zbl 1125.68026

Summary: The issue of value invention in logic programming embraces many scenarios, such as logic programming with function symbols, object oriented logic languages, inter-operability with external sources of knowledge, or set unification. This work introduces a framework embedding value invention in a general context. The class of programs having a suitable (but, in general, not decidable) ‘finite grounding property’ is identified, and the class of ‘value invention restricted’ programs is introduced. Value invention restricted programs have the finite grounding property and can be decided in polynomial time. They are a very large polynomially decidable class having this property, when no assumption can be made about the nature of invented values (while this latter is the case in the specific literature about logic programming with function symbols). Relationships with existing formalisms are eventually discussed, and the implementation of a system supporting the class of such programs is described.


68N17 Logic programming
68T27 Logic in artificial intelligence
68T30 Knowledge representation


DLV; foaf; DLV-EX
Full Text: DOI


[1] Abiteboul, S., Vianu, V.: Datalog extensions for database queries and updates. J. Comput. Syst. Sci. 43(1), 62–124 (1991) · Zbl 0764.68158
[2] Cabibbo, L.: Expressiveness of semipositive logic programs with value invention. In: Logic in Databases, pp. 457–474 (1996)
[3] Hull, R., Yoshikawa, M.: ILOG: declarative creation and manipulation of object identifiers. In: McLeod, D., Sacks-Davis, R., Schek, H.J. (eds.) Proceedings of the 16th International Conference on Very Large Data Bases, pp. 455–468, 13–16 August 1990. Brisbane, Queensland, Australia, Morgan Kaufmann (1990)
[4] Eiter, T., Ianni, G., Schindlauer, R., Tompits, H.: A uniform integration of higher-order reasoning and external evaluations in answer set programming. In: International Joint Conference on Artificial Intelligence (IJCAI) 2005, pp. 90–96. Edinburgh, UK (2005) · Zbl 1108.68359
[5] Heymans, S., Nieuwenborgh, D.V., Vermeir, D.: Nonmonotonic ontological and rule-based reasoning with extended conceptual logic programs. In: Proceedings of the Second European Semantic Web Conference, ESWC 2005. Lecture Notes in Computer Science, vol. 3532, pp. 392–407 (2005)
[6] 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. Logic 7(3), 499–562 (2006)
[7] Simons, P., Niemelä, I., Soininen, T.: Extending and implementing the stable model semantics. Artif. Intel. 138, 181–234 (2002) · Zbl 0995.68021
[8] Syrjänen, T.: Omega-restricted logic programs. In: Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning. Springer, Vienna, Austria, (2001) · Zbl 1007.68503
[9] Bonatti, P.A.: Reasoning with infinite stable models. In: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI) 2001, pp. 603–610. Seattle, WA, USA, Morgan Kaufmann Publishers (2001)
[10] Faber, W., Pfeifer, G.: DLV homepage (since 1996) http://www.dlvsystem.com/
[11] Ross, K.: The well-founded semantics for disjunctive logic programs. In: Kim, W., Nicolas, J.M., Nishio, S., (eds.) Deductive and Object-Oriented Databases, pp. 385–402. Elsevier Science Publishers B. V. (1990)
[12] Miller, L., Brickley, D.: The friend of a friend (foaf) project (since 2000) http://www.foaf-project.org/
[13] Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9, 365–385 (1991) · Zbl 0735.68012
[14] Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Logic Programming: Proceedings Fifth Intl Conference and Symposium, pp. 1070–1080. MIT Press, Cambridge, Mass. (1988)
[15] Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and expressive power of logic programming. ACM Comput. Surveys 33(3), 374–425 (2001)
[16] Lifschitz, V., Turner, H.: Splitting a logic program. In: Van Hentenryck, P. (ed.) Proceedings of the 11th International Conference on Logic Programming (ICLP’94), pp. 23–37. MIT Press, Santa Margherita Ligure, Italy (1994)
[17] Bonatti, P.A.: Reasoning with infinite stable models. Artif. Intel. 156(1), 75–111 (2004) · Zbl 1085.68681
[18] Leone, N., Perri, S., Scarcello, F.: Improving ASP instantiators by join-ordering methods. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) Logic Programming and Nonmonotonic Reasoning – Proceedings of the 6th International Conference, LPNMR’01, Vienna, Austria, September 2001. Lecture Notes in Al (LNAI), vol. 2173. Springer-Verlag (2001) · Zbl 1007.68712
[19] Dovier, A., Pontelli, E., Rossi, G.: Set unification. Theory and Practice of Logic Programming, vol. 6, pp. 645–701 (2006) · Zbl 1108.68104
[20] Heymans, S., Nieuwenborgh, D.V., Vermeir, D.: Semantic web reasoning with conceptual logic programs. In: Rules and Rule Markup Languages for the Semantic Web: Third International Workshop, RuleML 2004, pp. 113–127, November 2004, Hiroshima, Japan (2004)
[21] Cabibbo, L.: The expressive power of stratified logic programs with value invention. Inf. Comput. 147(1), 22–56 (1998) · Zbl 0927.68031
[22] Eiter, T., Ianni, G., Schindlauer, R., Tompits, H.: Nonmonotonic description logic programs: Implementation and experiments. In: Logic for Programming, Artificial Intelligence, and Reasoning, 11th International Conference, LPAR 2004, pp. 511–527 (2004) · Zbl 1108.68359
[23] Eiter, T., Ianni, G., Tompits, H., Schindlauer, R.: Effective integration of declarative rules with external evaluations for semantic web reasoning. In: Proceedings of the 3rd European Semantic Web Conference (ESWC 2006), pp. 273–287 (2006)
[24] Ullman, J.D.: Principles of Database and Knowledge-Base Systems, vol. I. Computer Science Press (1988)
[25] Ramakrishnan, R., Bancilhon, F., Silberschatz, A.: Safety of recursive horn clauses with infinite relations. In: Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 328–339, 23–25 March 1987. ACM, San Diego, California (1987)
[26] Sagiv, Y., Vardi, M.Y.: Safety of datalog queries over infinite databases. In: Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 160–171, 29–31 March 1989. ACM Press, Philadelphia, Pennsylvania (1989)
[27] Calimeri, F., Ianni, G.: DLVEX homepage (since 2004) http://www.mat.unical.it/ianni/wiki/dlvex
[28] Palopoli, L., Rombo, S., Terracina, G.: Flexible pattern discovery with (extended) disjunctive logic programming. In: International Symposium on Methodologies for Intelligent Systems (ISMIS 2005), Lecture Notes in AI (LNAI), vol. 3448, pp. 504–513. Springer, Saratoga Springs, New York, USA (2005) · Zbl 1132.68582
[29] Cumbo, C., Iiritano, S., Rullo, P.: Reasoning-based knowledge extraction for text classification. In: Discovery Science, pp. 380–387 (2004) · Zbl 1110.68438
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.