{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:43:14Z","timestamp":1760240594679,"version":"build-2065373602"},"reference-count":17,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T00:00:00Z","timestamp":1565222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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     O (   (  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.<\/jats:p>","DOI":"10.3390\/a12080159","type":"journal-article","created":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T11:05:32Z","timestamp":1565262332000},"page":"159","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Compaction of Church Numerals"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1918-5802","authenticated-orcid":false,"given":"Isamu","family":"Furuya","sequence":"first","affiliation":[{"name":"Graduate School\/Faculty of Information Science and Technology, Hokkaido University, Kita 14 Nishi 9, Sapporo 060-0814, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1666-3303","authenticated-orcid":false,"given":"Takuya","family":"Kida","sequence":"additional","affiliation":[{"name":"Graduate School\/Faculty of Information Science and Technology, Hokkaido University, Kita 14 Nishi 9, Sapporo 060-0814, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s10990-013-9093-z","article-title":"Functional programs as compressed data","volume":"25","author":"Kobayashi","year":"2012","journal-title":"High. Order Symb. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Yaguchi, K., Kobayashi, N., and Shinohara, A. (2014, January 26\u201328). Efficient algorithm and coding for higher-rder compression. Proceedings of the 2014 Data Compression Conference (DCC2014), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2014.63"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","article-title":"Grammar-based codes: A new class of universal lossless source codes","volume":"46","author":"Kieffer","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","article-title":"The smallest grammar problem","volume":"51","author":"Charikar","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1109\/5.892708","article-title":"Off-line dictionary-based compression","volume":"88","author":"Larsson","year":"2000","journal-title":"Proc. IEEE"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Maruyama, S., Tanaka, Y., Sakamoto, H., and Takeda, M. (2008, January 10\u201312). Context-sensitive grammar transform: Compression and pattern matching. Proceedings of the String Processing and Information Retrieval (SPIRE2008), Melbourne, Australia.","DOI":"10.1007\/978-3-540-89097-3_5"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Masaki, T., and Kida, T. (April, January 30). Online grammar transformation based on re-pair algorithm. Proceedings of the Data Compression Conference (DCC2016), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2016.69"},{"key":"ref_9","unstructured":"Nevill-Manning, C.G., Witten, I.H., and Maulsby, D.L. (1994, January 29\u201331). Compression by induction of hierarchical grammars. Proceedings of the Data Compression Conference (DCC\u201994), Snowbird, UT, USA."},{"key":"ref_10","unstructured":"Takabatake, Y., and Sakamoto, H. (2017, January 4\u20136). A space-optimal grammar compression. Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017), Vienna, Austria. Leibniz International Proceedings in Informatics (LIPIcs)."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ohno, T., Goto, K., Takabatake, Y., I, T., and Sakamoto, H. (2018, January 16\u201319). LZ-ABT: A practical algorithm for \u03b1-balanced grammar compressio. Proceedings of the 29th International Workshop on Combinatorial Algorithms (IWOCA 2018), Singapore.","DOI":"10.1007\/978-3-319-94667-2_27"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., and Sannella, D. (2004). Grammar compression, LZ-encodings, and string algorithms with implicit input. Automata, Languages, and Programming (ICALP2004), Springer.","DOI":"10.1007\/b99859"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1515\/gcc-2012-0016","article-title":"Algorithmics on SLP-compressed strings: A survey","volume":"4","author":"Lohrey","year":"2012","journal-title":"Groups Complex. Cryptol."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Furuya, I., and Kida, T. (2018, January 27\u201330). Compaction of church numerals for higher-order compression. Proceedings of the Data Compression Conference (DCC2018), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2018.00061"},{"key":"ref_15","unstructured":"Mogensen, T.A. (2001). An investigation of compact and efficient number representations in the pure lambda calculus. Revised Papers from the 4th International Andrei Ershov Memorial Conference on Perspectives of System Informatics (PSI \u201902): Akademgorodok, Novosibirsk, Russia, Springer-Verlag."},{"key":"ref_16","unstructured":"Hutter, M., Merkle, W., and Vitanyi, P.M. (2006). Binary lambda calculus and combinatory logic. Kolmogorov Complexity and Applications, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI). Number 06051 in Dagstuhl Seminar Proceedings."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Takeda, K., Kobayashi, N., Yaguchi, K., and Shinohara, A. (2016, January 18\u201324). Compact bit encoding schemes for simply-typed lambda-terms. Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, Nara, Japan.","DOI":"10.1145\/2951913.2951918"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/159\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:09:40Z","timestamp":1760188180000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,8]]},"references-count":17,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8]]}},"alternative-id":["a12080159"],"URL":"https:\/\/doi.org\/10.3390\/a12080159","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,8,8]]}}}