"Записки научных семинаров ПОМИ"
Том 402, стр. 83-90
Синхронизируемые случайные автоматы над 4-буквенным алфавитом
Ю. И. Закс, Е. С. Скворцов
Институт математики и компьютерных наук,
Уральский федеральный университет,
620083, Ленина 51, Екатеринбург Россия
yuzaks@gmail.com,
skvortsoves@googlemail.com
- Аннотация: Изучается синхронизация случайного автомата, распределенного
равномерно на множестве всех детерминированных конечных автоматов
с $n$ состояниями и $m$ буквами. Мы показываем, что для $m = 4$
вероятность того, что случайный автомат синхронизируем, больше
положительной константы.
Библ. -- 9 назв.
- Ключевые слова: синхронизируемый автомат, случайный автомат, гипотеза Черни
[syncronizing automaton, random automaton, Cerny Conjecture]
Полный текст(.pdf)