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

Теория автоматов является одним из разделов математической кибернетики, в котором изучаются устройства преобразования информации, используемые во многих прикладных задачах. В данной работе мы изучаем автоматы без выходных сигналов и называем их полуавтоматами. В зависимости от исследуемых задач рассматриваются полуавтоматы, у которых множества состояний наделены дополнительной математической структурой, согласованной с функцией переходов полуавтомата. Мы исследуем полуавтоматы над графами (так называемые графовые полуавтоматы), множество состояний которых наделено математической структурой графа. Универсальный графовый полуавтомат $\rm{Atm}(G)$  — это универсально притягивающий объект в категории полуавтоматов, у которых множество состояний наделено структурой графа $G$, сохраняющейся функцией переходов полуавтомата. Полугруппа входных сигналов такого полуавтомата имеет вид $S(G)=\rm{End}\ G$. Она может рассматриваться как производная алгебраическая система математического объекта $\rm{Atm}(G)$, которая содержит полезную информацию об исходном объекте. Свойства такой полугруппы взаимосвязаны со свойствами алгебраической структуры полуавтомата, это означает, что универсальные графовые полуавтоматы можно изучать путем исследования их полугрупп входных сигналов. Для таких полугрупп представляет интерес проблема конкретной характеризации универсальных графовых полуавтоматов: при каких условиях на множестве состояний $X$ полуавтомата $A=(X,S,\delta)$ возможно задать бинарное отношение $\rho$, такое, что для графа $G=(X,\rho)$ будет выполняться равенство $A=\rm{Atm}(G)$. В данной работе эта проблема решается для графовых полуавтоматов над рефлексивными квазибесконтурными графами.