Complexity of the combinator reduction machine

DOI10.1016/0304-3975(85)90076-3MaRDI QIDQ1075052zbMATH OpenOpenAlexFDO

Authors Sachio Hirokawa

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90076-3

zbMATH Keywords

recursive programsprogram schemecombinator codenumber of the reduction steps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• scientific article; zbMATH DE number 4039260
• scientific article; zbMATH DE number 3909737
• scientific article; zbMATH DE number 4045104
• \(c\beta\)-Machine with \(\lambda \beta\)-reduction
• (Leftmost-outermost) beta reduction is invariant, indeed

Cites work

• scientific article; zbMATH DE number 3905831 (Why is no real title available?)
• scientific article; zbMATH DE number 3735770 (Why is no real title available?)
• A linear space translation of functional programs to Turner combinators
• A new implementation technique for applicative languages
• An efficient interpreter for the lambda-calculus
• Another algorithm for bracket abstraction
• Minimal and Optimal Computations of Recursive Programs
• The BC-chain method for representing combinators in linear space
• The lambda calculus, its syntax and semantics

Cited in

(3)

• scientific article; zbMATH DE number 4039260 (Why is no real title available?)
• scientific article; zbMATH DE number 4045104 (Why is no real title available?)
• scientific article; zbMATH DE number 3909737 (Why is no real title available?)

This page was built for publication: Complexity of the combinator reduction machine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1075052)