Geodesic
Collectives of Automata in Finitely Generated Groups
Matematičeskie zametki, Tome 108 (2020) no. 5, pp. 692-701.

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

The present paper is devoted to traversing a maze by a collective of automata. This part of automata theory gave rise to a fairly wide range of diverse problems ([1:u692], [2:u692]), including those related to problems of the theory of computational complexity and probability theory. It turns out that the consideration of complicated algebraic objects, such as Burnside groups, can be interesting in this context. In the paper, we show that the Cayley graph a finitely generated group cannot be traversed by a collective of automata if and only if the group is infinite and its every element is periodic.
Keywords: finite automata, Burnside groups, robots in mazes, maze traversing. 
@article{MZM_2020_108_5_a4,
     author = {D. V. Gusev and I. A. Ivanov-Pogodaev and A. Ya. Kanel-Belov},
     title = {Collectives of {Automata} in {Finitely} {Generated} {Groups}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {692--701},
     publisher = {mathdoc},
     volume = {108},
     number = {5},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2020_108_5_a4/}
}
TY  - JOUR
AU  - D. V. Gusev
AU  - I. A. Ivanov-Pogodaev
AU  - A. Ya. Kanel-Belov
TI  - Collectives of Automata in Finitely Generated Groups
JO  - Matematičeskie zametki
PY  - 2020
SP  - 692
EP  - 701
VL  - 108
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2020_108_5_a4/
LA  - ru
ID  - MZM_2020_108_5_a4
ER  - 
%0 Journal Article
%A D. V. Gusev
%A I. A. Ivanov-Pogodaev
%A A. Ya. Kanel-Belov
%T Collectives of Automata in Finitely Generated Groups
%J Matematičeskie zametki
%D 2020
%P 692-701
%V 108
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2020_108_5_a4/
%G ru
%F MZM_2020_108_5_a4
D. V. Gusev; I. A. Ivanov-Pogodaev; A. Ya. Kanel-Belov. Collectives of Automata in Finitely Generated Groups. Matematičeskie zametki, Tome 108 (2020) no. 5, pp. 692-701. http://geodesic.mathdoc.fr/item/MZM_2020_108_5_a4/

[1] V. B. Kudryavtsev, G. Kilibarda, Sh. Ushchumlich, “Sistemy avtomatov v labirintakh”, Matem. voposy kibernet., 14 (2005), 93–160 | Zbl

[2] A. V. Andzhans, Povedenie determinirovannykh i veroyatnostnykh avtomatov v labirintakh, Dis. $\dots$ kand. fiz.-matem. nauk, Riga, 1987

[3] G. Kilibarda, “On the minimum universal collectives of automata for plane labyrinths”, Discrete Math. Appl., 3:6 (1993), 555–586 | MR | Zbl

[4] G. Kilibarda, “O minimalnykh universalnykh kollektivakh avtomatov dlya ploskikh labirintov”, Diskret. matem., 6:4 (1994), 133–153 | MR | Zbl

[5] A. Szepietowski, “A finite 5-pebble-automaton can search every maze”, Inform. Process. Lett., 15:5 (1982), 199–204 | MR | Zbl

[6] G. Kilibarda, Sh. Ushchumlich, “O labirintakh-lovushkakh dlya kollektivov avtomatov”, Diskret. matem., 5:2 (1993), 29–50 | MR | Zbl

[7] P. S. Novikov, S. I. Adyan, “O beskonechnykh periodicheskikh gruppakh. I”, Izv. AN SSSR. Ser. matem., 32:1 (1968), 212–244 | MR | Zbl

[8] V. B. Kudryavtsev, A. S. Podkolzin, Sh. Ushchumlich, Vvedenie v teoriyu abstraktnykh avtomatov, Izd-vo Mosk. un-ta, M., 1985 | MR

[9] V. B. Kudryavtsev, S. V. Aleshin, A. S. Podkolzin, Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR

[10] F. Kharari, Teoriya grafov, Mir, M., 1973 | MR | Zbl

[11] W. Burnside, “On an unsettled question in the theory of discontinuous groups”, Quart. J., 33 (1902), 230–238 | Zbl

[12] I. N. Sanov, “Reshenie problemy Bernsaida dlya pokazatelya 4”, Uch. zap. Leningr. gos. un-ta. Ser. matem., 10 (1940), 166–170 | Zbl

[13] M. Hall Jr., “Solution of the Burnside problem for exponentsix”, Illinois J. Math, 2 (1958), 764–786 | MR | Zbl

[14] E. S. Golod, “O nil-algebrakh i finitno-approksimiruemykh $p$-gruppakh”, Izv. AN SSSR. Ser. matem., 28:2 (1964), 273–276 | MR | Zbl

[15] S. I. Adyan, Problema Bernsaida i tozhdestva v gruppakh, Nauka, M., 1975 | MR | Zbl

[16] S. I. Adyan, “Novye otsenki nechetnykh periodov beskonechnykh bernsaidovykh grupp”, Izbrannye voprosy matematiki i mekhaniki, Tr. MIAN, 289, MAIK «Nauka/Interperiodika», M., 2015, 41–82 | DOI

[17] S. Ivanov, “The free Burnside groups of sufficiently large exponents”, Internat. J. Algebra Comput., 4:1 (1994), 1–307 | MR

[18] I. G. Lysenok, “Beskonechnye bernsaidovy gruppy chetnogo perioda”, Izv. RAN. Ser. matem., 60:3 (1996), 3–224 | DOI | MR | Zbl