Алгоритмические проблемы конечных автоматов

Abstract

Строится базис конечных автоматов, связанный выводимостью слов в нормальном исчислении Поста. Определяются операторы, реализуемые логическими сетями над этим базисом. Они являются вычислимыми на автоматах Мура, но их класс не является алгоритмически разрешимым. Рассматриваются различные способы обобщения этих конструкций. Формулируются задачи для продолжения этих исследований. Книга предназначена для студентов математических и прикладных специальностей университетов.