TY - JOUR
TI - On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic
AU - Lachowski, Łukasz
TI - On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic
AB - 
	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.
VL - 2018
IS - Number 53
PY - 2018
SN - 0137-2904
C1 - 2084-2589
SP - 19
EP - 42
DO - 10.4467/20842589RM.18.002.8835
UR - https://ejournals.eu/en/journal/reports-on-mathematical-logic/article/on-the-complexity-of-the-standard-translation-of-lambda-calculus-into-combinatory-logic
KW - combinatory logic
KW - lambda calculus
KW - complexity analysis
KW - functional programming