ИСТИНА

В классе конечных автоматов с операциями композиции (суперпозиции и обратной связи) число предполных классов континуально [В.Б. Кудрявцев], а массовая задача проверки полноты конечных подмножеств алгоритмически неразрешима [М.И. Кратко]. Доклад посвящен классам линейных автоматов над конечными полями с операциями композиции. Для этих классов автором решена проблема полноты: найдены все предполные классы, что позволило получить алгоритм проверки полноты конечных подмножеств. В случае линейных автоматов над полем из двух элементов найдены замкнутые подклассы, содержащие сумматор. При естественных ограничениях решена задача аппроксимационной выразимости. Исследована структура предполных классов для линейных 2-адических автоматов с операциями композиции. Помимо методов дискретной математики использован аппарат высшей алгебры: для полей Галуа и их трансцендентных расширений, колец, модулей над кольцами, линейных пространств.