<![CDATA[WUJ]]><![CDATA[info@ejournals.eu]]>http://www.ejournals.eu/20200401ejournals.eu.article.1228503010610.4467/20842589RM.18.002.883520<![CDATA[combinatory logic, lambda calculus, complexity analysis, functional programming]]>00ED031001Number10102<![CDATA[Reports on Mathematical Logic]]>03<![CDATA[2018]]>01<![CDATA[Number 53]]>1A01<![CDATA[Ćukasz Lachowski]]>0101<![CDATA[On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic]]>01en002303020PLN03<![CDATA[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.]]>012018090615000401http://dx.doi.org/10.4467/20842589RM.18.002.8835