Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


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

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
28.02.2025
Full text:
(downloads: 55)
Language: 
English
Heading: 
Article type: 
Article
UDC: 
519.713.2
EDN: 
DEBJXL

On structure of isomorphisms of universal graphic automata

Autors: 
Molchanov Vladimir Aleksandrovich, Saratov State University
Farakhutdinov Renat Abuhanovich, Saratov State University
Abstract: 

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.

References: 
  1. Plotkin B. I. Groups of automorphisms of algebraic systems. California, Wolters Noordhoff Publishing, 1972. 502 p. (Rus. ed. : Moscow, Nauka, 1966. 604 p.).
  2. 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
  3. 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
  4. 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).
  5. Gluskin L. M. Semi-groups of isotone transformations. Uspekhi Matematicheskikh Nauk, 1961, vol. 16, iss. 5, pp. 157–162 (in Russian).
  6. 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
  7. 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).
  8. 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
  9. 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).
  10. 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
  11. 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).
  12. Harary F. Graph theory. Boston, Addison-Wesley Publishing Company, 1969. 270 p. (Russ. ed. : Moscow, Mir, 1973. 300 p.).
  13. 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
  14. Kurosh A. G. Teoriya grupp [Group theory]. Moscow, Nauka, 1967. 648 p. (in Russian).
Received: 
01.09.2023
Accepted: 
10.10.2023
Published: 
28.02.2025