On Definability of Universal Graphic Automata by Their Input Symbol Semigroups
[Об определяемости универсальных графических автоматов своими полугруппами входных сигналов]

Универсальный графический автомат Atm(G, G′ ) — это универсально притягивающий объект в категории автоматов, у которых множество состояний наделено структурой графа G и множество выходных сигналов — структурой графа G′ , сохраняющимися функциями переходов и выходов автоматов. Полугруппа входных сигналов такого автомата имеет вид S(G, G′ ) = End G × Hom(G, G′ ). Она может рассматриваться как производная алгебраическая система математического объекта Atm(G, G′ ), которая содержит полезную информацию об исходном объекте. Хорошо известно, что свойства такой полугруппы взаимосвязаны со свойствами алгебраической структуры автомата. Следовательно, универсальные графические автоматы можно изучать путем исследования их полугрупп входных сигналов. Для таких полугрупп представляет интерес проблема определяемости универсальных графических автоматов своими полугруппами входных сигналов: при каких условиях полугруппы входных сигналов универсальных графических автоматов будут изоморфны. В данной работе мы исследовали эту проблему. Основной результат нашей работы состоит в том, что универсальные графические автоматы над рефлексивными графами определяются полугруппами своих входных сигналов с точностью до изоморфизма и двойственности графов, если в графе состояний автомата найдется дуга, не входящая ни в один орцикл.