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

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов представляются автоматами $\mathrm{Atm}\,(H_1 ,H_2)$ с гиперграфом состояний $H_1$, гиперграфом выходных символов $H_2$ и полугруппой входных символов $S=\mathrm{End}\, H_1\times \mathrm{Hom}\,(H_1,H_2)$, которые называются универсальными гиперграфическими автоматами. Для такого автомата $\mathrm{Atm}\,(H_1 ,H_2)$ полугруппа входных символов $S$ является производной алгеброй отображений, свойства которой взаимосвязаны со свойствами алгебраической структуры данного автомата. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных символов. В настоящей работе исследуется проблема абстрактной характеризации универсальных гиперграфических автоматов, суть которой заключается в нахождении условий изоморфности произвольного автомата некоторому универсальному гиперграфическому автомату. Основной результат работы дает решение этой задачи для универсальных гиперграфических автоматов над эффективными гиперграфами с $p$-определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными) или разбиениями на классы нетривиальных эквивалентностей. Для решения основной задачи работы показано, что алгебраическая структура эффективных гиперграфов с $p$-определимыми ребрами полностью определяется отношением $(p+1)$-ограниченности его вершин и для универсальных гиперграфических автоматов над такими гиперграфами алгебраическая структура гиперграфов состояний и выходных символов полностью определяется каноническими отношениями полугруппы входных символов таких автоматов.