|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2019, Volume 53, Issue 1, Pages 28–36
(Mi uzeru541)
|
|
|
|
Informatics
A necessary and sufficient condition for the uniqueness of βδ-normal form of typed λ-terms
L. Budaghyana, D. A. Grigoryanb, L. H. Torosyanc a University of Bergen
b Yerevan State University, Faculty of Informatics and Applied Mathematics
c Yerevan State University
Abstract:
In this paper the canonical notion of δ-reduction is considered. Typed λ-terms use variables of any order and constants of order ≤1, where the constants of order 1 are strongly computable, monotonic functions with indeterminate values of arguments. The canonical notion of βδ-reduction is the notion of δ-reduction that is used in the implementation of functional programming languages. It is shown that for canonical notion of δ-reduction SI-property is the necessary and sufficient condition for the uniqueness of βδ-normal form of typed λ-terms.
Keywords:
Canonical notion of δ-reduction, βδ-reduction, βδ-normal form.
Received: 07.11.2018 Revised: 29.01.2019 Accepted: 02.04.2019
Citation:
L. Budaghyan, D. A. Grigoryan, L. H. Torosyan, “A necessary and sufficient condition for the uniqueness of βδ-normal form of typed λ-terms”, Proceedings of the YSU, Physical and Mathematical Sciences, 53:1 (2019), 28–36
Linking options:
https://www.mathnet.ru/eng/uzeru541 https://www.mathnet.ru/eng/uzeru/v53/i1/p28
|
Statistics & downloads: |
Abstract page: | 124 | Full-text PDF : | 38 | References: | 27 |
|