Compaction of Church numerals
Summary: In this study, we address the problem of compaction of Church numerals. Church numerals are unary representations of natural numbers on the scheme of lambda terms. We propose a novel decomposition scheme from a given natural number into an arithmetic expression using tetration, which enables us to obtain a compact representation of lambda terms that leads to the Church numeral of the natural number. For natural number \(n\), we prove that the size of the lambda term obtained by the proposed method is \(\mathcal{O}((\operatorname{slog}_2 n)^{(\log n / \log \log n)})\). Moreover, we experimentally confirmed that the proposed method outperforms binary representation of Church numerals on average, when \(n\) is less than approximately \(10,000\).
- A space-optimal grammar compression
- Algorithmics on SLP-compressed strings: a survey
- Automata, Languages and Programming
- Compact bit encoding schemes for simply-typed lambda-terms
- Functional programs as compressed data
- Grammar-based codes: a new class of universal lossless source codes
- scientific article; zbMATH DE number 2084341 (Why is no real title available?)
- LZ-ABT: a practical algorithm for \(\alpha \)-balanced grammar compression
- The Smallest Grammar Problem
This page was built for publication: Compaction of Church numerals
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2005559)
