@article{920c2906-6098-4ece-adfe-998aa7dd320b,
author = {Łukasz Lachowski},
title = {On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic},
journal = {Reports on Mathematical Logic},
volume = {2018},
number = {Number 53},
year = {2018},
issn = {0137-2904},
pages = {19-42},keywords = {combinatory logic; lambda calculus; complexity analysis; functional programming},
abstract = {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.},
doi = {10.4467/20842589RM.18.002.8835},
url = {https://ejournals.eu/en/journal/reports-on-mathematical-logic/article/on-the-complexity-of-the-standard-translation-of-lambda-calculus-into-combinatory-logic}
}