Universal hypergraphic automata representation by autonomous input symbols

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов представляются автоматами $\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$-определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными) или разбиениями на классы нетривиальных эквивалентностей. Статья публикуется в авторской редакции.