Mirai Ikebuchi ; Keisuke Nakano - 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$-termsArticle

Authors: Mirai Ikebuchi ; Keisuke Nakano

    $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
    Accepted on: May 14, 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 1200 times.
    This article's PDF has been downloaded 365 times.