Relatively elementary definability of the class of universal partial graphic semiautomata in the class of semigroups
https://doi.org/10.26907/2949-3919.2024.4.103-123
Abstract
The work is devoted to the algebraic theory of structured automata. We consider semigroup automata without output signals over graphs, which are called graphic semiautomata. We study partial graphic semiautomata, each input signal of which is a partial endomorphism of the state graph. In the category of partial graphic semiautomata over the graph G = (X, ρ), special attention is paid to the semiautomaton PAtm(G) = (G, PEnd(G),⋆) with semigroup PEnd(G) of all partial endomorphisms of the graph G, since it is a universally attracting object in this category and is called a universal partial graphic semiautomaton. The main result of the work is the proof of the relatively elementary definability of the class of universal partial graphic semiautomata over nontrivial reflexive graphs in the class of semigroups, and applications of got relatively elementary definability.
About the Authors
V. A. Molchanov
Saratov State University
Russian Federation
Russian Federation
Vladimir Aleksandrovich Molchanov
83 Astrakhanskaya str., Saratov 410012
R. A. Farakhutdinov
Saratov State University
Russian Federation
Russian Federation
Renat Abukhanovich Farakhutdinov
83 Astrakhanskaya str., Saratov 410012
References
1. B.I. Plotkin, L.Ja. Greenglaz, A.A. Gvaramija, Elements of algebraic theory of automata, Vysshaya shkola, M., 1994 [in Russian].
2. R. Lidl, G. Pilz, Applied abstract algebra, Springer-Verlag, New York, 1998. DOI: https://doi.org/10.1007/978-1-4757-2941-2
3. S. Ulam, A collection of mathematical problems, Interscience Publ., New York, 1960.
4. B.I. Plotkin, Groups of automorphisms of algebraic systems, Wolters-Noordhoff Publ., Groningen, 1972.
5. A.G. Pinus, Elementary equivalence of derived structures of free semigroups, unars, and groups, Algebra Logic 43 (6), 408–417 (2004). DOI: https://doi.org/10.1023/B:ALLO.0000048829.60182.48
6. A.G. Pinus, Elementary equivalence of derived structures of free lattices, Russ. Math. 46 (5), 42–45 (2002).
7. Yu.M. Vazhenin, Elementary properties of semigroups of transformations of ordered sets, Algebra Logic 9 (3), 281–301 (1970) [in Russian]. URL: https://www.mathnet.ru/rus/al1245
8. Yu.M. Vazhenin, The elementary definability and elementary characterizability of classes of reflexive graphs, Izv. Vyssh. Uchebn. Zaved. Mat. (7), 3–11 (1972) [in Russian]. URL: https://www.mathnet.ru/rus/ivm4076
9. L.M. Gluskin, Semigroups and endomorphism rings of linear spaces, Izv. Akad. Nauk SSSR Ser. Mat. 23 (6), 841–870 (1959) [in Russian]. URL: https://www.mathnet.ru/rus/im3817
10. L.M. Gluskin, Semigroups of isotone transformations, Uspekhi Mat. Nauk 16 (5), 157–162 (1961) [in Russian]. URL: https://www.mathnet.ru/rus/rm6671
11. V.T. Markov, A.V. Mikhalev, L.A. Skornyakov, A.A. Tuganbaev, Endomorphism rings of modules, and lattices of submodules, J. Soviet Math. 31 (3), 3005–3051 (1985). DOI: https://doi.org/10.1007/BF02106808
12. Yu.L. Ershov, Decidability problems and constructive models, Nauka, M., 1980 [in 1109 Russian].
13. R.A. Farakhutdinov, Relatively elementary definability of the class of universal graphic semiautomata in the class of semigroups, Russ. Math. 66 (1), 62–70 (2022). DOI: https://doi.org/10.3103/S1066369X22010029
14. A.I. Mal’cev, Algebraic Systems, Springer-Verlag, New York–Heidelberg, 1973. DOI: https://doi.org/10.1007/978-3-642-65374-2
15. F. Harary, Graph theory, Addison-Wesley Publ., 1969. DOI: https://doi.org/10.1201/9780429493768
16. A.H. Clifford, G.B. Preston, The algebraic theory of semigroups, AMS, New York, 1967.
17. V.V. Vagner, Semigroups of partial transformations with a symmetric transitivity relation, Izv. Vyssh. Uchebn. Zaved. Mat. (1), 81–88 (1957) [in Russian]. URL: https://www.mathnet.ru/rus/ivm3022
18. A. Robinson, Introduction to model theory and to the metamathematics of algebra, North-Holland Publ., 1965.
19. Yu.L. Ershov, I.A. Lavrov, A.D. Taimanov, M.A. Taitslin, Elementary theories, Russ. Math. Surv. 20 (4), 35–105 (1965). DOI: https://doi.org/10.1070/RM1965v020n04ABEH001188
Review
For citations:
Molchanov V.A., Farakhutdinov R.A. Relatively elementary definability of the class of universal partial graphic semiautomata in the class of semigroups. Mathematics and Theoretical Computer Science. 2024;2(4):103-123. (In Russ.) https://doi.org/10.26907/2949-3919.2024.4.103-123
Views:
58
Email this article 