"Записки научных семинаров ПОМИ"

Том 402, стр. 9-39

Институт математики и компьютерных наук Уральский федеральный университет, пр. Ленина 51 620000 Екатеринбург, Россия

Dmitry.Ananichev@usu.ru, Mikhail.Volkov@usu.ru, vl.gusev@gmail.com

Аннотация:Мы приводим несколько бесконечных серий синхронизируемых автоматов, для каждого из которых длина кратчайшего синхронизирующего слова близка к квадрату числа состояний. Все эти автоматы тесно связаны с примитивными ориентированными графами с большими экспонентами. Библ. -- 28 назв.
Ключевые слова: примитивный орграф, экспонента орграфа, синхронизируемый автомат, синхронизирующее слово, порог синхронизируемости, раскраска орграфа [primitive digraph, exponent of a digraph, synchronizing automaton, reset word, synchronization threshold, coloring of a digraph]