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 ORCID

    B-terms are built from the B combinator alone defined by Bλ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

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1896 times.
    This article's PDF has been downloaded 560 times.