Paper: Freyd's hierarchy of combinator monoids (at LICS 1991)

Authors: Richard Statman

Abstract

The Freyd hierarchy of monoids is introduced. The Freyd hierarchy is a fragment of type-free combinatory algebra λ-calculus that has some remarkable properties, some of which are presented. One result characterizes the combinators in the hierarchy in terms of some simple ideas from the theory of rewrite rules. The computational/expressive power of the fragment is studied. This includes not only the functions computable by the combinators but also the varieties definable by combinator equations. Certain extraordinary connections between the lowest level of the hierarchy, combinatorics, and topology are also included

BibTeX

  @InProceedings{Statman-Freydshierarchyofco,
    author = 	 {Richard Statman},
    title = 	 {Freyd's hierarchy of combinator monoids},
    booktitle =  {Proceedings of the Sixth Annual IEEE Symposium on Logic in Computer Science (LICS 1991)},
    year =	 {1991},
    month =	 {July}, 
    pages =      {186--190},
    location =   {Amsterdam, The Netherlands}, 
    publisher =	 {IEEE Computer Society Press}
  }