Complexity of the combinator reduction machine

Sachio Hirokawa

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


The complexity of the computation of recursive programs by the combinator reduction machine is studied. The number of the reduction steps in compared between the two models of computation. The main theorem states that the time required by the reduction machine is linear in that of the program scheme. The coefficient of the linearity was shown to be O(n2), where n is the maximal number of variables of the functions being used. For the analysis of the combinator codes, the notion of extended combinator code is introduced.

Original languageEnglish
Pages (from-to)289-303
Number of pages15
JournalTheoretical Computer Science
Issue numberC
Publication statusPublished - 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Complexity of the combinator reduction machine'. Together they form a unique fingerprint.

Cite this