On a concrete characterization problem of universal graphic semiautomata

R. A. Farakhutdinov

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 4, pp. 458-467

Résumé

Automata theory is one of the branches of mathematical cybernetics, that studies information transducers that arise in many applied problems. The major objective of automata theory is to develop methods by which one can describe and analyze the dynamic behavior of discrete systems. In this paper, we consider automata without output signals (called semiautomata). Depending on study tasks, semiautomata are considered, for which the set of states is equipped with additional mathematical structure preserved by the transition function of semiautomata. We investigate semiautomata over graphs and call them graphic semiautomata. For graphs $G$ a universal graphic semiautomaton $\rm{Atm}(G)$ is the universally attracted object in the category of graphic semiautomata, for which the set of states is equipped with the structure of the graph $G$. The input signal semigroup of the universal graphic semiautomaton is $S(G) = \rm{End}\ G$. It may be considered as a derived algebraic system of the mathematical object $\rm{Atm}(G)$. It is common knowledge that properties of the semigroup are closely interconnected with properties of the algebraic structure of the semiautomaton. This suggests that universal graphic semiautomata may be researched using their input signal semigroups. In this article, we investigate the concrete characterization problem of graphic semiautomata over quasi-acyclic reflexive graphs. The main result of our study states necessary and sufficient conditions for a semiautomaton to be a universal graphic semiautomaton over quasi-acyclic reflexive graphs.