Hostname: page-component-7b7567c8c-8tzhz Total loading time: 0 Render date: 2026-11-19T21:25:28.187Z Has data issue: false hasContentIssue false

Compact serialization of Prolog terms (with catalan skeletons, cantor tupling and Gödel numberings)

Published online by Cambridge University Press:  25 September 2013

PAUL TARAU*
Affiliation:
Department of Computer Science and Engineering (e-mail: tarau@cs.unt.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 ‘no bit lost’ bijection, as it associates to each Prolog term a unique natural number and each natural number corresponds to a unique syntactically well-formed term.

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.

A novel algorithm for the generalized Cantor bijection between ${\mathbb{N}$ and ${\mathbb{N}$k is used in the process of assigning polynomially bounded Gödel numberings to various data objects involved in the translation.

Supplementary material: PDF

Tarau supplementary material

Appendix

Download Tarau supplementary material(PDF)
PDF 128.1 KB