RUS  ENG
Full version
JOURNALS // Proceedings of the Yerevan State University, series Physical and Mathematical Sciences // Archive

Proceedings of the YSU, 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.

MSC: 68N18

Received: 07.11.2018
Revised: 29.01.2019
Accepted: 02.04.2019

Language: English



© Steklov Math. Inst. of RAS, 2024