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\).
- An investigation of compact and efficient number representations in the pure lambda calculus
- An adequate and efficient left-associated binary numeral system in the -calculus
- THEORETICAL PEARL Church numerals, twice!
- Compact numeral representation with combinators
- Some results on numerical systems in -calculus
- A space-optimal grammar compression
- Algorithmics on SLP-compressed strings: a survey
- An investigation of compact and efficient number representations in the pure lambda calculus
- Compact bit encoding schemes for simply-typed lambda-terms
- Functional programs as compressed data
- Grammar compression, LZ-encodings, and string algorithms with implicit input
- Grammar-based codes: a new class of universal lossless source codes
- 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)
