Word operation definable in the typed \(\lambda\)-calculus (Q1099156)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Word operation definable in the typed \(\lambda\)-calculus |
scientific article |
Statements
Word operation definable in the typed \(\lambda\)-calculus (English)
0 references
1987
0 references
The problem of representability of word functions over a binary (any finite) alphabet by closed terms of the type \(\underline B^ n\to \underline B\) (where \(\underline B = (0\to 0)\to ((0\to 0)\to (0\to 0)))\) is solved. It is proved that the set FUN Ḇ, i.e. \(\cup^{\infty}_{i=1}Cl(\underline B^ i\to \underline B),\) is finitely generated. This is an extension of Schwichtenberg's and Statman's results.
0 references
typed lambda calculus
0 references
lambda-definability
0 references
representability of word functions
0 references
0 references