For citation:
Molchanov V. A., Farakhutdinov R. A. On structure of isomorphisms of universal graphic automata. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2025, vol. 25, iss. 1, pp. 34-45. DOI: 10.18500/1816-9791-2025-25-1-34-45, EDN: DEBJXL
On structure of isomorphisms of universal graphic automata
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. Depending on study tasks, automata are considered, for which the set of states and the set of output signals are equipped with additional mathematical structure preserved by transition and output functions of automata. We investigate automata over graphs and call them graphic automata. Universal graphic automaton Atm(G,H) is a universally attractive object in the category of such automata. The semigroup of input signals of the automaton is S(G,H)=End G×Hom(G,H). It can be considered as a derivative algebraic system of the mathematical object Atm(G,H), which contains useful information about the initial automaton. It is common knowledge that properties of the semigroup are interconnected with properties of the algebraic structure of the automaton. Hence, it is possible to study universal graphic automata by researching their input signal semigroups. Earlier the authors proved that a wide class of such kind of automata are determined up to isomorphism by their input signal semigroups. In this paper, we investigate a connection between isomorphisms of universal graphic automata and isomorphisms of their components — semigroups of input signals and graphs of states and output signals.
- Plotkin B. I. Groups of automorphisms of algebraic systems. California, Wolters Noordhoff Publishing, 1972. 502 p. (Rus. ed. : Moscow, Nauka, 1966. 604 p.).
- Pinus A. G. Elementary equivalence of derived structures of free semigroups, unars, and groups. Algebra and Logic, 2004, vol. 43, iss 6, pp. 408–417. https://doi.org/10.1023/B:ALLO.0000048829.60182.48
- Pinus A. G. On the elementary equivalence of derived structures of free lattices. Russian Mathematics, 2002, iss. 5, pp. 44–47 (in Russian). EDN: HQUCWH
- Gluskin L. M. Semigroups and rings of endomorphisms of linear spaces. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 1959, vol. 23, iss. 6, pp. 841–870 (in Russian).
- Gluskin L. M. Semi-groups of isotone transformations. Uspekhi Matematicheskikh Nauk, 1961, vol. 16, iss. 5, pp. 157–162 (in Russian).
- Vazhenin Yu. M. Elementary properties of semigroups of transformations of ordered sets. Algebra and Logic, 1970, vol. 9, iss 3, pp. 169–179. https://doi.org/10.1007/BF02218675
- Vazhenin Yu. M. Elementary definability and elementary characterizability of classes of reflexive graphs. Izvestiya Vysshih Uchebnyh Zavedenij. Matematika, 1972, iss. 7, pp. 3–11 (in Russian).
- Mikhalev A. V. Endomorphism rings of modules and lattices of submodules. Journal of Soviet Mathematics, 1976, vol. 5, iss. 6, pp. 786–802. https://doi.org/10.1007/BF01085149
- Plotkin B. I., Greenglaz L. Ya., Gvaramiya A. A. Elementy algebraicheskoy teorii avtomatov [Elements of algebraic theory of automata]. Moscow, Vyshaja Shkola, 1994. 191 p. (in Russian).
- Molchanov V. A., Farakhutdinov R. A. On definability of universal graphic automata by their input symbol semigroups. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2020, vol. 20, iss. 1, pp. 42–50. https://doi.org/10.18500/1816-9791-2020-20-1-42-50
- Bogomolov A. M., Salii V. N. Algebraicheskie osnovy teorii diskretnykh sistem [Algebraic foundations of the theory of discrete systems]. Moscow, Nauka, 1997. 368 p. (in Russian).
- Harary F. Graph theory. Boston, Addison-Wesley Publishing Company, 1969. 270 p. (Russ. ed. : Moscow, Mir, 1973. 300 p.).
- Farakhutdinov R. A. Relatively elementary definability of the class of universal graphic semiautomata in the class of semigroups. Russian Mathematics, 2022, vol. 66, iss. 1, pp. 62–70. https://doi.org/10.3103/S1066369X22010029
- Kurosh A. G. Teoriya grupp [Group theory]. Moscow, Nauka, 1967. 648 p. (in Russian).
- 206 reads