Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

On the Computational Capabilities of One-Dimensional Cellular Automata with Locators

Abstract

We study the computational power of one-dimensional cellular automata with locators. We formalize function computation in this model and prove that the languages recognizable in polynomial time are exactly those in PSPACE. The key step is the construction of a one-dimensional cellular automaton with locators that solves the quantified Boolean formula problem in polynomial time.

Keywords: cellular automata with locators, computational complexity, polynomial time, PSPACE.

BibTeX
@article{IS-Kalachev2026,
  author  = {Kalachev, Gleb Vyacheslavovich},
  title   = {{On the Computational Capabilities of One-Dimensional Cellular Automata with Locators}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {99--102},
}
AMSBIB
\Bibitem{IS-Kalachev2026}
\by G.\,V.~Kalachev
\paper On the Computational Capabilities of One-Dimensional Cellular Automata with Locators
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 99--102
\lang In Russian
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover