scientific article; zbMATH DE number 3557747
[This article was published in the book announced in Zbl 0349.00016.] The aim of this paper is to investigate the termination property, i.e., the property to have normal form, of terms of \(\lambda\)-calculus of the shape \(NX_1\dots X_r\) where \(N,X_1,\dots, X_r\) are terms in normal form. This is done by characterizing (constructively) a domain \(C(N,r) \in {\mathcal N}^r\) (where \(r\) is a positive integer and \({\mathcal N}\) is the set of terms in normal form) such that for all \(X_1,\dots ,X_r \in C(N,r)\) the term \(NX_1\dots X_r\) reduces to a normal form. If we interpret \(N\) as a function, \(C(N,r)\) represents a domain onto which \(N\) is total and, therefore, it is contained in the (semidecidable) domain of total convergence of \(N\). These two domains coincide if and only if \(C(N,r)={\mathcal N}^r\). The decidability of this relation has been shown (also constructively) in a previous work by \textit{C. Böhm} and \textit{M. Dezani-Ciancaglini} [Lect. Notes Comput. Sci. 37, 96--121 (1975; Zbl 0342.02017)]. The characterization of \(C(N,r)\) is done by coding some features of \(N\) and \(X_1,\dots ,X_r\) by means of lists of integers and comparing them. Further investigations of termination properties of terms have been done (by M. Coppo and M. Dezani-Ciancaglini) by introducing a new functionality theory in which types represent termination properties of terms.
- Proving termination of normalization functions for conditional expressions
- Perpetual reductions in -calculus
- Distributional Learning and Context/Substructure Enumerability in Nonlinear Tree Grammars
- A new type assignment for λ-terms
- scientific article; zbMATH DE number 3672268 (Why is no real title available?)
- scientific article; zbMATH DE number 3697079 (Why is no real title available?)
- scientific article; zbMATH DE number 3720894 (Why is no real title available?)
- scientific article; zbMATH DE number 218500 (Why is no real title available?)
- Calculi, types and applications: essays in honour of M. Coppo, M. Dezani-Ciancaglini and S. Ronchi della Rocca
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4133598)