{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:39Z","timestamp":1750306719677,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>\n            As evaluation methods for logic programs have become more sophisticated, the classes of programs for which termination can be guaranteed have expanded. From the perspective of ar set programs that include function symbols, recent work has identified classes for which grounding routines can terminate either on the entire program [Calimeri et al. 2008] or on suitable queries [Baselice et al. 2009]. From the perspective of tabling, it has long been known that a tabling technique called\n            <jats:italic>subgoal abstraction<\/jats:italic>\n            provides good termination properties for definite programs [Tamaki and Sato 1986], and this result was recently extended to stratified programs via the class of bounded term-size programs [Riguzzi and Swift 2013]. In this article, we provide a formal definition of tabling with subgoal abstraction resulting in the SLG\n            <jats:sub>SA<\/jats:sub>\n            algorithm. Moreover, we discuss a declarative characterization of the queries and programs for which SLG\n            <jats:sub>SA<\/jats:sub>\n            terminates. We call this class\n            <jats:italic>strongly bounded term-size programs<\/jats:italic>\n            and show its equivalence to programs with finite well-founded models. For normal programs, strongly bounded term-size programs strictly includes the finitely ground programs of Calimeri et al. [2008]. SLG\n            <jats:sub>SA<\/jats:sub>\n            has an asymptotic complexity on strongly bounded term-size programs equal to the best known and produces a residual program that can be sent to an answer set programming system. Finally, we describe the implementation of subgoal abstraction within the SLG-WAM of XSB and provide performance results.\n          <\/jats:p>","DOI":"10.1145\/2629337","type":"journal-article","created":{"date-parts":[[2014,9,17]],"date-time":"2014-09-17T14:22:25Z","timestamp":1410963745000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Terminating Evaluation of Logic Programs with Finite Three-Valued Models"],"prefix":"10.1145","volume":"15","author":[{"given":"Fabrizio","family":"Riguzzi","sequence":"first","affiliation":[{"name":"University of Ferrara, Ferrara, Italy"}]},{"given":"Terrance","family":"Swift","sequence":"additional","affiliation":[{"name":"Coherent Knowledge Systems, Inc. and NOVALincs, Universidade Nova de Lisboa, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2014,9,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2480759.2480768"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000244"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000232"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S147106840900372X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216374.1216378"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89982-2_37"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2350124.2350130"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068412000105"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/227595.227597"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11562931_25"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)90027-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/330643.330645"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376938"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1656242.1656249"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science","volume":"4483","author":"Gebser M.","unstructured":"M. Gebser , T. Schaub , and S. Thiele . 2007. GrinGo: A new grounder for answer set programming . In Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science , Vol. 4483 . Springer, 266--271. M. Gebser, T. Schaub, and S. Thiele. 2007. GrinGo: A new grounder for answer set programming. In Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, Vol. 4483. Springer, 266--271."},{"volume-title":"Proceedings of the International Conference and Symposium on Logic Programming. 1070--1080","author":"Gelfond M.","key":"e_1_2_1_17_1","unstructured":"M. Gelfond and V. Lifschitz . 1988. The stable model semantics for logic programming . In Proceedings of the International Conference and Symposium on Logic Programming. 1070--1080 . M. Gelfond and V. Lifschitz. 1988. The stable model semantics for logic programming. In Proceedings of the International Conference and Symposium on Logic Programming. 1070--1080."},{"volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)","author":"Greco S.","key":"e_1_2_1_18_1","unstructured":"S. Greco , C. Molinaro , and I. Trubitsyna . 2013. Bounded programs: A new decidable class of logic programs with function symbols . In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13) . 926--931. S. Greco, C. Molinaro, and I. Trubitsyna. 2013. Bounded programs: A new decidable class of logic programs with function symbols. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13). 926--931."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920858"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402750"},{"volume-title":"Proceedings of the International Conference on Logic Programming (Technical Communications). 323--333","author":"Greco S.","key":"e_1_2_1_21_1","unstructured":"S. Greco , F. Spezzano , and I. Trubitsyna . 2012. On the termination of logic programs with function symbols . In Proceedings of the International Conference on Logic Programming (Technical Communications). 323--333 . S. Greco, F. Spezzano, and I. Trubitsyna. 2012. On the termination of logic programs with function symbols. In Proceedings of the International Conference on Logic Programming (Technical Communications). 323--333."},{"key":"e_1_2_1_22_1","unstructured":"B. Grosof M. Dean and M. Kifer. 2012. Semantic Web rules: Fundamentals applications and standards. Tutorial presented at the 11th International Semantic Web Conference.  B. Grosof M. Dean and M. Kifer. 2012. Semantic Web rules: Fundamentals applications and standards. Tutorial presented at the 11th International Semantic Web Conference."},{"volume-title":"Proceedings of the 27th AAAI Conference (AAAI'13)","author":"Grosof B.","key":"e_1_2_1_23_1","unstructured":"B. Grosof and T. Swift . 2013. Radial restraint: A semantically clean approach to bounded rationality for logic programs . In Proceedings of the 27th AAAI Conference (AAAI'13) . B. Grosof and T. Swift. 2013. Radial restraint: A semantically clean approach to bounded rationality for logic programs. In Proceedings of the 27th AAAI Conference (AAAI'13)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068413000434"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the European Conference on Logics in Artificial Intelligence. Lecture Notes in Computer Science","volume":"2424","author":"Leone N.","unstructured":"N. Leone , G. Pfeifer , W. Faber , F. Calimeri , T. Dell'Armi , T. Eiter , G. Gottlob , G. Ianni , G. Ielpa , K. Koch , S. Perri , and A. Polleres . 2002. The DLV system . In Proceedings of the European Conference on Logics in Artificial Intelligence. Lecture Notes in Computer Science , Vol. 2424 . Springer, 537--540. N. Leone, G. Pfeifer, W. Faber, F. Calimeri, T. Dell'Armi, T. Eiter, G. Gottlob, G. Ianni, G. Ielpa, K. Koch, S. Perri, and A. Polleres. 2002. The DLV system. In Proceedings of the European Conference on Logics in Artificial Intelligence. Lecture Notes in Computer Science, Vol. 2424. Springer, 537--540."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068413000446"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02846-5_40"},{"volume-title":"Foundations of Logic Programming (2nd extended ed.)","author":"Lloyd J. W.","key":"e_1_2_1_28_1","unstructured":"J. W. Lloyd . 1987. Foundations of Logic Programming (2nd extended ed.) . Springer-Verlag . J. W. Lloyd. 1987. Foundations of Logic Programming (2nd extended ed.). Springer-Verlag."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559799"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687737"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11562931_24"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78769-3_2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-010-0122-4"},{"volume-title":"OpenRuleBench: Benchmarks for Semantic Web rule engines. Retrieved","year":"2014","key":"e_1_2_1_34_1","unstructured":"OpenRuleBench. 2009--2011. OpenRuleBench: Benchmarks for Semantic Web rule engines. Retrieved July 9, 2014 , from http:\/\/rulebench.projects.semwebcentral.org. OpenRuleBench. 2009--2011. OpenRuleBench: Benchmarks for Semantic Web rule engines. Retrieved July 9, 2014, from http:\/\/rulebench.projects.semwebcentral.org."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068402001400"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73723"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(98)10013-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000664"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/291889.291897"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1614431.1614433"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068404002042"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-005-6546-z"},{"key":"e_1_2_1_43_1","series-title":"Lecture Notes in Artificial Intelligence","volume-title":"Proceedings of the Portuguese Conference on Artificial Intelligence","author":"Swift T.","unstructured":"T. Swift . 1999. A new formulation of tabled resolution with delay . In Proceedings of the Portuguese Conference on Artificial Intelligence . Lecture Notes in Artificial Intelligence , Vol. 1695 . Springer , 163--177. T. Swift. 1999. A new formulation of tabled resolution with delay. In Proceedings of the Portuguese Conference on Artificial Intelligence. Lecture Notes in Artificial Intelligence, Vol. 1695. Springer, 163--177."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000500"},{"key":"e_1_2_1_45_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning","author":"Syrjanen T.","unstructured":"T. Syrjanen . 2001. Omega-restricted logic programs . In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning . Lecture Notes in Computer Science , Vol. 2173 . Springer , 267--280. T. Syrjanen. 2001. Omega-restricted logic programs. In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, Vol. 2173. Springer, 267--280."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 3rd International Conference on Logic Programming. Lecture Notes in Computer Science","volume":"225","author":"Tamaki H.","unstructured":"H. Tamaki and T. Sato . 1986. OLD resolution with tabulation . In Proceedings of the 3rd International Conference on Logic Programming. Lecture Notes in Computer Science , Vol. 225 . Springer, 84--98. H. Tamaki and T. Sato. 1986. OLD resolution with tabulation. In Proceedings of the 3rd International Conference on Logic Programming. Lecture Notes in Computer Science, Vol. 225. Springer, 84--98."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73722"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116838"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/371282.371357"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000159"},{"key":"e_1_2_1_51_1","first-page":"99","article-title":"Knowledge Representation & Reasoning with Flora-2. Flora-2","volume":"0","author":"Yang G.","year":"2013","unstructured":"G. Yang , M. Kifer , H. Wan , and C. Zhao . 2013 . Knowledge Representation & Reasoning with Flora-2. Flora-2 : User's Manual Version 0 . 99 .3. Retrieved July 9, 2014, from http:\/\/flora.sourceforge.net. G. Yang, M. Kifer, H. Wan, and C. Zhao. 2013. Knowledge Representation & Reasoning with Flora-2. Flora-2: User's Manual Version 0.99.3. Retrieved July 9, 2014, from http:\/\/flora.sourceforge.net.","journal-title":"User's Manual Version"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:30Z","timestamp":1750231170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1145\/2629337"],"URL":"https:\/\/doi.org\/10.1145\/2629337","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}