|
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 $\beta\delta$-normal form of typed $\lambda$-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 $\delta$-reduction is considered. Typed $\lambda$-terms use variables of any order and constants of order $\leq 1$, where the constants of order $1$ are strongly computable, monotonic functions with indeterminate values of arguments. The canonical notion of $\beta\delta$-reduction is the notion of $\delta$-reduction that is used in the implementation of functional programming languages. It is shown that for canonical notion of $\delta$-reduction SI-property is the necessary and sufficient condition for the uniqueness of $\beta\delta$-normal form of typed $\lambda$-terms.
Keywords:
Canonical notion of $\delta$-reduction, $\beta\delta$-reduction, $\beta\delta$-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 $\beta\delta$-normal form of typed $\lambda$-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: | 94 | Full-text PDF : | 21 | References: | 17 |
|