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

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

Д. Н. Бабин

Аннотация

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

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

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

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