Complexity of the Addressation Problem for Idempotent Cellular Automata with Locators
Received: 05 Nov 2026 Accepted: 06 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 70–73
Abstract
We study the complexity of the addressation problem for one-dimensional idempotent cellular automata with locators. On a tape infinite in both directions, we consider a segment of \(N+1\) marked cells, outside of which all cells are in the quiescent state. Given a transmitted address, it is required to single out the cell with this address. We establish the order of complexity: with a constant number of states, the addressation problem is solvable in \(O(\log N)\) steps.
Keywords: cellular automata with locators, addressation problem, idempotency, complexity.
BibTeX
@article{IS-Bukharina2026,
author = {Bukharina, Daria Anatolevna},
title = {{Complexity of the Addressation Problem for Idempotent Cellular Automata with Locators}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {70--73},
}
AMSBIB
\Bibitem{IS-Bukharina2026}
\by D.\,A.~Bukharina
\paper Complexity of the Addressation Problem for Idempotent Cellular Automata with Locators
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 70--73
\lang In Russian
RU