Теория синхронизируемости

Книга посвящена исследованию основных вопросов теории синхронизируемых автоматов. Автомат называется синхронизируемым, если он обладает словом, действие которого переводит автомат в некоторое состояние вне зависимости от исходного состояния. Соответствующее слово называется синхронизируемым. Данное понятие является очень естественным, так как соответствует свойствам устойчивости и управляемости для дискретных систем, а сама теория активно изучается уже более 40 лет. Первая часть книги посвящена основной открытой теоретической проблеме - доказательству квадратичной (от числа состояний автомата) оценки на длины синхронизирующих слов. В частности, опровергнуты выдвинутые известными учеными гипотезы, справедливость которых была подтверждена ими для частных случаев и влекла бы решение проблемы в общем случае. На основе идей, свяазанных с опровержением этих гипотез, в книге доказана квадратичная оценка для класса однокластерных автоматов. Вторая часть книги посвящена основным вопросам,...