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 37–46 (Mi uzeru542)

Informatics

On the uniqueness of $\beta\delta$-normal form of typed $\lambda$-terms for the canonical notion of $\delta$-reduction

D. A. Grigoryan

Yerevan State University, Faculty of Informatics and Applied Mathematics

Abstract: In this paper we consider a substitution and inheritance property, which is the necessary and sufficient condition for the uniqueness of $\beta\delta$-normal form of typed $\lambda$-terms, for canonical notion of $\delta$-reduction. Typed $\lambda$-terms use variables of any order and constants of order $\leq1$, where the constants of order $1$ are strongly computable, monotonic functions with indeterminate values of arguments. The canonical notion of $\delta$-reduction is the notion of $\delta$-reduction that is used in the implementation of functional programming languages.

Keywords: Canonical notion of $\delta$-reduction, SI-property, $\beta\delta$-normal form.

MSC: 68N18

Received: 27.12.2018
Revised: 31.01.2019
Accepted: 02.04.2019

Language: English



© Steklov Math. Inst. of RAS, 2024