RUS  ENG
Полная версия
ЖУРНАЛЫ // Ученые записки Ереванского государственного университета, серия Физические и Математические науки // Архив

Уч. записки ЕГУ, сер. Физика и Математика, 2019, том 53, выпуск 1, страницы 37–46 (Mi uzeru542)

Informatics

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

[О единственности $\beta\delta$-нормальной формы типизированных $\lambda$-термов в случае канонического понятия $\delta$-редукции]

D. A. Grigoryan

Yerevan State University, Faculty of Informatics and Applied Mathematics

Аннотация: В данной работе обсуждается ПН-свойство, которое является необходимым и достаточным условием для единственности $\beta\delta$-нормальной формы типизированных $\lambda$-термов в случае канонического понятия $\delta$-редукции. Типизированные $\lambda$-термы используют переменные любых порядков и константы, порядок которых $\leq1$, причем константы порядка $1$ являются сильно вычислимыми, монотонными функциями с неопределенными значениями аргументов. Каноническое понятие $\delta$-редукции используется при реализации функциональных языков программирования.

Ключевые слова: Kаноническоe понятиe $\delta$-редукции, ПН-свойство, $\beta\delta$-нормальная форма.

MSC: 68N18

Поступила в редакцию: 27.12.2018
Исправленный вариант: 31.01.2019
Принята в печать: 02.04.2019

Язык публикации: английский



© МИАН, 2024