On the Computational Capabilities of One-Dimensional Cellular Automata with Locators
Received: 30 Oct 2026 Accepted: 31 Oct 2026
Published: 2026, vol. 30, issue 4, pp. 99–102
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)
RU