Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

For citation:

Farakhutdinov R. A. On a concrete characterization problem of universal graphic semiautomata. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2022, vol. 22, iss. 4, pp. 458-467. DOI: 10.18500/1816-9791-2022-22-4-458-467, EDN: PKWNTS

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 403)
Article type: 

On a concrete characterization problem of universal graphic semiautomata

Farakhutdinov Renat Abuhanovich, Saratov State University

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.

  1. Plotkin B. I. Gruppy avtomorfizmov algebraicheskikh sistem [Groups of Automorphisms of Algebraic Systems]. Moscow, Nauka, 1966. 604 p. (in Russian).
  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, EDN: GQLIGM
  3. Pinus A. G. On the elementary equivalence of derived structures of free lattices. Russian Mathematics (Izvestiya VUZ. Matematika), 2002, vol. 46, iss. 5, pp. 42–45.
  4. 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
  5. Vazhenin Yu. M. The elementary definability and elementary characterizability of classes of reflexive graphs. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 1972, iss. 7, pp. 3–11 (in Russian).
  6. Gluskin L. M. Semigroups and endomorphism rings of linear spaces. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 1959, vol. 23, iss. 6, pp. 841–870 (in Russian).
  7. Gluskin L. M. Semi-groups of isotone transformations. Uspekhi Matematicheskikh Nauk, 1961, vol. 16, iss. 5 (101), pp. 157–162 (in Russian).
  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, 1985, vol. 31, iss. 3, pp. 3005–3051. https://doi.org/10.1007/BF02106808
  9. Ulam S. M. A Сollection of Mathematical Problems. New York, Interscience, 1960. 150 p. (Russ. ed.: Moscow, Nauka, 1964. 168 p.). 
  10. Plotkin B. I., Greenglaz L. Ja., Gvaramija A. A. Elementy algebraicheskoj teorii avtomatov [Elements of Algebraic Theory of Automata]. Moscow, Vysshaya Shkola, 1994. 191 p. (in Russian).
  11. Lidl R., Pilz G. Applied Abstract Algebra. New York, Springer-Verlag, 1998. 487 p. (Russ. ed.: Ekaterinburg, Ural University Publ., 1996. 744 p.).
  12. International Conference MAL’TSEV MEETING November 16–20, 2020. Collection of Abstracts. Available at: http://www.math.nsc.ru/conference/malmeet/20/maltsev20.pdf (accessed 15 January 2021).
  13. Materials of the International Youth Scientific Forum “LOMONOSOV-2020”. Available at: https://lomonosov-msu.ru/archive/Lomonosov_2020/index.htm (accessed 15 January 2021) (in Russian).
  14. Bogomolov A. M., Saliy V. N. Algebraicheskie osnovy teorii diskretnykh sistem [Algebraic Foundations of the Theory of Discrete Systems]. Moscow, Nauka. Fizmatlit, 1997. 368 p. (in Russian).
  15. Harary F. Graph Theory. Boston, Addison-Wesley Publishing Company, 1969. 274 p. (Russ. ed.: Moscow, Mir, 1973. 300 p.).
  16. Ershov Yu. L. Problemy razreshimosti i konstruktivnye modeli [Problems of Decidability and Constructive Models]. Moscow, Nauka. Fizmatlit, 1980. 416 p. (in Russian).