О некоторых перечислительных задачах лямбда-исчисления

И. Н. Лабутин; Д. Н. Москвин; А. В. Омельченко; А. И. Храбров; Е. С. Краско

?

О некоторых перечислительных задачах лямбда-исчисления

Записки научных семинаров ПОМИ РАН. 2018. Т. 475. С. 99–121.

Лабутин И. Н., Москвин Д. Н., Омельченко А. В., Храбров А. И., Краско Е. С.

В статье рассматриваются комбинаторные задачи, связанные с перечислением лямбда-термов в бестиповом лямбда-исчислении, а также в просто типизированных системах с одним атомом в стиле Черча. Для случая бестипового лямбда-исчисления строится система уравнений на производящие функции, описывающие количество лямбда-термов. В случае типизированного лямбда-исчисления перечисляются как населенные типы, так и простейшие обитатели в них.

Приоритетные направления: компьютерно-математическое математика

Язык: русский

Полный текст

Текст на другом сайте

Ключевые слова: теория типов перечислительная комбинаторика generating functions лямбда-исчисление lambda-terms lambda calculus

A Three-Party W-State Quantum Secret Sharing Protocol with X-Gate Encoding and Forbidden-Outcome Detection

Терегулов Т. Р., Лубенец Е. Р., / Series Quantum Physics "arXiv". 2026. No. 2609.31472.

Добавлено: 28 сентября 2026 г.

Pairings on the algebra of Laurent series over a ring

Левашев В. А., / Series arXiv "math". 2026. No. 2609.06010.

Добавлено: 24 сентября 2026 г.

Iterative construction of the R-matrices in arbitrary dimensions

Пятов П. Н., Пивоваров П. А., / Series math "arxiv.org". 2026. No. 2609.06274.

Добавлено: 24 сентября 2026 г.

On static manifolds with boundary admitting a nowhere-vanishing static potential

Медведев В. О., / Series arXiv "math". 2026.

We study complete static manifolds with boundary admitting a nowhere-vanishing static potential. Our main result shows that, under a natural lower bound relating the scalar curvature and the boundary mean curvature, a simple static manifold with boundary must in fact have positive scalar curvature, negative boundary mean curvature, and be compact; we also obtain explicit ...

Добавлено: 19 сентября 2026 г.

Vague stimulating ideas, images and metaphors in scientific thinking: researchers' work with horizons of unclear knowledge

Поддьяков А. Н., / Series Social Science Research Network "Social Science Research Network". 2026. No. 7437658.

Добавлено: 15 сентября 2026 г.

On phase-lock area parquet in a special slow-fast limit of model of Josephson junction.

Глуцюк А. А., / Series arXiv "math". 2026.

Добавлено: 8 сентября 2026 г.

Infinitely many graph manifolds with unique geometrical piece that admit arbitrarily many Anosov flows

Починка О. В., Шмуклер В. И., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.

Добавлено: 31 августа 2026 г.

On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands

Shabanov N., Kuricheva O., Kurbatova J. и др., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.

Добавлено: 21 августа 2026 г.

Three Algorithms for Merging Hierarchical Navigable Small World Graphs

Пономаренко А. А., / Series Computer Science "arxiv.org". 2025.

Добавлено: 30 июля 2026 г.

New bound on S1× S2-setting Bell locality of a nonseparable Werner state

Лубенец Е. Р., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.

Добавлено: 21 июля 2026 г.

On functional equations for Chow polylogarithms

Болбачан В. С., / Series math "arxiv.org". 2024.

Полилогарифмы Чжоу — это специальные функции, возникающие при явном описании отображения регулятора Бейлинсона. Наиболее интересное функциональное уравнение для этой функции отражает тот факт, что она обращается в нуль на границе в комплексе циклов Блоха. Мы показываем, что это функциональное уравнение формально вытекает из более простых свойств: кососимметричности, функториальности и мультипликативности. Для доказательства этого мы рассматриваем ...

Добавлено: 16 июля 2026 г.

On Goncharov’s conjecture in next to Milnor degree

Болбачан В. С., / Series math "arxiv.org". 2024.

