{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T00:57:37Z","timestamp":1649206657881},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T00:00:00Z","timestamp":1476403200000},"content-version":"unspecified","delay-in-days":43,"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":[[2016,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Tabling is a powerful resolution mechanism for logic programs that captures their least fixed point semantics more faithfully than plain Prolog. In many tabling applications, we are not interested in the set of all answers to a goal, but only require an aggregation of those answers. Several works have studied efficient techniques, such as lattice-based answer subsumption and mode-directed tabling, to do so for various forms of aggregation.<\/jats:p><jats:p>While much attention has been paid to expressivity and efficient implementation of the different approaches, soundness has not been considered. This paper shows that the different implementations indeed fail to produce least fixed points for some programs. As a remedy, we provide a formal framework that generalises the existing approaches and we establish a soundness criterion that explains for which programs the approach is sound.<\/jats:p>","DOI":"10.1017\/s147106841600048x","type":"journal-article","created":{"date-parts":[[2016,10,15]],"date-time":"2016-10-15T17:28:20Z","timestamp":1476552500000},"page":"933-949","source":"Crossref","is-referenced-by-count":1,"title":["Tabling with Sound Answer Subsumption"],"prefix":"10.1017","volume":"16","author":[{"given":"ALEXANDER","family":"VANDENBROUCKE","sequence":"first","affiliation":[]},{"given":"MACIEJ","family":"PIR\u00d3G","sequence":"additional","affiliation":[]},{"given":"BENOIT","family":"DESOUTER","sequence":"additional","affiliation":[]},{"given":"TOM","family":"SCHRIJVERS","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2016,10,14]]},"reference":[{"key":"S147106841600048X_ref11","volume-title":"Matroid theory","author":"Oxley","year":"1992"},{"key":"S147106841600048X_ref18","unstructured":"Van Hentenryck P. , Degimbe O. , Charlier B. L. and Michel L. 1993. Abstract interpretation of Prolog based on OLDT resolution. Tech. rep., Providence, RI, USA."},{"key":"S147106841600048X_ref3","first-page":"89","volume-title":"Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, International Summer School and Workshop, Oxford, UK, April 10-14, 2000, Revised Lectures","author":"Backhouse","year":"2000"},{"key":"S147106841600048X_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-96826-6"},{"key":"S147106841600048X_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24836-1_12"},{"key":"S147106841600048X_ref7","first-page":"75","article-title":"Simplifying dynamic programming via mode-directed tabling.","volume":"38","author":"Guo","year":"2008","journal-title":"Software: Practice and Experience"},{"key":"S147106841600048X_ref1","unstructured":"Abramsky S. and Hankin C. 1987. Abstract Interpretation of declarative languages. Vol. 1. Ellis Horwood, Chapter An introduction to abstract interpretation, 63\u2013102."},{"key":"S147106841600048X_ref21","doi-asserted-by":"crossref","unstructured":"Zhou N. F. and Dovier A. 2011. A tabled Prolog program for solving sokoban. In 2011 IEEE 23rd International Conference on Tools with Artificial Intelligence. 896\u2013897.","DOI":"10.1109\/ICTAI.2011.145"},{"key":"S147106841600048X_ref16","unstructured":"Swift T. and Warren D. 2010. Tabling with answer subsumption: Implementation, applications performance. 300\u2013312."},{"key":"S147106841600048X_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000512"},{"key":"S147106841600048X_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77442-6_14"},{"key":"S147106841600048X_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000445"},{"key":"S147106841600048X_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45284-0_10"},{"key":"S147106841600048X_ref15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018990308362"},{"key":"S147106841600048X_ref10","doi-asserted-by":"crossref","unstructured":"MacNeille H. M. 1937. Partially ordered sets. Transactions of the American Mathematical Society, 416\u2013460.","DOI":"10.1090\/S0002-9947-1937-1501929-X"},{"key":"S147106841600048X_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000500"},{"key":"S147106841600048X_ref8","unstructured":"Korte B. , Lov\u00e1sz L. and Schrader R. 1991. Greedoids, algorithms and combinatorics, vol. 4."},{"key":"S147106841600048X_ref19","doi-asserted-by":"crossref","unstructured":"Vandenbroucke A. , Schrijvers T. and Piessens F. 2016. Fixing non-determinism. In Proceedings of the 27th symposium on Implementation and Application of Functional Languages 2015.","DOI":"10.1145\/2897336.2897342"},{"key":"S147106841600048X_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"S147106841600048X_ref22","doi-asserted-by":"crossref","unstructured":"Zhou N.-F. , Kameya Y. and Sato T. 2010. Mode-directed tabling for dynamic programming, machine learning, and constraint solving. In 22nd International Conference on Tools with Artificial Intelligence (ICTAI), 2010. Vol. 2. 213\u2013218.","DOI":"10.1109\/ICTAI.2010.103"},{"key":"S147106841600048X_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63166-6_16"},{"key":"S147106841600048X_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(92)90030-7"}],"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\/S147106841600048X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,14]],"date-time":"2019-09-14T13:04:36Z","timestamp":1568466276000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106841600048X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":22,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S147106841600048X"],"URL":"https:\/\/doi.org\/10.1017\/s147106841600048x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}