{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T21:50:43Z","timestamp":1757541043316},"reference-count":48,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2012,1,25]],"date-time":"2012-01-25T00:00:00Z","timestamp":1327449600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Answer-Set Programming (ASP) is a powerful logic-based programming language, which is enjoying increasing interest within the scientific community and (very recently) in industry. The evaluation of Answer-Set Programs is traditionally carried out in two steps. At the first step, an input program <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1471068411000652_char1\" \/><\/jats:private-char> undergoes the so-called instantiation (or grounding) process, which produces a program <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1471068411000652_char1\" \/><\/jats:private-char>\u2032 semantically equivalent to <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1471068411000652_char1\" \/><\/jats:private-char>, but not containing any variable; in turn, <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1471068411000652_char1\" \/><\/jats:private-char>\u2032 is evaluated by using a backtracking search algorithm in the second step. It is well-known that instantiation is important for the efficiency of the whole evaluation, might become a bottleneck in common situations, is crucial in several real-world applications, and is particularly relevant when huge input data have to be dealt with. At the time of this writing, the available instantiator modules are not able to exploit satisfactorily the latest hardware, featuring multi-core\/multi-processor Symmetric MultiProcessing technologies. This paper presents some parallel instantiation techniques, including load-balancing and granularity control heuristics, which allow for the effective exploitation of the processing power offered by modern Symmetric MultiProcessing machines. This is confirmed by an extensive experimental analysis reported herein.<\/jats:p>","DOI":"10.1017\/s1471068411000652","type":"journal-article","created":{"date-parts":[[2012,1,25]],"date-time":"2012-01-25T09:20:37Z","timestamp":1327483237000},"page":"253-278","source":"Crossref","is-referenced-by-count":12,"title":["Parallel instantiation of ASP programs: techniques and experiments"],"prefix":"10.1017","volume":"13","author":[{"given":"SIMONA","family":"PERRI","sequence":"first","affiliation":[]},{"given":"FRANCESCO","family":"RICCA","sequence":"additional","affiliation":[]},{"given":"MARCO","family":"SIRIANNI","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,1,25]]},"reference":[{"key":"S1471068411000652_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543357"},{"key":"S1471068411000652_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/11546207_18"},{"key":"S1471068411000652_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/383779.383785"},{"key":"S1471068411000652_ref24","first-page":"1","volume-title":"Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond","author":"Grasso","year":"2011"},{"key":"S1471068411000652_ref28","volume-title":"The Stanford GraphBase: A Platform for Combinatorial Computing","author":"Knuth","year":"1994"},{"key":"S1471068411000652_ref39","unstructured":"Perri S. , Ricca F. and Vescio S. 2008. Efficient parallel ASP instantiation via dynamic rewriting. In Proc. of the First Workshop on Answer Set Programming and Other Computing Paradigms. ASPOCP '08, 16\u201330."},{"key":"S1471068411000652_ref8","first-page":"108","volume-title":"Proc. of the 1986 International Conference on Management of Data","author":"Carey","year":"1986"},{"key":"S1471068411000652_ref43","volume-title":"Operating Systems: Internals and Design Principles","author":"Stallings","year":"1998"},{"key":"S1471068411000652_ref44","doi-asserted-by":"publisher","DOI":"10.1109\/69.390244"},{"key":"S1471068411000652_ref32","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068411000652_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068411000652_ref33","first-page":"346","volume-title":"Proc. of the 7th International Conference on Logic Programming and Non-Monotonic Reasoning","author":"Lierler","year":"2004"},{"key":"S1471068411000652_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11503-5_5"},{"key":"S1471068411000652_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1119439.1119440"},{"key":"S1471068411000652_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2005.03.004"},{"key":"S1471068411000652_ref31","unstructured":"Leone N. , Perri S. and Scarcello F. 2004. BackJumping techniques for rules instantiation in the DLV system. In Proc. of the 10th International Workshop on Non-monotonic Reasoning. NMR '04. 258\u2013266."},{"key":"S1471068411000652_ref16","first-page":"72","volume-title":"Proc. of the Symposium on Answer Set Programming, Towards Efficient and Scalable Knowledge Representation and Reasoning","author":"Finkel","year":"2001"},{"key":"S1471068411000652_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72200-7_3"},{"key":"S1471068411000652_ref48","doi-asserted-by":"publisher","DOI":"10.1109\/69.368511"},{"key":"S1471068411000652_ref7","first-page":"34","article-title":"Experimenting with parallelism for the instantiation of ASP programs","volume":"63","author":"Calimeri","year":"2008","journal-title":"Journal of Algorithms in Cognition, Informatics and Logics"},{"key":"S1471068411000652_ref2","first-page":"406","volume-title":"Proc. of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning","author":"Anger","year":"2001"},{"key":"S1471068411000652_ref5","first-page":"186","volume-title":"Proc. of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning","author":"Baral","year":"2001"},{"key":"S1471068411000652_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/195613.195637"},{"key":"S1471068411000652_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"S1471068411000652_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_75"},{"key":"S1471068411000652_ref11","first-page":"277","volume-title":"Proc. of the 1994 International Conference on Management of Data","author":"Dewan","year":"1994"},{"key":"S1471068411000652_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"S1471068411000652_ref45","volume-title":"Principles of Database and Knowledge Base Systems","author":"Ullman","year":"1989"},{"key":"S1471068411000652_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_47"},{"key":"S1471068411000652_ref14","first-page":"135","volume-title":"Proc. of the 7th International Workshop on Deductive Databases and Logic Programming","author":"Faber","year":"1999"},{"key":"S1471068411000652_ref15","first-page":"200","volume-title":"Proc. of the 9th European Conference on Artificial Intelligence","author":"Faber","year":"2004"},{"key":"S1471068411000652_ref47","first-page":"329","volume-title":"Proc. of the 1988 International Conference on Management of Data","author":"Wolfson","year":"1988"},{"key":"S1471068411000652_ref17","first-page":"143","volume-title":"Proc. of the 1990 International Conference on Management of Data","author":"Ganguly","year":"1990"},{"key":"S1471068411000652_ref42","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"S1471068411000652_ref18","first-page":"386","volume-title":"Proc. of the 10th International Joint Conference on Artificial Intelligence","author":"Gebser","year":"2007"},{"key":"S1471068411000652_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72200-7_24"},{"key":"S1471068411000652_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00207-2"},{"key":"S1471068411000652_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068411000652_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_31"},{"key":"S1471068411000652_ref29","unstructured":"Lembo D. , Lenzerini M. and Rosati R. 2002. Integrating inconsistent and incomplete data sources. In Proc. of the 10th Italian Symposium on Advanced Database Systems 2005. SEBD '05. 299\u2013308."},{"key":"S1471068411000652_ref30","first-page":"280","volume-title":"Proc. of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning","author":"Leone","year":"2001"},{"key":"S1471068411000652_ref34","first-page":"23","volume-title":"Proc. of the 16th International Conference on Logic Programming","author":"Lifschitz","year":"1999"},{"key":"S1471068411000652_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.004"},{"key":"S1471068411000652_ref37","first-page":"421","volume-title":"Proc. of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning","author":"Niemel\u00e4","year":"1997"},{"key":"S1471068411000652_ref38","doi-asserted-by":"publisher","DOI":"10.1145\/1708046.1708060"},{"key":"S1471068411000652_ref40","first-page":"174","volume-title":"Proc. of the Symposium on Answer Set Programming, Towards Efficient and Scalable Knowledge Representation and Reasoning","author":"Pontelli","year":"2001"},{"key":"S1471068411000652_ref41","unstructured":"Simons P. 2000. Extending and Implementing the Stable Model Semantics. PhD thesis, Helsinki University of Technology, Finland."},{"key":"S1471068411000652_ref46","first-page":"133","volume-title":"Proc. of the 1990 International Conference on Management of Data","author":"Wolfson","year":"1990"}],"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\/S1471068411000652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T15:18:36Z","timestamp":1556119116000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068411000652\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,25]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["S1471068411000652"],"URL":"https:\/\/doi.org\/10.1017\/s1471068411000652","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,25]]}}}