{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T02:12:45Z","timestamp":1712369565927},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2012,9,5]],"date-time":"2012-09-05T00:00:00Z","timestamp":1346803200000},"content-version":"unspecified","delay-in-days":66,"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":[[2012,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Current tabling systems suffer from an increase in space complexity, time complexity or both when dealing with sequences due to the use of data structures for tabled subgoals and answers and the need to copy terms into and from the table area. This symptom can be seen in not only B-Prolog, which uses hash tables, but also systems that use tries such as XSB and YAP. In this paper, we apply hash-consing to tabling structured data in B-Prolog. While hash-consing can reduce the space consumption when sharing is effective, it does not change the time complexity. We enhance hash-consing with two techniques, called <jats:italic>input sharing<\/jats:italic> and <jats:italic>hash code memoization<\/jats:italic>, for reducing the time complexity by avoiding computing hash codes for certain terms. The improved system is able to eliminate the extra linear factor in the old system for processing sequences, thus significantly enhancing the scalability of applications such as language parsing and bio-sequence analysis applications. We confirm this improvement with experimental results.<\/jats:p>","DOI":"10.1017\/s1471068412000178","type":"journal-article","created":{"date-parts":[[2012,9,5]],"date-time":"2012-09-05T07:28:45Z","timestamp":1346830125000},"page":"547-563","source":"Crossref","is-referenced-by-count":6,"title":["Efficient tabling of structured data with enhanced hash-consing"],"prefix":"10.1017","volume":"12","author":[{"given":"NENG-FA","family":"ZHOU","sequence":"first","affiliation":[]},{"given":"CHRISTIAN THEIL","family":"HAVE","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,9,5]]},"reference":[{"key":"S1471068412000178_ref10","first-page":"617","article-title":"O(1) reversible tree navigation without cycle","volume":"1","author":"O'Keefe","year":"2001","journal-title":"TPLP"},{"key":"S1471068412000178_ref9","unstructured":"Nguyen P.-L. and Demoen B. 2012. Representation sharing for Prolog. TPLP."},{"key":"S1471068412000178_ref7","unstructured":"Michie D. 1968. \u201cMemo\u201d functions and machine learning. Nature, 19\u201322."},{"key":"S1471068412000178_ref1","volume-title":"Hash-Consing Garbage Collection","author":"Appel","year":"2003"},{"key":"S1471068412000178_ref20","first-page":"189","article-title":"The language features and architecture of B-Prolog","volume":"12","author":"Zhou","year":"2012","journal-title":"TPLP, Special Issue on Prolog Systems"},{"key":"S1471068412000178_ref16","unstructured":"Somogyi Z. and Sagonas K. 2006. Tabling in Mercury: Design and implementation. In PADL. LNCS 3819, 150\u2013167."},{"key":"S1471068412000178_ref14","doi-asserted-by":"crossref","unstructured":"Sato T. and Kameya Y. 2008. New advances in logic-based probabilistic modeling by PRISM. In Probabilistic Inductive Logic Programming. 118\u2013155.","DOI":"10.1007\/978-3-540-78652-8_5"},{"key":"S1471068412000178_ref2","first-page":"101","article-title":"A sharing of structure in theorem proving programs","volume":"7","author":"Boyer","year":"1972","journal-title":"Machine Intelligence"},{"key":"S1471068412000178_ref5","volume-title":"Monocopy and Associative Algorithms in Extended Lisp","author":"Goto","year":"1974"},{"key":"S1471068412000178_ref13","first-page":"5","article-title":"The YAP Prolog system","volume":"12","author":"Rocha","year":"2012","journal-title":"TPLP, Special Issue on Prolog Systems"},{"key":"S1471068412000178_ref6","unstructured":"Have C. T. and Christiansen H. 2012. Efficient tabling of structured data using indexing and program transformation. In PADL. LNCS 7149, 93\u2013107."},{"key":"S1471068412000178_ref17","first-page":"157","article-title":"XSB: Extending Prolog with tabled logic programming","volume":"12","author":"Swift","year":"2012","journal-title":"TPLP, Special issue on Prolog systems"},{"key":"S1471068412000178_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/368892.368907"},{"key":"S1471068412000178_ref8","unstructured":"Neumerkel U. 1989. Garbage Collection in Prolog Systems (in German). PhD Thesis, Technical University of Vienna."},{"key":"S1471068412000178_ref11","unstructured":"Raimundo J. and Rocha R. 2011. Global trie for subterms. In CICLOPS."},{"key":"S1471068412000178_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(98)10013-4"},{"key":"S1471068412000178_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/227595.227597"},{"key":"S1471068412000178_ref15","unstructured":"Sato T. , Zhou N.-F. , Kameya Y. and Yizumi Y. 2010. The PRISM user's manual. http:\/\/www.mi.cs.titech.ac.jp\/prism\/."},{"key":"S1471068412000178_ref18","unstructured":"Swift T. and Warren D. S. 2009. The XSB Programmer's Manual: vols. 1 and 2. http:\/\/xsb.sf.net."},{"key":"S1471068412000178_ref19","unstructured":"Warren D. H. D. 1983. An abstract Prolog instruction set. Technical note 309, SRI International."},{"key":"S1471068412000178_ref21","first-page":"81","article-title":"Linear tabling strategies and optimizations","volume":"8","author":"Zhou","year":"2008","journal-title":"TPLP"}],"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\/S1471068412000178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T16:26:28Z","timestamp":1556209588000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068412000178\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":21,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["S1471068412000178"],"URL":"https:\/\/doi.org\/10.1017\/s1471068412000178","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}