"Записки научных семинаров ПОМИ"
Том 475, стр. 99-121
О некоторых перечислительных задачах лямбда-исчисления
Е. С. Краско, И. Н. Лабутин, Д. Н. Москвин,
А. В. Омельченко, А. И. Храбров
Национальный
исследовательский университет
``Высшая школа экономики''
ул. Союза Печатников, д. 16,
С.-Петербург 190008, Россия
krasko.evgeniy@gmail.com
labutin.igorl@gmail.com
dmoskvin@gmail.com
avo.travel@gmail.com
aikhrabrov@mail.ru
- Аннотация:
В статье рассматриваются комбинаторные задачи, связанные с перечислением лямбда-термов в бестиповом
лямбда-исчислении, а также в просто типизированных системах с одним атомом в стиле Черча. Для случая
бестипового лямбда-исчисления строится система уравнений на производящие функции, описывающие количество
лямбда-термов. В случае типизированного лямбда-исчисления перечисляются как населенные типы, так и
простейшие обитатели в них.
Библ. -- 11 назв.
- Ключевые слова: лямбда-термы, перечисление, бестиповое и типизированное лямбда-исчисление
[lambda-terms, enumeration, untyped and typed lambda calculus]
Полный текст(.pdf)