О структуре изоморфизмов универсальных графовых автоматов

Теория автоматов — один из разделов математической кибернетики, изучающий преобразователи информации, возникающие во многих прикладных задачах. Основная цель теории автоматов — разработка методов, с помощью которых можно описывать и анализировать динамическое поведение дискретных систем. В зависимости от исследуемых задач рассматриваются автоматы, у которых множество состояний и множество выходных сигналов наделены дополнительной математической структурой, согласованной с функциями переходов и выходов автомата. Мы исследуем автоматы над графами и называем их графовыми автоматами. Универсальный графовый автомат $\mathrm{Atm}(G,H)$ является универсально притягивающим объектом в категории таких автоматов. Полугруппа входных сигналов такого автомата имеет вид $S(G,H) = \mathrm{End}\ G \times \mathrm{Hom}(G,H)$. Её можно рассматривать как производную алгебраическую систему математического объекта $\mathrm{Atm}(G,H)$, содержащую полезную информацию об исходном автомате. Известно, что свойства полугруппы взаимосвязаны со свойствами алгебраической структуры автомата. Следовательно, можно изучать универсальные графовые автоматы, исследуя их полугруппы входных сигналов. Ранее авторы доказали, что широкий класс таких автоматов определяется (с точностью до изоморфизма) своими полугруппами входных сигналов. В данной работе исследуется связь изоморфизмов универсальных графовых автоматов с изоморфизмами их компонент — полугрупп входных сигналов и графов состояний и выходных сигналов.

автомат, граф, полугруппа, изоморфизм, автоморфизм