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

Данная работа посвящена алгебраической теории автоматов, являющейся одним из разделов математической кибернетики, в котором изучаются устройства преобразования информации, возникающие во многих прикладных задачах. В зависимости от исследуемых задач рассматриваются автоматы, у которых основные множества наделены дополнительными математическими структурами, согласованными с функциями автомата. В настоящей работе исследуются автоматы над графами — графовые автоматы, множество состояний и множество выходных сигналов которых наделены математическими структурами графов. Для графов $G$ и $H$ универсальный графовый автомат $\text{Atm}(G,H)$ является универсально притягивающим объектом в категории графовых автоматов. Полугруппа входных сигналов такого автомата имеет вид $S = \text{End}\ G \times \text{Hom}(G,H)$. Естественно возникает интерес к исследованию вопроса абстрактной характеризации универсальных графовых автоматов: при каких условиях абстрактный автомат $A$ будет изоморфен универсальному графовому автомату $\text{Atm}(G,H)$ над графами $G$ из класса ${\mathbf K_1}$, $H$ из класса ${\mathbf K_2}$? Целью работы является исследование вопроса элементарной аксиоматизации некоторых классов графовых автоматов. Доказана невозможность элементарной аксиоматизации средствами языка узкого исчисления предикатов некоторых широких классов таких автоматов над рефлексивными графами.