Geodesic
Relative elementary definability of the class of universal graphic semiautomata in the class of semigroups
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2022), pp. 74-84.

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

The theory of automata is one of the branches of mathematical cybernetics, which studies information transformation devices that arise in many applied problems. In this paper, we study automata without output signals and call them semiautomata. Depending on specific problem, semiautomata are considered, in which the set of states is equipped with an additional mathematical structure consistent with the transition function of a semiautomaton. In this paper, we investigate semiautomata over graphs (what is known as graphic semiautomata), the set of states of which is equipped with the mathematical structure of a graph. Universal graphic semiautomaton $\text{Atm}(G)$ is the universally attracting object in the category of semiautomata, for which the set of states is equipped with the structure of a graph $G$, preserved by the transition function of the semiautomaton. The input signal semigroup of such semiautomaton is $S(G) = \text{End}\ G$. In this paper, we consider the problem of the relatively elementary definability of the class of universal graphic semiautomata over reflexive quasi-acyclic graphs in the class of semigroups, and applications of the obtained relatively elementary definability.
Keywords: semiautomata, semigroup of endomorphisms, relatively elementary definability, graph. 
@article{IVM_2022_1_a6,
     author = {R. A. Farakhutdinov},
     title = {Relative elementary definability of the class of universal graphic semiautomata in the class of semigroups},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {74--84},
     publisher = {mathdoc},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2022_1_a6/}
}
TY  - JOUR
AU  - R. A. Farakhutdinov
TI  - Relative elementary definability of the class of universal graphic semiautomata in the class of semigroups
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2022
SP  - 74
EP  - 84
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2022_1_a6/
LA  - ru
ID  - IVM_2022_1_a6
ER  - 
%0 Journal Article
%A R. A. Farakhutdinov
%T Relative elementary definability of the class of universal graphic semiautomata in the class of semigroups
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2022
%P 74-84
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2022_1_a6/
%G ru
%F IVM_2022_1_a6
R. A. Farakhutdinov. Relative elementary definability of the class of universal graphic semiautomata in the class of semigroups. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2022), pp. 74-84. http://geodesic.mathdoc.fr/item/IVM_2022_1_a6/

[1] Vazhenin Yu. M., Pinus A. G., “Elementarnaya klassifikatsiya i razreshimost teorii proizvodnykh struktur”, UMN, 2005, no. 3, 3–40 | Zbl

[2] Pinus A. G., “Ob elementarnoi ekvivalentnosti proizvodnykh struktur svobodnykh reshetok”, Izv. vuzov. Matem., 2002, no. 5, 44–47 | Zbl

[3] Pinus A. G., “Ob elementarnoi ekvivalentnosti proizvodnykh struktur svobodnykh polugrupp, unarov i grupp”, Algebra i logika, 43:6 (2004), 408–417 | MR | Zbl

[4] Pinus A. G., “Ob elementarnoi ekvivalentnosti reshetok podalgebr i grupp avtomorfizmov svobodnykh algebr”, Sib. matem. zhurn., 49:4 (2008), 865–869 | MR | Zbl

[5] Gluskin L. M., “Polugruppy izotonnykh preobrazovanii”, UMN, 16:5 (1961), 157–162 | MR | Zbl

[6] Gluskin L. M., “Polugruppy i koltsa endomorfizmov lineinykh prostranstv”, Izv. AN SSSR. Ser. matem., 23 (1959), 841–870 | Zbl

[7] Bunina E. I., Mikhalev A. V., “Elementarnaya ekvivalentnost kolets endomorfizmov abelevykh p-grupp”, Fundament. i prikl. matem., 10:2 (2004), 135–224 | Zbl

[8] Murzin F. A., “Ob elementarnoi ekvivalentnosti kolets nepreryvnykh funktsii”, Teoriya modelei i ee prilozheniya, Kazakhsk. gos. un-t, Alma-Ata, 1980, 72–74

[9] Ershov Yu. L., Problemy razreshimosti i konstruktivnye modeli, Nauka, Fizmatlit, M., 1980

[10] Plotkin B. I., Gringlaz L. Ya., Gvaramiya A. A., Elementy algebraicheskoi teorii avtomatov, Vyssh. shk., M., 1994

[11] Lidl R., Pilts G., Prikladnaya abstraktnaya algebra, Izd-vo Uralsk. un-ta, Ekaterinburg, 1996

[12] Vazhenin Yu. M., “Ob elementarnoi opredelyaemosti i elementarnoi kharakterizuemosti klassov refleksivnykh grafov”, Izv. vuzov. Matem., 1972, no. 7, 3–11 | Zbl

[13] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, Fizmatlit, M., 1997 | MR

[14] Kharari F., Teoriya grafov, Mir, M., 1973

[15] Vazhenin Yu. M., “Elementarnye svoistva polugrupp preobrazovanii uporyadochennykh mnozhestv”, Algebra i logika, 9:3 (1970), 281–301 | Zbl