On the Weakness of One-Dimensional Idempotent Cellular Automata with
Locators

Gasanov Elyar Eldarovich

On the Weakness of One-Dimensional Idempotent Cellular Automata with Locators

Gasanov E. E.

Gasanov Elyar Eldarovich

Doctor of Physical and Mathematical Sciences, Head of the Chair of Mathematical Theory of Intelligent Systems, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

0000-0002-0739-0967

Received: 16 May 2026 Revised: 15 Aug 2026 Accepted: 16 Aug 2026

Published: 2026, vol. 30, issue 3, pp. 151–169

Download full text (In Russian)

Abstract

We consider one-dimensional cellular automata with locators for which the semigroup defined on the broadcast alphabet is an idempotent monoid. It has previously been shown that complex cellular automata problems such as the firing squad synchronization problem or the problem of controlling the motion of a point on a line are solved quite simply in idempotent cellular automata with locators, and the problems essentially degenerate. In this paper, we show that for problems that require distance comparison, idempotent cellular automata with locators provide no asymptotic advantage over conventional cellular automata. However, the use of non-idempotent cellular automata provides a significant time advantage.

Keywords: Idempotent cellular automata with locators, comparison and addition of integers.

BibTeX

@article{IS-Gasanov2026,
  author  = {Gasanov, Elyar Eldarovich},
  title   = {{On the Weakness of One-Dimensional Idempotent Cellular Automata with Locators}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {3},
  pages   = {151--169},
}

AMSBIB

\Bibitem{IS-Gasanov2026}
\by E.\,E.~Gasanov
\paper On the Weakness of One-Dimensional Idempotent Cellular Automata with Locators
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 3
\pages 151--169
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue