Ikebuchi, Mirai and Nakano, Keisuke - On properties of $B$-terms

lmcs:5156 - Logical Methods in Computer Science, June 2, 2020, Volume 16, Issue 2 - https://doi.org/10.23638/LMCS-16(2:8)2020
On properties of $B$-terms

Authors: Ikebuchi, Mirai and Nakano, Keisuke

$B$-terms are built from the $B$ combinator alone defined by $B\equiv\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.

Volume: Volume 16, Issue 2
Published on: June 2, 2020
Submitted on: February 1, 2019
Keywords: Computer Science - Logic in Computer Science,03B40 (Primary) 68Q42 (Secondary),F.4.1,F.4.2


Consultation statistics

This page has been seen 139 times.
This article's PDF has been downloaded 71 times.