Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

For citation:

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. DOI: 10.18500/1816-9791-2020-20-1-42-50, EDN: UEIFDI

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
02.03.2020
Full text:
download
(downloads: 521)
Language: 
English
Heading: 
Mathematics
Article type: 
Article
UDC: 
519.713.2
DOI: 
10.18500/1816-9791-2020-20-1-42-50
EDN: 
UEIFDI

On Definability of Universal Graphic Automata by Their Input Symbol Semigroups

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

Universal graphic automaton Atm(G, G′ ) is the universally attracting object in the category of automata, for which the set of states is equipped with the structure of a graph G and the set of output symbols is equipped with the structure of a graph G′ preserved by transition and output functions of the automata. The input symbol semigroup of the automaton is S(G, G′ ) = End G×Hom(G, G′ ). It can be considered as a derivative algebraic system of the mathematical object Atm(G, G′ ) 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, we can study universal graphic automata by researching their input symbol semigroups. For these semigroups it is interesting to study the problem of definability of universal graphic automata by their input symbol semigroups — under which conditions are the input symbol semigroups of universal graphic automata isomorphic. This is the subject we investigate in the present paper. The main result of our study states that the input symbol semigroups of universal graphic automata over reflexive graphs determine the initial automata up to isomorphism and duality of graphs if the state graphs of the automata contain an edge that does not belong to any cycle.

Key words: 
generalized Galois theory
automaton
graph
semigroup
isomorphism
References: 
  1. Plotkin B. I. Groups of Automorphisms of Algebraic Systems. Groningen, The Netherlands, WoLters-Noordhoff Publ., 1972. 502 p.
  2. Pinus A. G. On the elementary equivalence of derived structures of free lattices. Russian Math. (Iz. VUZ), 2002, vol. 46, no. 5, pp. 42–45.
  3. Pinus A. G. Elementary Equivalence of Derived Structures of Free Semigroups. Algebra and Logic, 2004, vol. 43, no. 6, pp. 408–417. DOI: https://doi.org/10.1023/B:ALLO.0000048829.60182.48
  4. Gluskin L. M. Semigroups and rings of endomorphisms of linear spaces. Izv. Akad. Nauk SSSR. Ser. Mat., 1959, vol. 23, iss. 6, pp. 841–870 (in Russian).
  5. Gluskin L. M. Semi-groups of isotone transformations. Uspekhi Mat. Nauk, 1961, vol. 16, iss. 5 (101), pp. 157–162 (in Russian).
  6. Vazhenin Yu. M. Ordered sets and their inf-endomorphisms. Math. Notes, 1970, vol. 7, iss. 3, pp. 204–208. DOI: https://doi.org/10.1007/BF01093116
  7. Vazhenin Yu. M. The elementary definability and elementary characterizability of classes of reflexive graphs. Izv. Vyssh. Uchebn. Zaved. Mat., 1972, no. 7, pp. 3–11 (in Russian).
  8. Markov V. T., Mikhalev A. V., Skornyakov L. A., Tuganbaev A. A. Rings of endomorphisms of modules and lattices of submodules. J. Soviet Math., 1985, vol. 31, iss. 3, pp. 3005–3051. DOI: https://doi.org/10.1007/BF02106808
  9. Ulam S. M. A Collection of Mathematical Problems. NewYork, Interscience, 1960. 150 p.
  10. Plotkin B. I., Greenglaz L. Ja., Gvaramija A. A. Algebraic structures in automata and databases theory. River Edge, NJ, World Scientific Publ. Co., 1992. 296 p.
  11. Molchanov V. A. Semigroups of mappings on graphs. Semigroup Forum, 1983, vol. 27, pp. 155–199. DOI: https://doi.org/10.1007/BF02572738
  12. Molchanov V. A., Farakhutdinov R. A. On universal graphic automata. In: Komp’iuternye nauki i informatsionnye tekhnologii: materialy mezhdunarodnoy nauchnoy konferentsii [Computer Science and Information Technologies: Materials of the Int. Sci. Conf.]. Saratov, Izdatel’skii tsentr “Nauka”, 2018, pp. 276–279 (in Russian).
  13. Clifford A. H., G. B. Preston. The algebraic theory of semigroups. Providence, RI, Amer. Math. Soc., 1964. 224 p.
  14. 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).
  15. Harary F. Graph Theory. Reading, MA, Addison-Wesley, 1969. 274 p.
  16. Molchanov V. A. A universal planar automaton is determined by its semigroup of input symbols. Semigroup Forum, 2011, vol. 82, iss. 1, pp. 1–9. DOI: https://doi.org/10.1007/s00233-010-9256-8
Received: 
28.02.2019
Accepted: 
24.03.2019
Published: 
02.03.2020
  • 1159 reads