Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Sixth Annual IEEE Symposium on

Logic in Computer Science (LICS 1991)

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}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski