ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2009, ТОМ 15, ВЫПУСК 3, СТР. 33-47

О классификации базисов в Pk по разрешимости проблемы полноты для автоматов

Д. Н. Бабин

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

Рассматривается проблема полноты систем автоматных функций вида F È n, где F Í Pk, n конечно. Ранее автор решил эту задачу в случае k = 2, а также показал, что для [F] = Pk существует алгоритм распознавания полноты систем F È n. В статье рассматривается случай, когда [F] является максимальным (предполным) классом в Pk. Показано, что если класс F вложим в класс Слупецкого, то проблема полноты систем F È n неразрешима, а если F содержит класс сохранения всех констант, то имеет место алгоритмическая разрешимость указанной задачи. Тем самым возникает возможность классификации базисов в Pk, k ³ 3, по их способности в качестве добавки в автоматный базис обеспечивать алгоритмическую разрешимость проблемы полноты.

Полнотекстовая версия статьи в формате PDF (177 Kb)

Главная страница Содержание журнала Новости Поиск

URL страницы: http://mech.math.msu.su/~fpm/rus/k09/k093/k09305h.htm
Изменения вносились 13 января 2010 г.