О вычислительных возможностях одномерных клеточных автоматов с локаторами
Получена: 30.10.2026 Принята: 31.10.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 99–102
Аннотация
В работе исследуются вычислительные возможности одномерных клеточных автоматов с локаторами (КАсЛ). Вводится определение вычисления функции при помощи КАсЛ и показывается, что в рамках данного определения класс задач, решаемых КАсЛ за полиномиальное время, совпадает с PSPACE. Нетривиальной частью этого результата является одномерный клеточный автомат с локаторами, решающий за полиномиальное время задачу проверки истинности булевых формул с кванторами.
Ключевые слова: клеточные автоматы с локаторами, вычислительная сложность, полиномиальное время, PSPACE.
BibTeX
@article{IS-Kalachev2026,
author = {Калачев, Глеб Вячеславович},
title = {{О вычислительных возможностях одномерных клеточных автоматов с локаторами}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {99--102},
}
AMSBIB
\RBibitem{IS-Kalachev2026}
\by Г.\,В.~Калачев
\paper О вычислительных возможностях одномерных клеточных автоматов с локаторами
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 99--102
Опубликовано на условиях лицензии
Creative Commons Attribution 4.0 International (CC BY 4.0)
EN