RUS  ENG
Полная версия
ЖУРНАЛЫ // Успехи математических наук // Архив

УМН, 2022, том 77, выпуск 5(467), страницы 53–130 (Mi rm10005)

Эта публикация цитируется в 2 статьях

Синхронизация конечных автоматов

М. В. Волков

Уральский федеральный университет

Аннотация: Дан обзор современного состояния теории синхронизируемых автоматов в её части, относящейся к случаю полных детерминированных автоматов. Освещены алгоритмические и теоретико-сложностные аспекты, описаны имеющиеся результаты в направлении гипотезы Черни и методы их получения.
Библиография: 193 названия.

Ключевые слова: конечный автомат, синхронизируемость, алгоритм, вычислительная сложность, порог синхронизации, гипотеза Черни.

УДК: 519.713

MSC: Primary 03D15, 20F10; Secondary 20M35, 68Q25, 68Q45, 68Q70, 68R15

Поступила в редакцию: 31.08.2020

DOI: 10.4213/rm10005


 Англоязычная версия: Russian Mathematical Surveys, 2022, 77:5, 819–891

Реферативные базы данных:


© МИАН, 2024