A NECESSARY AND SUFFICIENT CONDITION FOR THE UNIQUENESS OF $ \beta\delta $-NORMAL FORM OF TYPED $ \lambda $-TERMS FOR THE CANONICAL NOTION OF $ \delta $-REDUCTION

Authors

  • L.E. Budaghyan Chair of Programming and Information Technologies, YSU, Armenia
  • D.A. Grigoryan Chair of Programming and Information Technologies, YSU, Armenia
  • L.H. Torosyan HS International LLC, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2019.53.1.028

Keywords:

canonical notion of $ \delta $-reduction, $ \beta\delta $-reduction, $ \beta\delta $-normal form

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 $ \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.

Downloads

Published

2019-04-15

How to Cite

Budaghyan, L., Grigoryan, D., & Torosyan, L. (2019). A NECESSARY AND SUFFICIENT CONDITION FOR THE UNIQUENESS OF $ \beta\delta $-NORMAL FORM OF TYPED $ \lambda $-TERMS FOR THE CANONICAL NOTION OF $ \delta $-REDUCTION. Proceedings of the YSU A: Physical and Mathematical Sciences, 53(1 (248), 28–36. https://doi.org/10.46991/PYSU:A/2019.53.1.028

Issue

Section

Informatics