Relatively elementary definability of the class of universal partial graphic semiautomata in the class of semigroups
Vladimir Alexandrovich Molchanov, Renat Abuhanovich Farakhutdinov · Mathematics and Theoretical Computer Science · 2025
The work is devoted to the algebraic theory of structured automata. We consider semigroup automata without output signals over graphs, which are called graphic semiautomata. We study partial graphic semiautomata, each input signal of which is a partial endomorphism of the state graph. In the category of partial graphic semiautomata over the graph G = (X, ρ), special attention is paid to the semiautomaton PAtm(G) = (G, PEnd(G),⋆) with semigroup PEnd(G) of all partial endomorphisms of the graph G, since it is a universally attracting object in this category and is called a universal partial graphic semiautomaton. The main result of the work is the proof of the relatively elementary definability of the class of universal partial graphic semiautomata over nontrivial reflexive graphs in the class of semigroups, and applications of got relatively elementary definability.