Д. Н. Бабин, А. А. Летуновский, “О выразимости автоматов с операцией суперпозиции”, Интеллектуальные системы. Теория и приложения, 2023, том 27, выпуск 4,страницы 76

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

О выразимости автоматов с операцией суперпозиции

Д. Н. Бабин, А. А. Летуновский

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

Аннотация: Задача выразимости для константных автоматов и линейных автоматов для расширенной суперпозиции алгоритмически разрешима. Имеет место теорема об алгоритмической разрешимости задачи выразимости автоматов с линейными переходами над полем конечной характеристики.

Ключевые слова: расширенная суперпозиция, выразимость, линейные автоматы, алгоритмическая разрешимость