Geodesic
Lower estimate of complexity in the problem of searching the nearest neighbor on a straight line using a cellular automation with locators
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2023), pp. 33-39 
D. I. Vasilyev; È. È. Gasanov. Lower estimate of complexity in the problem of searching the nearest neighbor on a straight line using a cellular automation with locators. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2023), pp. 33-39. http://geodesic.mathdoc.fr/item/VMUMM_2023_5_a4/
@article{VMUMM_2023_5_a4,
     author = {D. I. Vasilyev and \`E. \`E. Gasanov},
     title = {Lower estimate of complexity in the problem of searching the nearest neighbor on a straight line using a cellular automation with locators},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {33--39},
     year = {2023},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2023_5_a4/}
}
TY  - JOUR
AU  - D. I. Vasilyev
AU  - È. È. Gasanov
TI  - Lower estimate of complexity in the problem of searching the nearest neighbor on a straight line using a cellular automation with locators
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2023
SP  - 33
EP  - 39
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2023_5_a4/
LA  - ru
ID  - VMUMM_2023_5_a4
ER  - 
%0 Journal Article
%A D. I. Vasilyev
%A È. È. Gasanov
%T Lower estimate of complexity in the problem of searching the nearest neighbor on a straight line using a cellular automation with locators
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2023
%P 33-39
%N 5
%U http://geodesic.mathdoc.fr/item/VMUMM_2023_5_a4/
%G ru
%F VMUMM_2023_5_a4

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

The paper considers the application of the locator cellular automaton model to the closest neighbour search problem. The locator cellular automaton model assumes the possibility for each cell to translate a signal through any distance using the ether. It was proven earlier that the ether model allows us to solve the problem with logarithmic time. In this paper we have derived a logarithmic lower bound for this problem.

[1] fon Neiman Dzh., Teoriya samovosproizvodyaschikhsya avtomatov, Mir, M., 1971

[2] Neumann J. von, Collected Works, N.Y., 1961–1963 | MR

[3] Neumann J. von, Theory of self-reproducing automata, London, 1966

[4] Burks A., Essays on Cellular Automata, University of Illinois Press, 1971 | MR

[5] Mur E.F., “Matematicheskie modeli samovosproizvedeniya”, Matematicheskie problemy v biologii, Mir, M., 1966

[6] Kudryavtsev V.B., Podkolzin A.S., Bolotov A.A., Osnovy teorii odnorodnykh struktur, Nauka, M., 1990 | MR

[7] Kudryavtsev V.B., Gasanov E.E., Podkolzin A.S., Teoriya intellektualnykh sistem, V 4 kn., v. 4, Teoriya avtomatov, Izdatelskie resheniya, M., 2018

[8] Titova E.E., “Konstruirovanie dvizhuschikhsya izobrazhenii kletochnymi avtomatami”, Intellektualnye sistemy. Teoriya i prilozheniya, 18:1 (2014), 153–180 | MR

[9] Kalachev G.V., Titova E.E., “O mere mnozhestva zakonov dvizheniya tochki, realizuemykh kletochnymi avtomatami”, Intellektualnye sistemy. Teoriya i prilozheniya, 22:3 (2018), 105–125 | MR

[10] Gasanov E.E., “Kletochnye avtomaty s lokatorami”, Intellektualnye sistemy. Teoriya i prilozheniya, 24:2 (2020), 120–133

[11] Vasilev D. I., “Poisk blizhaishego soseda na pryamoi s pomoschyu kletochnogo avtomata s lokatorami”, Intellektualnye sistemy. Teoriya i prilozheniya, 24:3 (2020), 99–119

[12] Vasilev D.I., “Poisk blizhaishego soseda na ploskosti s pomoschyu kletochnogo avtomata s lokatorami”, Intellektualnye sistemy. Teoriya i prilozheniya, 25:4 (2021), 83–87

[13] Kalachev G.V., “Zamechaniya k opredeleniyu kletochnogo avtomata s lokatorami”, Intellektualnye sistemy. Teoriya i prilozheniya, 24:4 (2020), 47–56

[14] Ibragimova D. E., “Slozhenie vektorov na pryamoi s pomoschyu kletochnogo avtomata s lokatorami”, Intellektualnye sistemy. Teoriya i prilozheniya, 26:4 (2022), 134–162