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

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных сигналов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов называются универсальными гиперграфическими автоматами. Для таких автоматов полугруппы входных сигналов являются производными алгебрами отображений, свойства которых взаимосвязаны со свойствами алгебраической структуры исходного автомата. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных сигналов. Ранее авторами было доказано, что такие автоматы над гиперграфами из довольно широкого класса полностью (с точностью до изоморфизма) определяются своими полугруппами входных сигналов. В настоящей работе доказывается элементарная определимость класса таких автоматов в классе полугрупп. Основной результат статьи дает решение этой задачи для универсальных гиперграфических автоматов над $p$-гиперграфами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных сигналов являются плоскостями (например, проективными или аффинными). Полученные результаты показывают, что универсальный гиперграфический автомат над $p$-гиперграфами с точностью до изоморфизма представляется как алгебраическая система, построенная в полугруппе входных сигналов этого автомата с помощью канонических отношений этого автомата, которые определяются формулами элементарной теории полугрупп. С помощью такого представления автоматов определяется эффективная синтаксическая трансформация формул элементарной теории гиперграфических автоматов в формулы элементарной теории полугрупп, что позволяет всесторонне исследовать взаимосвязь элементарных свойств универсальных гиперграфических автоматов над $p$-гиперграфами и их полугрупп входных сигналов.