Minimal Forms in $\lambda$-Calculus Computations

Bohm, Corrado; Micali, Silvio

J. Symbolic Logic, Tome 45 (1980) no. 1, p. 165-171 / Harvested from Project Euclid

Résumé

The notion of a minimal form is defined as an extension of the notion of a normal form in $\lambda-\beta$-calculus and its meaning is discussed in a computational environment. The features of the Knuth-Gross reduction strategy are used to prove that to possess a minimal form, for a generic term, is a semidecidable predicate.

Publié le : 1980-03-14
Classification:

@article{1183740519,
     author = {Bohm, Corrado and Micali, Silvio},
     title = {Minimal Forms in $\lambda$-Calculus Computations},
     journal = {J. Symbolic Logic},
     volume = {45},
     number = {1},
     year = {1980},
     pages = { 165-171},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183740519}
}

Bohm, Corrado; Micali, Silvio. Minimal Forms in $\lambda$-Calculus Computations. J. Symbolic Logic, Tome 45 (1980) no. 1, pp.  165-171. http://gdmltest.u-ga.fr/item/1183740519/