Сложность задачи адресации идемпотентными клеточными автоматами с локаторами
Получена: 05.11.2026 Принята: 06.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 70–73
Аннотация
Исследуется сложность задачи адресации для одномерных идемпотентных клеточных автоматов с локаторами. На бесконечной в обе стороны ленте рассматривается отрезок из \(N+1\) размеченной клетки, вне которого все клетки находятся в состоянии покоя. Требуется по переданному адресу выделить клетку с этим адресом. Установлен порядок сложности: при константном числе состояний задача адресации разрешима за \(O(\log N)\) шагов.
Ключевые слова: клеточные автоматы с локаторами, задача адресации, идемпотентность, сложность.
BibTeX
@article{IS-Bukharina2026,
author = {Бухарина, Дарья Анатольевна},
title = {{Сложность задачи адресации идемпотентными клеточными автоматами с локаторами}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {70--73},
}
AMSBIB
\RBibitem{IS-Bukharina2026}
\by Д.\,А.~Бухарина
\paper Сложность задачи адресации идемпотентными клеточными автоматами с локаторами
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 70--73
Опубликовано на условиях лицензии
Creative Commons Attribution 4.0 International (CC BY 4.0)
EN