Д. С. Ананичев, М. В. Волков, В. В. Гусев, “Примитивные орграфы с большими экспонентами и медленно синхронизируемые автоматы”, Зап. научн. сем. ПОМИ, 2012, том 402,страницы 9

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

Примитивные орграфы с большими экспонентами и медленно синхронизируемые автоматы

Д. С. Ананичев, М. В. Волков, В. В. Гусев

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

Аннотация: Мы приводим несколько бесконечных серий синхронизируемых автоматов, для каждого из которых длина кратчайшего синхронизирующего слова близка к квадрату числа состояний. Все эти автоматы тесно связаны с примитивными ориентированными графами с большими экспонентами. Библ. – 28 назв.

Ключевые слова: примитивный орграф, экспонента орграфа, синхронизируемый автомат, синхронизирующее слово, порог синхронизируемости, раскраска орграфа.

УДК: 519.713.4+519.172.3

Поступило: 27.12.2011