{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T22:48:39Z","timestamp":1776898119412,"version":"3.51.2"},"reference-count":67,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T00:00:00Z","timestamp":1658707200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide a comprehensive elaboration of the theoretical foundations of variable instantiation, or grounding, in Answer Set Programming (ASP). Building on the semantics of ASP\u2019s modeling language, we introduce a formal characterization of grounding algorithms in terms of (fixed point) operators. A major role is played by dedicated well-founded operators whose associated models provide semantic guidance for delineating the result of grounding along with on-the-fly simplifications. We address an expressive class of logic programs that incorporates recursive aggregates and thus amounts to the scope of existing ASP modeling languages. This is accompanied with a plain algorithmic framework detailing the grounding of recursive aggregates. The given algorithms correspond essentially to the ones used in the ASP grounder <jats:italic>gringo<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s1471068422000308","type":"journal-article","created":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T08:51:38Z","timestamp":1658739098000},"page":"1138-1197","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["On the Foundations of Grounding in Answer Set Programming"],"prefix":"10.1017","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1361-6045","authenticated-orcid":false,"given":"ROLAND","family":"KAMINSKI","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7456-041X","authenticated-orcid":false,"given":"TORSTEN","family":"SCHAUB","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2022,7,25]]},"reference":[{"key":"S1471068422000308_ref24","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Kaminski, R. , Kaufmann, B. and Schaub, T. 2009. On the implementation of weight constraint rules in conflict-driven ASP solvers. In Proceedings of the Twenty-fifth International Conference on Logic Programming (ICLP\u201909). Lecture Notes in Computer Science, vol. 5649. Springer-Verlag, 250\u2013264.","DOI":"10.1007\/978-3-642-02846-5_23"},{"key":"S1471068422000308_ref28","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Kaufmann, B. and Schaub, T. 2012. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence 187-188, 52\u201389.","DOI":"10.1016\/j.artint.2012.04.001"},{"key":"S1471068422000308_ref1","volume-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"key":"S1471068422000308_ref14","doi-asserted-by":"crossref","unstructured":"Eiter, T. , Leone, N. , Mateis, C. , Pfeifer, G. and Scarcello, F. 1997. A deductive system for nonmonotonic reasoning. In Proceedings of the Fourth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201997), J. Dix, U. Furbach and A. Nerode, Eds. Lecture Notes in Artificial Intelligence, vol. 1265. Springer-Verlag, 363\u2013374.","DOI":"10.1007\/3-540-63255-7_27"},{"key":"S1471068422000308_ref16","unstructured":"Faber, W. , Leone, N. , Perri, S. and Pfeifer, G. 2001. Efficient instantiation of disjunctive databases. Technical Report DBAI-TR-2001-44, Technische Universit\u00c4t Wien."},{"key":"S1471068422000308_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001923"},{"key":"S1471068422000308_ref26","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Kaminski, R. , Ostrowski, M. , Schaub, T. and Thiele, S. 2009. On the input language of ASP grounder gringo. In Proceedings of the Tenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201909), E. Erdem, F. Lin and T. Schaub, Eds. Lecture Notes in Artificial Intelligence, vol. 5753. Springer-Verlag, 502\u2013508.","DOI":"10.1007\/978-3-642-04238-6_49"},{"key":"S1471068422000308_ref4","volume-title":"Modern Uses of Multiple-Valued Logic","author":"Belnap","year":"1977"},{"key":"S1471068422000308_ref36","unstructured":"Harrison, A. , Lifschitz, V. and Yang, F. 2014. The semantics of gringo and infinitary propositional formulas. In Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR\u201914), C. Baral, G. De Giacomo and T. Eiter, Eds. AAAI Press."},{"key":"S1471068422000308_ref9","doi-asserted-by":"crossref","unstructured":"Calimeri, F. , Cozza, S. , Ianni, G. and Leone, N. 2008. Computable functions in ASP: Theory and implementation. In Proceedings of the Twenty-fourth International Conference on Logic Programming (ICLP\u201908). Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, 407\u2013424.","DOI":"10.1007\/978-3-540-89982-2_37"},{"key":"S1471068422000308_ref6","first-page":"1","article-title":"Semantics of (disjunctive) logic programs based on partial evaluation","volume":"1","author":"Brass","year":"1999","journal-title":"Journal of Logic Programming 40"},{"key":"S1471068422000308_ref53","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2009-180"},{"key":"S1471068422000308_ref31","unstructured":"Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of the Fifth International Conference and Symposium of Logic Programming (ICLP\u201988), R. Kowalski and K. Bowen, Eds. MIT Press, 1070\u20131080."},{"key":"S1471068422000308_ref30","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Schaub, T. and Thiele, S. 2007. Gringo: A new grounder for answer set programming. In Proceedings of the Ninth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201907). Lecture Notes in Artificial Intelligence, vol. 4483. Springer-Verlag, 266\u2013271.","DOI":"10.1007\/978-3-540-72200-7_24"},{"key":"S1471068422000308_ref49","first-page":"82","article-title":"Die logik und das grundlagenproblem","volume":"12","author":"Lukasiewicz","year":"1941","journal-title":"Les Entreties de Z\u00dcrich sur les Fondaments et la M\u00c9thode des Sciences Math\u00c9matiques"},{"key":"S1471068422000308_ref54","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002973"},{"key":"S1471068422000308_ref42","doi-asserted-by":"crossref","unstructured":"Leone, N. , Perri, S. and Scarcello, F. 2001. Improving ASP instantiators by join-ordering methods. In Proceedings of the Sixth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201901). Lecture Notes in Computer Science, vol. 2173. Springer-Verlag, 280\u2013294.","DOI":"10.1007\/3-540-45402-0_21"},{"key":"S1471068422000308_ref48","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.004"},{"key":"S1471068422000308_ref51","unstructured":"Mumick, I. , Pirahesh, H. and Ramakrishnan, R. 1990. The magic of duplicates and aggregates. In Proceedings of the Sixteenth International Conference on Very Large Data Bases (VLDB\u201990), D. McLeod, R. Sacks-Davis and H. Schek, Eds. Morgan Kaufmann Publishers, 264\u2013277."},{"key":"S1471068422000308_ref41","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068416000569"},{"key":"S1471068422000308_ref67","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2980"},{"key":"S1471068422000308_ref66","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068420000332"},{"key":"S1471068422000308_ref50","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"Martello","year":"1990"},{"key":"S1471068422000308_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S147106840100103X"},{"key":"S1471068422000308_ref17","first-page":"25","article-title":"Logic programs with propositional connectives and aggregates","volume":"4","author":"Ferraris","year":"2011","journal-title":"ACM Transactions on Computational Logic 12"},{"key":"S1471068422000308_ref23","volume-title":"Potassco User Guide","author":"Gebser","year":"2015"},{"key":"S1471068422000308_ref37","doi-asserted-by":"crossref","unstructured":"Janhunen, T. 2001. On the effect of default negation on the expressiveness of disjunctive rules. In Proceedings of the Sixth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201901). Lecture Notes in Computer Science, vol. 2173. Springer-Verlag, 93\u2013106.","DOI":"10.1007\/3-540-45402-0_7"},{"key":"S1471068422000308_ref57","unstructured":"Syrj\u00e4nen, T. 2001a. Lparse 1.0 user\u2019s manual."},{"key":"S1471068422000308_ref45","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00186-8"},{"key":"S1471068422000308_ref55","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-008-9090-9"},{"key":"S1471068422000308_ref56","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"S1471068422000308_ref2","doi-asserted-by":"crossref","unstructured":"Alviano, M. , Dodaro, C. , Leone, N. and Ricca, F. 2015. Advances in WASP. In Proceedings of the Thirteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201915), F. Calimeri, G. Ianni and M. Truszczy\u0144ski, Eds. Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag, 40\u201354.","DOI":"10.1007\/978-3-319-23264-5_5"},{"key":"S1471068422000308_ref52","doi-asserted-by":"crossref","unstructured":"Niemel\u00e4, I. 2008. Answer set programming without unstratified negation. In Proceedings of the Twenty-fourth International Conference on Logic Programming (ICLP\u201908). Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, 88\u201392.","DOI":"10.1007\/978-3-540-89982-2_15"},{"key":"S1471068422000308_ref62","volume-title":"Principles of Database and Knowledge-Base Systems","author":"Ullman","year":"1988"},{"key":"S1471068422000308_ref8","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2679"},{"key":"S1471068422000308_ref15","first-page":"247","volume-title":"Computer Science","volume":"7265","author":"Faber","year":"2012"},{"key":"S1471068422000308_ref38","doi-asserted-by":"crossref","unstructured":"Janhunen, T. , Oikarinen, E. , Tompits, H. and Woltran, S. 2007. Modularity aspects of disjunctive stable models. In Proceedings of the Ninth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201907). Lecture Notes in Artificial Intelligence, vol. 4483. Springer-Verlag, 175\u2013187.","DOI":"10.1007\/978-3-540-72200-7_16"},{"key":"S1471068422000308_ref44","doi-asserted-by":"crossref","unstructured":"Lierler, Y. and Lifschitz, V. 2009. One more decidable class of finitely ground programs. In Proceedings of the Twenty-fifth International Conference on Logic Programming (ICLP\u201909). Lecture Notes in Computer Science, vol. 5649. Springer-Verlag, 489\u2013493.","DOI":"10.1007\/978-3-642-02846-5_40"},{"key":"S1471068422000308_ref43","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068422000308_ref65","unstructured":"Vanbesien, L. , Bruynooghe, M. and Denecker, M. 2021. Analyzing semantics of aggregate answer set programming using approximation fixpoint theory. CoRR abs\/2104.14789."},{"key":"S1471068422000308_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00330-3"},{"key":"S1471068422000308_ref60","doi-asserted-by":"crossref","unstructured":"Truszczy\u0144ski, M. 2012. Connecting first-order ASP and the logic FO(ID) through reducts. In Correct Reasoning: Essays on Logic-Based AI in Honour of Vladimir Lifschitz. Lecture Notes in Computer Science, vol. 7265. Springer-Verlag, 543\u2013559.","DOI":"10.1007\/978-3-642-30743-0_37"},{"key":"S1471068422000308_ref21","volume-title":"Database Systems: The Complete Book","author":"Garcia-Molina","year":"2009"},{"key":"S1471068422000308_ref12","unstructured":"Dell\u2019Armi, T. , Faber, W. , Ielpa, G. , Leone, N. and Pfeifer, G. 2003. Aggregate functions in disjunctive logic programming: Semantics, complexity, and implementation in DLV. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI\u201903), G. Gottlob and T. Walsh, Eds. Morgan Kaufmann Publishers, 847\u2013852."},{"key":"S1471068422000308_ref29","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2673"},{"key":"S1471068422000308_ref58","doi-asserted-by":"crossref","unstructured":"Syrj\u00e4nen, T. 2001b. Omega-restricted logic programs. In Proceedings of the Sixth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201901). Lecture Notes in Computer Science, vol. 2173. Springer-Verlag, 267\u2013279.","DOI":"10.1007\/3-540-45402-0_20"},{"key":"S1471068422000308_ref18","unstructured":"Ferraris, P. , Lee, J. , Lifschitz, V. and Palla, R. 2009. Symmetric splitting in the general theory of stable models. In Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence (IJCAI\u201909), C. Boutilier, Ed. AAAI\/MIT Press, 797\u2013803."},{"key":"S1471068422000308_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068415000228"},{"key":"S1471068422000308_ref10","doi-asserted-by":"publisher","DOI":"10.3233\/IA-170104"},{"key":"S1471068422000308_ref27","unstructured":"Gebser, M. , Kaminski, R. and Schaub, T. 2015c. Grounding recursive aggregates: Preliminary report. In Proceedings of the Third Workshop on Grounding, Transforming, and Modularizing Theories with Variables (GTTV\u201915), M. Denecker and T. Janhunen, Eds."},{"key":"S1471068422000308_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068416000314"},{"key":"S1471068422000308_ref64","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90024-Q"},{"key":"S1471068422000308_ref11","unstructured":"De Cat, B. , Bogaerts, B. , Bruynooghe, M. and Denecker, M. 2014. Predicate logic as a modelling language: The IDP system. CoRR abs\/1401.6312."},{"key":"S1471068422000308_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.02.002"},{"key":"S1471068422000308_ref39","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2672"},{"key":"S1471068422000308_ref47","unstructured":"Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In Proceedings of the Eleventh International Conference on Logic Programming. MIT Press, 23\u201337."},{"key":"S1471068422000308_ref25","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Kaminski, R. , K\u00f6nig, A. and Schaub, T. 2011. Advances in gringo series 3. In Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201911), J. Delgrande and W. Faber, Eds. Notes, Lecture in Artificial Intelligence, vol. 6645. Springer-Verlag, 345\u2013351.","DOI":"10.1007\/978-3-642-20895-9_39"},{"key":"S1471068422000308_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068415000150"},{"key":"S1471068422000308_ref61","doi-asserted-by":"publisher","DOI":"10.1145\/3191315.3191318"},{"key":"S1471068422000308_ref59","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.285"},{"key":"S1471068422000308_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068422000308_ref13","doi-asserted-by":"crossref","unstructured":"Denecker, M. , Marek, V. and Truszczy\u0144ski, M. 2000. Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning. In Logic-Based Artificial Intelligence, J. Minker, Ed. Kluwer Academic Publishers, Dordrecht, 127\u2013144.","DOI":"10.1007\/978-1-4615-1567-8_6"},{"key":"S1471068422000308_ref5","doi-asserted-by":"crossref","unstructured":"Bomanson, J. , Gebser, M. and Janhunen, T. 2014. Improving the normalization of weight rules in answer set programs. In Proceedings of the Fourteenth European Conference on Logics in Artificial Intelligence (JELIA\u201914), E. Ferm\u00e9 and J. Leite, Eds. Lecture Notes in Artificial Intelligence, vol. 8761. Springer-Verlag, 166\u2013180.","DOI":"10.1007\/978-3-319-11558-0_12"},{"key":"S1471068422000308_ref40","unstructured":"Kemp, D. , Stuckey, P. and Srivastava, D. 1991. Magic sets and bottom-up evaluation of well-founded models. In Logic Programming, Proceedings of the 1991 International Symposium. MIT Press, 337\u2013351."},{"key":"S1471068422000308_ref33","first-page":"345","article-title":"Answer set programming based on propositional satisfiability","volume":"4","author":"Giunchiglia","year":"2006","journal-title":"Journal of Automated Reasoning 36"},{"key":"S1471068422000308_ref46","doi-asserted-by":"crossref","unstructured":"Lifschitz, V. 2008. Twelve definitions of a stable model. In Proceedings of the Twenty-fourth International Conference on Logic Programming (ICLP\u201908). Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, 37\u201351.","DOI":"10.1007\/978-3-540-89982-2_8"},{"key":"S1471068422000308_ref63","doi-asserted-by":"publisher","DOI":"10.1145\/321978.321991"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068422000308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T12:06:46Z","timestamp":1706098006000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068422000308\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,25]]},"references-count":67,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["S1471068422000308"],"URL":"https:\/\/doi.org\/10.1017\/s1471068422000308","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,25]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}