On the problem of abstract characterization of universal graphic automata
Renat Abuhanovich Farakhutdinov · Чебышевский сборник · 2024
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 𝐺 and 𝐻 universal graphic automaton Atm(𝐺,𝐻) is a universally attracting object in the category of semigroup automata. The input signalsemigroup of such automaton is 𝑆 = End 𝐺×Hom(𝐺,𝐻). Naturally, interest arises in studying the question of abstract characterization of universal graph automata: under what conditions will the abstract automaton 𝐴 be isomorphic to the universal graph automaton Atm(𝐺,𝐻) over graphs 𝐺 from the class K_1, 𝐻 from class K_2? The purpose of the work is to study the issue of elementary axiomatization of some classes of graphic automata. The impossibility of elementaryaxiomatization by means of the language of restricted predicate calculus of some wide classes of such automata over reflexive graphs is proved.