article Open access

On properties of $B$-terms

  • Logical Methods in Computer Science
  • Logical Methods in Computer Science e.V.
Research footprint

At a glance

Citations
0
References
5
Comments
0
Paper overview

Abstract

$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. Comment: Journal version in Logical Methods in Computer Science. arXiv admin note: substantial text overlap with arXiv:1703.10938

Record transparency

Publication details

DOI
10.23638/lmcs-16(2:8)2020
OpenAlex
W2912412101
Document type
article
Language
EN
Source
Logical Methods in Computer Science
Last metadata update
Community

Comments

Log in to join the discussion.

  1. No comments yet. Start the discussion.