This article is cited in 4 papers

Mathematics

Lower estimate of complexity in the problem of searching the nearest neighbor on a straight line using a cellular automation with locators

D. I. Vasilyev, È. È. Gasanov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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.

Key words: cellular automata, homogeneous structures, the closest neighbour search problem.

UDC: 511

Received: 15.03.2023

DOI: 10.55959/MSU0579-9368-1-64-5-5

 English version: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2023, 78:5, 244–252

Bibliographic databases:

•