On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic

2018/01/01 by Łukasz Lachowski · 1 citation
Computer Science · Mathematics · #Logic, programming, and type systems #Logic, Reasoning, and Knowledge #Advanced Algebra and Logic #Mathematics #Calculus (dental) #Lambda #Translation (biology) #Curry–Howard correspondence #Church encoding #Combinatory logic #Typed lambda calculus #Algebra over a field #Lambda calculus #Discrete mathematics #Simply typed lambda calculus #Computer science #Pure mathematics #Programming language

paper · pdf · doi:10.4467/20842589rm.18.002.8835

openalex publication_date 2018/01/01 · openalex created_date 2018/11/09 · openalex updated_date 2026/08/01

Abstract

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.

Citations

• Über die Bausteine der mathematischen Logik
• Grundlagen der Kombinatorischen Logik
• Another algorithm for bracket abstraction
• An Unsolvable Problem of Elementary Number Theory

Cited by

• Combinatory logic [wikipedia]

Related

• Binary Lambda Calculus and Combinatory Logic
• Counting Terms in the Binary Lambda Calculus
• A direct proof of the confluence of combinatory strong reduction
• A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms
• Counting and generating lambda terms