{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T00:07:55Z","timestamp":1715645275974},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T00:00:00Z","timestamp":1380067200000},"content-version":"unspecified","delay-in-days":86,"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,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We describe a compact serialization algorithm mapping Prolog terms to natural numbers of bit-sizes proportional to the memory representation of the terms. The algorithm is a \u2018no bit lost\u2019 bijection, as it associates to each Prolog term a unique natural number and each natural number corresponds to a unique syntactically well-formed term.<\/jats:p><jats:p>To avoid an exponential explosion resulting from bijections mapping term trees to natural numbers, we separate the symbol content and the syntactic skeleton of a term that we serialize compactly using a ranking algorithm for Catalan families.<\/jats:p><jats:p>A novel algorithm for the generalized Cantor bijection between <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1471068413000537_inline1\"\/><jats:tex-math>${\\mathbb{N}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1471068413000537_inline1\"\/><jats:tex-math>${\\mathbb{N}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup> is used in the process of assigning polynomially bounded G\u00f6del numberings to various data objects involved in the translation.<\/jats:p>","DOI":"10.1017\/s1471068413000537","type":"journal-article","created":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T16:24:58Z","timestamp":1380126298000},"page":"847-861","source":"Crossref","is-referenced-by-count":8,"title":["Compact serialization of Prolog terms (with catalan skeletons, cantor tupling and G\u00f6del numberings)"],"prefix":"10.1017","volume":"13","author":[{"given":"PAUL","family":"TARAU","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2013,9,25]]},"reference":[{"key":"S1471068413000537_ref13","first-page":"171","volume-title":"Proceedings of 11th International ACM SIGPLAN Symposium PPDP 2009","author":"Tarau","year":"2009"},{"key":"S1471068413000537_ref11","first-page":"572","volume-title":"MFCS","author":"Martinez","year":"2003"},{"key":"S1471068413000537_ref4","first-page":"301","volume-title":"ICALP","author":"Hartmanis","year":"1974"},{"key":"S1471068413000537_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01700692"},{"key":"S1471068413000537_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00281-8"},{"key":"S1471068413000537_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/355732.355739"},{"key":"S1471068413000537_ref14","volume-title":"CICLOPS'2011","author":"Tarau","year":"2011"},{"key":"S1471068413000537_ref12","volume-title":"Formal Languages","author":"Salomaa","year":"1973"},{"key":"S1471068413000537_ref7","volume-title":"Combinatorial Algorithms: Generation, Enumeration, and Search","author":"Kreher","year":"1999"},{"key":"S1471068413000537_ref10","article-title":"Some remarks on the Cantor pairing function.","volume":"62","author":"Lisi","year":"2007","journal-title":"Le Matematiche"},{"key":"S1471068413000537_ref9","article-title":"Ranking and unranking of a generalized Dyck language and the application to the generation of random trees.","volume":"43","author":"Liebehenschel","year":"2000","journal-title":"S\u00e9minaire Lotharingien de Combinatoire"},{"key":"S1471068413000537_ref5","volume-title":"The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions","author":"Knuth","year":"2005"},{"key":"S1471068413000537_ref8","first-page":"5","volume-title":"Applied Combinatorial Mathematics","author":"Lehmer","year":"1964"},{"key":"S1471068413000537_ref6","volume-title":"The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees\u2013History of Combinatorial Generation (Art of Computer Programming)","author":"Knuth","year":"2006"},{"key":"S1471068413000537_ref15","volume-title":"28th International Conference on Logic Programming - Technical Communications (ICLP'12)","author":"Tarau","year":"2012"}],"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\/S1471068413000537","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T09:29:25Z","timestamp":1715592565000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068413000537\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":15,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["S1471068413000537"],"URL":"https:\/\/doi.org\/10.1017\/s1471068413000537","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7]]}}}