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

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