Abstract | ||
---|---|---|
B-terms are built from the B combinator alone defined by B (math) lambda fgx.f(g x), which is well known as a function composition operator. This paper investigates an interesting property of B-terms, that is, whether repetitive right applications of a B-term cycles or not. We discuss conditions for B-terms to have and not to have the property through a sound and complete equational axiomatization. Specifically, we give examples of B-terms which have the cyclic property and show that there are infinitely many B-terms which do not have the property. Also, we introduce another interesting property about a canonical representation of B-terms that is useful to detect cycles, or equivalently, to prove the cyclic property, with an efficient algorithm. |
Year | DOI | Venue |
---|---|---|
2019 | 10.23638/LMCS-16(2:8)2020 | LOGICAL METHODS IN COMPUTER SCIENCE |
Keywords | DocType | Volume |
Combinatory logic,B combinator,Lambda calculus | Journal | 16 |
Issue | ISSN | Citations |
2 | 1860-5974 | 0 |
PageRank | References | Authors |
0.34 | 1 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mirai Ikebuchi | 1 | 0 | 0.34 |
Keisuke Nakano | 2 | 212 | 24.62 |