On the problem of abstract characterization of universal graphic automata

This work is devoted to the algebraic theory of automata, which is one of the branches of mathematical cybernetics, which studies information transformation devices that arise in many applied problems. Depending on a specific problem, automata are considered, in which the main sets are equipped with additional mathematical structures consistent with the functions of an automaton. In this work, we study automata over graphs — graphic automata, that is, automata in which the set of states and the set of output signals are equipped with the mathematical structure of graphs. For graphs $G$ and $H$ universal graphic automaton $\text{Atm}(G,H)$ is a universally attracting object in the category of semigroup automata. The input signal semigroup of such automaton is $S = \text{End}\ G \times \text{Hom}(G,H)$. Naturally, interest arises in studying the question of abstract characterization of universal graph automata: under what conditions will the abstract automaton $A$ be isomorphic to the universal graph automaton $\text{Atm}(G,H)$ over graphs $G$ from the class ${math\bf K_1} $, $H$ from class ${\mathbf K_2}$? The purpose of the work is to study the issue of elementary axiomatization of some classes of graphic automata. The impossibility of elementary axiomatization by means of the language of restricted predicate calculus of some wide classes of such automata over reflexive graphs is proved.