| Autor: |
Isamu Furuya, Takuya Kida |
| Jazyk: |
angličtina |
| Rok vydání: |
2019 |
| Předmět: |
|
| Zdroj: |
Algorithms, Vol 12, Iss 8, p 159 (2019) |
| Druh dokumentu: |
article |
| ISSN: |
1999-4893 |
| DOI: |
10.3390/a12080159 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
|
Nepřihlášeným uživatelům se plný text nezobrazuje |
K zobrazení výsledku je třeba se přihlásit.
|
