On the problem of abstract characterization of universal graphic automata
https://doi.org/10.22405/2226-8383-2024-25-1-116-126
Abstract
This work is devoted to the algebraic theory of automata, which is one of the branches of mathematical cybernetics, which studies information transformation devices that arise in many applied problems. Depending on a specific problem, automata are considered, in which the main sets are equipped with additional mathematical structures consistent with the functions of an automaton. In this work, we study automata over graphs — graphic automata, that is, automata in which the set of states and the set of output signals are equipped with the mathematical structure of graphs. For graphs 𝐺 and 𝐻 universal graphic automaton Atm(𝐺,𝐻) is a universally attracting object in the category of semigroup automata. The input signal
semigroup of such automaton is 𝑆 = End 𝐺×Hom(𝐺,𝐻). Naturally, interest arises in studying the question of abstract characterization of universal graph automata: under what conditions will the abstract automaton 𝐴 be isomorphic to the universal graph automaton Atm(𝐺,𝐻) over graphs 𝐺 from the class K_1, 𝐻 from class K_2? The purpose of the work is to study the issue of elementary axiomatization of some classes of graphic automata. The impossibility of elementary
axiomatization by means of the language of restricted predicate calculus of some wide classes of such automata over reflexive graphs is proved.
About the Author
Renat Abukhanovich Farakhutdinov
Saratov State University
Russian Federation
Russian Federation
postgraduate student
References
1. Plotkin, B. I., Greenglaz, L. Ja. & Gvaramija, A. A., 1994, “Elements of algebraic theory of automata”, Vyshaja Shkola, Moscow, 191 p. (In Russ.)
2. Plotkin, B. I., 1966, “Groups of automorphisms of algebraic systems”, Nauka, Moscow, 604 p. (In Russ.)
3. Pinus, A. G., 2004, “Elementary equivalence of derived structures of free semigroups, unars, and groups”, Algebra and logic, vol. 43, no. 6, pp. 408–417 (In Russ.)
4. Pinus, A.G., 2002, “Elementary equivalence of derived structures of free lattices”, Izv. Vyssh. Uchebn. Zaved. Mat., vol. 5, pp. 44–47 (In Russ.)
5. Gluskin, L. M., 1961, “Semigroups and endomorphism rings of linear spaces”, Izv. Akad. Nauk SSSR Ser. Mat., vol. 25, no. 6, pp. 809–814 (In Russ.)
6. Gluskin, L. M., 1961, “Semigroups of isotone transformations”, Uspekhi Mat. Nauk, vol. 16, no. 5, pp. 157–162 (In Russ.)
7. Vazhenin, Yu. M., 1970, “Elementary properties of semigroups of transformations of ordered sets”, Algebra and logic, vol. 9, no. 3, pp. 281–301 (In Russ.)
8. Vazhenin, Yu. M., 1972, “The elementary definability and elementary characterizability of classes of reflexive graphs”, Izv. Vyssh. Uchebn. Zaved. Mat., vol. 7, pp. 3–11 (In Russ.)
9. Mikhalev, A. V., 1976, “Endomorphism rings of modules, and lattices of submodules”, J Math Sci, vol. 5, no. 6, pp. 786–802.
10. Ulam, S. M., 1960, “A collection of mathematical problems”, Interscience, New York, 150 p.
11. Jonsson, B., 1972, “Topics in Universal Algebras”, Lecture Notes in Math. Springer-Verlag, vol. 250, 230 p.
12. Harary, F., 1969, “Graph Theory”, Addison Wesley, 288 p.
13. Maltzev, A. I., 1970, “Algebraic systems”, Nauka. Fizmatlit, Moscow, 392 p. (In Russ.)
14. Akimova, S. A., 2004, “Abstract characterization of endomorphism semigroups of ordered sets”, Mathematika. Mekhanika: sb. nauch. tr. Saratov: Izd. Saratov State Un., no. 6, pp. 3–5. (In Russ.)
15. Farakhutdinov, R. A., 2022, “Relatively elementary definability of the class of universal graphic semiautomata in the class of semigroups”, Allerton Press, vol. 66, no. 1, pp. 62–70.
16. Kejsler, H. J., Chang, C. C., 2013, “Model theory”, Dover Publications, 672 p.
17. Molchanov, V. A., Farakhutdinov, R. A., 2022, “On Concrete Characterization of Universal Graphic Automata”, Lobachevskii Journal of Mathematics, vol. 43, iss. 3, pp. 664–671.
18. Kuratowski, K., Mostowski, A., 1698, “Set theory”, North-Holland, 417 p.
Review
For citations:
Farakhutdinov R.A. On the problem of abstract characterization of universal graphic automata. Chebyshevskii Sbornik. 2024;25(1):116-126. (In Russ.) https://doi.org/10.22405/2226-8383-2024-25-1-116-126
Views:
263
Email this article 