Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Complexity of the Addressation Problem for Idempotent Cellular Automata with Locators

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover