RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2011, номер 4, страницы 55–57 (Mi vmumm705)

Краткие сообщения

Об исчислении Ламбека с единицей и одним делением

С. Л. Кузнецов

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: В статье предъявляется подстановка, сводящая выводимость в исчислении Ламбека с единицей и одним делением к выводимости в исчислении Ламбека с одним делением, допускающем пустые антецеденты. При помощи этой подстановки устанавливается существование алгоритма, за полиномиальное время проверяющего выводимость в исчислении Ламбека с единицей и одним делением.

Ключевые слова: исчисление Ламбека, алгоритмическая сложность.

УДК: 510.66

Поступила в редакцию: 01.12.2010



Реферативные базы данных:


© МИАН, 2025