УДК 510.66

Об исчислении Ламбека с единицей и одним делением / С. Л. Кузнецов. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2011. № 4. С. 55-57.

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

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

Библиогр. 4.