On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic
Åukasz Lachowski · Reports on Mathematical Logic · 2018
A b s t r a c t.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 Θ(n 3 ) in worst-case, where n denotes the size of the lambda term.