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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@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
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/

[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