Пусть K поле характеристики ноль. Мы доказываем что его когомологии в степени m-1 и весе m рационально изоморфны когомологиям полилогарифмического комплекса в соответствующей степени. Это дает частичное расширение теоремы Суслина, описывающую неразложимую K теорию K_3 для поля. ...

Добавлено: 16 июля 2026 г.

Statistical inference based on band-limited kernels: Rational-infinitely divisible distributions and beyond

Панов В. А., Рябченко А. П., / Series arXiv "stat.ME". 2026. No. 2607.05048.

Добавлено: 9 июля 2026 г.

Growth in noncommutative algebras and entropy in derived categories

Пионтковский Д. И., / Series arXiv "math". 2026.

Добавлено: 23 июня 2026 г.

Multilinear nilalgebras and the Jacobian theorem

Пионтковский Д. И., / Series arXiv "math". 2025.

Добавлено: 23 июня 2026 г.

О количестве независимых и k-доминирующих множеств в графах со средней степенью вершин не более k

Талецкий Д. С., Математический сборник 2023 Т. 214 № 11 С. 133–156

Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа k ⩾ 1, то количество его k-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является k-регулярным. Эта гипотеза доказана для случая k ∈ {1,2}. ...

Добавлено: 2 ноября 2023 г.

Функциональное программирование

Петренко А. А., Суворов А. О., Шаякбаров Н. Ф., Пермь: Издательство Пермского национального исследовательского политехнического университета, 2022.

Рассмотрены вопросы, касающиеся языков функционального программирования: особенности применения, синтаксис, функции. Приведено большое количество содержательных примеров решения задач, демонстрирующих возможности языков функционального программирования. Предназначено студентам образовательных учреждений высшего образования, обучающимся по специальностям направлений «Информатика и вычислительная техника», «Программная инженерия», а также лицам, самостоятельно изучающим функциональное программирование. ...

Добавлено: 25 октября 2022 г.

On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales

Игнатов Д. И., Яковлева А. С., , in: Proceedings of the 9th International Workshop "What can FCA do for Artificial Intelligence?" (FCA4AI 2021)Vol. 2972.: CEUR-WS, 2021. P. 87–98.

Добавлено: 1 ноября 2021 г.

On lattice point counting in Δ-modular polyhedra

Грибанов Д. В., Золотых Н. Ю., Optimization Letters 2022 Vol. 16 No. 7 P. 1991–2018

Добавлено: 29 октября 2021 г.

On Some Enumerative Problems in Lambda Calculus

Краско Е. С., Лабутин И. Н., Москвин Д. Н. и др., Journal of Mathematical Sciences 2020 Vol. 247 P. 442–456

Добавлено: 26 октября 2021 г.

Constellations and τ-functions for rationally weighted hurwitz numbers

Harnad J., Рунов Б. А., Annales de l'Institut Henri Poincare (D) Combinatorics, Physics and their Interactions 2021 Vol. 8 No. 1 P. 119–158

Добавлено: 21 октября 2021 г.

On moments of a polytope

Gravin N., Пасечник Д., Shapiro B. и др., Analysis and Mathematical Physics 2018 Vol. 8 No. 2 P. 255–287

Добавлено: 25 февраля 2021 г.

Generating functions and Owen value in cooperative network cover game

Mazalov V. V., V. V. Gusev, Performance Evaluation 2020 Vol. 144 P. 102135

Добавлено: 29 сентября 2020 г.

Разработка схемы адаптивного конфигурирования загрузки виртуальных машин на основе аппликативного исчисления информационных процессов

Зыков С. В., Шумский Л. Д., Тарасов И. Е., Cloud of Science 2018 Т. 5 С. 704–712

В работе исследуются типичные сценарии, при которых возникает потребность совместного использования ограниченных общесистемных ресурсов несколькими виртуальными машинами. Разработаны правила балансировки нагрузки в зависимости от информационных процессов, выполняемых виртуальными машинами. Вычисление производительности рассмотренных операций основано на типизированной модели, что дает возможность оценки общей производительности. ...

Добавлено: 3 ноября 2019 г.