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.

Bibliographie

[1] Plotkin B. I., Groups of Automorphisms of Algebraic Systems, Nauka, M., 1966, 604 pp. (in Russian) | MR

[2] Pinus A. G., “Elementary equivalence of derived structures of free semigroups, unars, and groups”, Algebra and Logic, 43:6 (2004), 408–417 | DOI | MR

[3] Pinus A. G., “On the elementary equivalence of derived structures of free lattices”, Russian Mathematics (Izvestiya VUZ. Matematika), 46:5 (2002), 42–45 | MR

[4] Vazhenin Yu. M., “Elementary properties of semigroups of transformations of ordered sets”, Algebra and Logic, 9:3 (1970), 169–179 | DOI | MR

[5] Vazhenin Yu. M., “The elementary definability and elementary characterizability of classes of reflexive graphs”, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 1972, no. 7, 3–11 (in Russian)

[6] Gluskin L. M., “Semigroups and endomorphism rings of linear spaces”, Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 23:6 (1959), 841–870 (in Russian)

[7] Gluskin L. M., “Semi-groups of isotone transformations”, Uspekhi Matematicheskikh Nauk, 16:5(101) (1961), 157–162 (in Russian) | MR

[8] Markov V. T., Mikhalev A. V., Skornyakov L. A., Tuganbaev A. A., “Endomorphism rings of modules, and lattices of submodules”, Journal of Soviet Mathematics, 31:3 (1985), 3005–3051 | DOI | MR

[9] Ulam S. M., A Collection of Mathematical Problems, Interscience, New York, 1960, 150 pp. | MR

[10] Plotkin B. I., Greenglaz L. Ja., Gvaramija A. A., Elements of Algebraic Theory of Automata, Vysshaya Shkola, M., 1994, 191 pp. (in Russian)

[11] Lidl R., Pilz G., Applied Abstract Algebra, Springer-Verlag, New York, 1998, 487 pp. | MR

[12] International Conference MAL'TSEV MEETING, Collection of Abstracts (November 16–20, 2020) (accessed 15 January 2021)

[13] Materials of the International Youth Scientific Forum “LOMONOSOV-2020” (in Russian) (accessed 15 January 2021)

[14] Bogomolov A. M., Saliy V. N., Algebraic Foundations of the Theory of Discrete Systems, Nauka. Fizmatlit, M., 1997, 368 pp. (in Russian) | MR

[15] Harary F., Graph Theory, Addison-Wesley Publishing Company, Boston, 1969, 274 pp. | MR

[16] Ershov Yu. L., Problems of Decidability and Constructive Models, Nauka. Fizmatlit, M., 1980, 416 pp. (in Russian)