Часть 3. Математические модели

Задача определения порядка для автоматов, чьи функции переходов и выходов принадлежат замкнутому классу Поста

Н. В. Муравьев

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

Аннотация: Рассматривается задача определения порядка автомата Мили относительно операции суперпозиции. Доказано разбиение решетки Поста замкнутых классов относительно разрешимости задачи вычисления порядка для соответствующих $R$-автоматов.

Ключевые слова: автоматы Мили, классы Поста, алгоритмическая разрешимость