We investigate the complexity of the standard translation of lambda calculus into combinatory logic. The main result shows that the asymptotic growth rate of the size of a translated term is Ø(n3) in worst-case, where n denotes the size of the lambda term.
Received 8 June 2017
This work was partially supported by the grant 2013/11/B/ST6/00975 funded by the Polish National Science Center.
AMS subject classification: 03B40, 68Q25, 68N18.
