Domain expansion for ASP-programs with external sources. (English) Zbl 1351.68265

Summary: Answer set programming (ASP) is a popular approach to declarative problem solving which for broader usability has been equipped with external source access. The latter may introduce new constants to the program (known as value invention), which can lead to infinite answer sets and non-termination; to prevent this, syntactic safety conditions on programs are common which considerably limit expressiveness (in particular, recursion). We present liberal domain-expansion (lde) safe programs, a novel generic class of ASP programs with external source access and value invention that enjoy finite restrictability, i.e., equivalence to a finite ground version. They use term bounding functions as a parametric notion of safety, which can be instantiated with syntactic, semantic or combined safety criteria; this empowers us to generalize and integrate many other notions of safety from the literature, and modular composition of criteria makes future extensions easy. Furthermore, we devise a grounding algorithm for lde-safe programs which in contrast to traditional algorithms can ground any such program directly without the need for program decomposition. While we present our approach on top of a proposed formalism in order to make the formalization precise, the general concepts carry over to related formalisms and important special cases as well. An experimental evaluation of lde-safety on various applications confirms the practicability of our approach.


68T27 Logic in artificial intelligence
68N17 Logic programming
68T30 Knowledge representation
Full Text: DOI


[1] Alviano, M.; Faber, W.; Leone, N.; Manna, M., Disjunctive Datalog with existential quantifiers: semantics, decidability, and complexity issues, Theory Pract. Log. Program., 12, 4-5, 701-718, (2012) · Zbl 1260.68055
[2] Baader, F.; Hollunder, B., Embedding defaults into terminological knowledge representation formalisms, J. Autom. Reason., 14, 1, 149-180, (1995)
[3] Bartholomew, M.; Lee, J., A decidable class of groundable formulas in the general theory of stable models, (12th International Conf. Principles of Knowledge Representation and Reasoning, KR’10, (2010), AAAI Press), 477-485
[4] (Biere, A.; Heule, M. J.H.; van Maaren, H.; Walsh, T., Handbook of Satisfiability, Front. Artif. Intell. Appl., vol. 185, (2009), IOS Press) · Zbl 1183.68568
[5] Bonatti, P. A., Reasoning with infinite stable models II: disjunctive programs, (18th International Conf. Logic Programming, ICLP’02, LNCS, vol. 2401, (2002), Springer), 333-346 · Zbl 1045.68508
[6] Bonatti, P. A., Reasoning with infinite stable models, Artif. Intell., 156, 1, 75-111, (2004) · Zbl 1085.68681
[7] Brewka, G.; Eiter, T., Equilibria in heterogeneous nonmonotonic multi-context systems, (Holte, R. C.; Howe, A., 22nd National Conf. Artificial Intelligence, AAAI’07, (2007), AAAI Press), 385-390
[8] Brewka, G.; Eiter, T.; Truszczyński, M., Answer set programming at a glance, Commun. ACM, 54, 12, 92-103, (2011)
[9] Cabalar, P.; Pearce, D.; Valverde, A., A revised concept of safety for general answer set programs, (10th International Conf. Logic Programming and Nonmonotonic Reasoning, LPNMR’09, LNCS, vol. 5753, (2009), Springer), 58-70 · Zbl 1258.68026
[10] Calì, A.; Gottlob, G.; Lukasiewicz, T., \(\text{Datalog}^\pm\): a unified approach to ontologies and integrity constraints, (Proc. 12th International Conf. Database Theory, ICDT ’09, (2009), ACM), 14-30
[11] Calimeri, F.; Cozza, S.; Ianni, G., External sources of knowledge and value invention in logic programming, Ann. Math. Artif. Intell., 50, 3-4, 333-361, (2007) · Zbl 1125.68026
[12] Calimeri, F.; Cozza, S.; Ianni, G.; Leone, N., Computable functions in ASP: theory and implementation, (International Conf. Logic Programming, ICLP’08, LNCS, vol. 5366, (2008), Springer), 407-424 · Zbl 1185.68150
[13] F. Calimeri, W. Faber, M. Gebser, G. Ianni, R. Kaminski, T. Krennwallner, N. Leone, F. Ricca, T. Schaub, ASP-Core-2: 4th ASP competition official input language format, 2013.
[14] Dung, P. M., On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell., 77, 2, 321-357, (1995) · Zbl 1013.68556
[15] Dunne, P. E., The computational complexity of ideal semantics, Artif. Intell., 173, 18, 1559-1591, (2009) · Zbl 1185.68666
[16] Eiter, T.; Fink, M.; Ianni, G.; Krennwallner, T.; Schüller, P., Pushing efficient evaluation of HEX programs by modular decomposition, (Delgrande, J.; Faber, W., 11th Int’l Conf. Logic Programming and Nonmonotonic Reasoning, LPNMR’11, LNCS/LNAI, vol. 6645, (May 2011), Springer), 93-106 · Zbl 1327.68062
[17] Eiter, T.; Fink, M.; Krennwallner, T.; Redl, C., Conflict-driven ASP solving with external sources, Theory Pract. Log. Program., 12, 4-5, 659-679, (July 2012), special issue on ICLP 2012
[18] Eiter, T.; Fink, M.; Krennwallner, T.; Redl, C., Grounding HEX-programs with expanding domains, (Pearce, D.; Tasharrofi, S.; Ternovska, E.; Vidal, C., Informal Proc. 2nd Workshop on Grounding and Transformations for Theories with Variables, GTTV’13, Sept. 15, 2013, Corunna, Spain, (2013)), 3-15
[19] Eiter, T.; Fink, M.; Krennwallner, T.; Redl, C., Liberal safety criteria for HEX-programs, (desJardins, M.; Littman, M., 27th AAAI Conference, AAAI 2013, July 14-18, 2013, Bellevue, Washington, USA, (2013), AAAI Press), 267-275
[20] Eiter, T.; Fink, M.; Krennwallner, T.; Redl, C., Domain expansion for ASP-programs with external sources, (September 2014), Institut f. Informationssysteme, TU Wien, Tech. Rep. INFSYS RR-1843-14-02
[21] Eiter, T.; Fink, M.; Krennwallner, T.; Redl, C.; Schüller, P., Efficient HEX-program evaluation based on unfounded sets, J. Artif. Intell. Res., 49, 269-321, (2014) · Zbl 1361.68031
[22] Eiter, T.; Fink, M.; Redl, C.; Krennwallner, T., HEX-programs with existential quantification, (Hanus, M.; Rocha, R., Declarative Programming and Knowledge Management - Declarative Programming Days, KDPD 2013, Unifying INAP, WFLP, and WLP, Kiel, Germany, Sept. 11-13, 2013, LNCS, vol. 8439, (2014), Springer), 99-117, Revised Selected Papers
[23] Eiter, T.; Ianni, G.; Lukasiewicz, T.; Schindlauer, R.; Tompits, H., Combining answer set programming with description logics for the semantic web, Artif. Intell., 172, 12-13, 1495-1539, (2008) · Zbl 1183.68595
[24] Eiter, T.; Ianni, G.; Schindlauer, R.; Tompits, H., A uniform integration of higher-order reasoning and external evaluations in answer-set programming, (Kaelbling, L. P.; Saffiotti, A., 19th International Joint Conf. Artificial Intelligence, IJCAI’05, (2005), Professional Book Center), 90-96
[25] Eiter, T.; Ianni, G.; Schindlauer, R.; Tompits, H., Effective integration of declarative rules with external evaluations for semantic-web reasoning, (Sure, Y.; Domingue, J., 3rd European Conf. Semantic Web, ESWC’06, LNCS, vol. 4011, (2006), Springer), 273-287
[26] Eiter, T.; Krennwallner, T.; Prandtstetter, M.; Rudloff, C.; Schneider, P.; Straub, M., Semantically enriched multi-modal routing, Int. J. Intell. Transp. Syst. Res., (2014), Published online August 5, 2014
[27] Erdem, E.; Erdem, Y.; Erdogan, H.; Öztok, U., Finding answers and generating explanations for complex biomedical queries, (Burgard, W.; Roth, D., Proc 25th Conf. Artificial Intelligence, AAAI 2011, (2011), AAAI Press)
[28] Faber, W.; Leone, N.; Pfeifer, G., Semantics and complexity of recursive aggregates in answer set programming, Artif. Intell., 175, 1, 278-298, (January 2011)
[29] Gebser, M.; Kaufmann, B.; Kaminski, R.; Ostrowski, M.; Schaub, T.; Schneider, M., Potassco: the Potsdam answer set solving collection, AI Commun., 24, 2, 107-124, (2011) · Zbl 1215.68214
[30] Gebser, M.; Ostrowski, M.; Schaub, T., Constraint answer set solving, (Hill, P.; Warren, D., Proc. 25th Int’l Conf. Logic Programming, ICLP’09, LNCS, vol. 5649, (2009), Springer), 235-249 · Zbl 1251.68061
[31] Gebser, M.; Schaub, T.; Thiele, S., Gringo: a new grounder for answer set programming, (Proc. 9th International Conf. Logic Programming and Nonmonotonic Reasoning, LPNMR’07, LNCS, vol. 4483, (2007), Springer), 266-271
[32] Gelfond, M.; Lifschitz, V., Classical negation in logic programs and disjunctive databases, New Gener. Comput., 9, 3-4, 365-386, (1991) · Zbl 0735.68012
[33] Grau, B. C.; Horrocks, I.; Krötzsch, M.; Kupke, C.; Magka, D.; Motik, B.; Wang, Z., Acyclicity notions for existential rules and their application to query answering in ontologies, J. Artif. Intell. Res., 47, 741-808, (2013) · Zbl 1270.68295
[34] Greco, S.; Molinaro, C.; Trubitsyna, I., Bounded programs: a new decidable class of logic programs with function symbols, (Proceedings of the 23rd International Joint Conf. Artificial Intelligence, IJCAI 2013, (2013), AAAI Press), 926-931
[35] Greco, S.; Spezzano, F.; Trubitsyna, I., On the termination of logic programs with function symbols, (Dovier, A.; Costa, V. S., ICLP (Technical Communications), LIPIcs, vol. 17, (2012), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 323-333 · Zbl 1281.68065
[36] Hoehndorf, R.; Loebe, F.; Kelso, J.; Herre, H., Representing default knowledge in biomedical ontologies: application to the integration of anatomy and phenotype ontologies, BMC Bioinform., 8, 1, 377, (2007)
[37] Krishnamurthy, R.; Ramakrishnan, R.; Shmueli, O., A framework for testing safety and effective computability, J. Comput. Syst. Sci., 52, 1, 100-124, (1996) · Zbl 0846.68018
[38] O. Lassila, R. Swick, Resource description framework (RDF) model and syntax specification, 1999.
[39] Lee, J.; Lifschitz, V.; Palla, R., Safe formulas in the general theory of stable models (preliminary report), (24th Int’l Conf. Logic Programming, ICLP’08, LNCS, vol. 5366, (2008), Springer), 672-676 · Zbl 1185.68163
[40] 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, (Jul. 2006)
[41] Lierler, Y.; Lifschitz, V., One more decidable class of finitely ground programs, (25th International Conf. Logic Programming, ICLP’09, LNCS, vol. 5649, (2009), Springer), 489-493 · Zbl 1251.68064
[42] Marek, V.; Niemelä, I.; Truszczyśki, M., Logic programs with monotone cardinality atoms, (Proceedings LPNMR-2004, LNCS, vol. 2923, (2004), Springer), 154-166 · Zbl 1122.68380
[43] Mosca, A.; Bernini, D., Ontology-driven geographic information system and dlvhex reasoning for material culture analysis, (Italian Workshop RiCeRcA 2008, (2008))
[44] Ramakrishnan, R.; Bancilhon, F.; Silberschatz, A., Safety of recursive Horn clauses with infinite relations, (6th Symposium on Principles of Database Systems, PODS’87, (1987), ACM), 328-339
[45] Redl, C., Answer set programming with external sources: algorithms and efficient evaluation, (April 2014), TU Wien Austria, PhD thesis
[46] Sagiv, Y.; Vardi, M. Y., Safety of Datalog queries over infinite databases, (8th Symposium on Principles of Database Systems, PODS’89, (1989), ACM), 160-171
[47] Schüller, P.; Patoglu, V.; Erdem, E., Levels of integration between low-level reasoning and task planning, (Workshops at the 27th AAAI Conf. Artificial Intelligence, AAAI 2013 - Intelligent Robotic Systems, Bellevue, WA, July 14th, 2013, (2013), AAAI Press)
[48] Simons, P.; Niemelä, I.; Soininen, T., Extending and implementing the stable model semantics, Artif. Intell., 138, 181-234, (2002) · Zbl 0995.68021
[49] Syrjänen, T., Omega-restricted logic programs, (6th International Conf. Logic Programming and Nonmonotonic Reasoning, LPNMR’11, (2001), Springer), 267-279 · Zbl 1007.68503
[50] Zakraoui, J.; Zagler, W. L., A method for generating CSS to improve web accessibility for old users, (Int. Conf. on Computers Helping People with Special Needs, ICCHP, (2012)), 329-336
[51] Zantema, H., Termination of term rewriting: interpretation and type elimination, J. Symb. Comput., 17, 1, 23-50, (1994) · Zbl 0810.68087
[52] Zantema, H., The termination hierarchy for term rewriting, Appl. Algebra Eng. Commun. Comput., 12, 1-2, 3-19, (2001) · Zbl 0973.68099
[53] Zirtiloǧlu, H.; Yolum, P., Ranking semantic information for e-government: complaints management, (1st International Workshop on Ontology-supported Business Intelligence, OBI’08, No. 5 in OBI’08, (2008), ACM), 7
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.