Geodesic
On the problem of abstract characterization of universal graphic automata
Čebyševskij sbornik, Tome 25 (2024) no. 1, pp. 116-126.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $G$ and $H$ universal graphic automaton $\text{Atm}(G,H)$ is a universally attracting object in the category of semigroup automata. The input signal semigroup of such automaton is $S = \text{End}\ G \times \text{Hom}(G,H)$. Naturally, interest arises in studying the question of abstract characterization of universal graph automata: under what conditions will the abstract automaton $A$ be isomorphic to the universal graph automaton $\text{Atm}(G,H)$ over graphs $G$ from the class ${math\bf K_1} $, $H$ from class ${\mathbf 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.
Keywords: automaton, semigroup, graph, abstract characterization, axiomatization. 
@article{CHEB_2024_25_1_a7,
     author = {R. A. Farakhutdinov},
     title = {On the problem of abstract characterization of universal graphic automata},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {116--126},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2024_25_1_a7/}
}
TY  - JOUR
AU  - R. A. Farakhutdinov
TI  - On the problem of abstract characterization of universal graphic automata
JO  - Čebyševskij sbornik
PY  - 2024
SP  - 116
EP  - 126
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2024_25_1_a7/
LA  - ru
ID  - CHEB_2024_25_1_a7
ER  - 
%0 Journal Article
%A R. A. Farakhutdinov
%T On the problem of abstract characterization of universal graphic automata
%J Čebyševskij sbornik
%D 2024
%P 116-126
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2024_25_1_a7/
%G ru
%F CHEB_2024_25_1_a7
R. A. Farakhutdinov. On the problem of abstract characterization of universal graphic automata. Čebyševskij sbornik, Tome 25 (2024) no. 1, pp. 116-126. http://geodesic.mathdoc.fr/item/CHEB_2024_25_1_a7/

[1] Plotkin, B. I., Greenglaz, L. Ja., Gvaramija, A. A., Elements of algebraic theory of automata, Vyshaja Shkola, M., 1994, 191 pp. (In Russ.)

[2] Plotkin, B. I., Groups of automorphisms of algebraic systems, Nauka, M., 1966, 604 pp. (In Russ.)

[3] Pinus, A. G., “Elementary equivalence of derived structures of free semigroups, unars, and groups”, Algebra and logic, 43:6 (2004), 408–417 (In Russ.) | MR

[4] Pinus, A. G., “Elementary equivalence of derived structures of free lattices”, Izv. Vyssh. Uchebn. Zaved. Mat., 5 (2002), 44–47 (In Russ.) | Zbl

[5] Gluskin, L. M., “Semigroups and endomorphism rings of linear spaces”, Izv. Akad. Nauk SSSR Ser. Mat., 25:6 (1961), 809–814 (In Russ.) | MR | Zbl | Zbl

[6] Gluskin, L. M., “Semigroups of isotone transformations”, Uspekhi Mat. Nauk, 16:5 (1961), 157–162 (In Russ.) | MR | Zbl

[7] Vazhenin, Yu. M., “Elementary properties of semigroups of transformations of ordered sets”, Algebra and logic, 9:3 (1970), 281–301 (In Russ.) | Zbl

[8] Vazhenin, Yu. M., “The elementary definability and elementary characterizability of classes of reflexive graphs”, Izv. Vyssh. Uchebn. Zaved. Mat., 7 (1972), 3–11 (In Russ.) | Zbl

[9] Mikhalev, A. V., “Endomorphism rings of modules, and lattices of submodules”, J. Math. Sci., 5:6 (1976), 786–802 | DOI | MR | MR | Zbl | Zbl

[10] Ulam, S. M., A collection of mathematical problems, Interscience, New York, 1960, 150 pp. | MR | Zbl

[11] Jonsson B., Topics in Universal Algebras, Lecture Notes in Math., 250, Springer-Verlag, 1972, 230 pp. | DOI | MR

[12] Harary, F., Graph Theory, Addison Wesley, 1969, 288 pp. | MR | Zbl

[13] Maltzev, A. I., Algebraic systems, Nauka. Fizmatlit, M., 1970, 392 pp. (In Russ.) | MR

[14] Akimova, S. A., “Abstract characterization of endomorphism semigroups of ordered sets”, sb. nauch. tr., Mathematika. Mekhanika, 6, Izd. Saratov State Un., Saratov, 2004, 3–5 (In Russ.) | MR

[15] Farakhutdinov, R. A., “Relatively elementary definability of the class of universal graphic semiautomata in the class of semigroups”, Russian Math. (Iz. VUZ), 66:1 (2022), 62–70 | DOI | MR

[16] Kejsler, H. J., Chang, C. C., Model theory, Dover Publications, 2013, 672 pp. | MR

[17] Molchanov V. A., Farakhutdinov R. A., “On Concrete Characterization of Universal Graphic Automata”, Lobachevskii Journal of Mathematics, 43:3 (2022), 664–671 | DOI | MR | Zbl

[18] Kuratowski, K., Mostowski, A., Set theory, North-Holland, 1698, 417 pp. | MR | MR