Год выпуска: 2011 Автор: Михаил Берлинков Издательство: LAP Lambert Academic Publishing Страниц: 84 ISBN: 9783845422626
Описание
Книга посвящена исследованию основных вопросов теории синхронизируемых автоматов. Автомат называется синхронизируемым, если он обладает словом, действие которого переводит автомат в некоторое состояние вне зависимости от исходного состояния. Соответствующее слово называется синхронизируемым. Данное понятие является очень естественным, так как соответствует свойствам устойчивости и управляемости для дискретных систем, а сама теория активно изучается уже более 40 лет. Первая часть книги посвящена основной открытой теоретической проблеме - доказательству квадратичной (от числа состояний автомата) оценки на длины синхронизирующих слов. В частности, опровергнуты выдвинутые известными учеными гипотезы, справедливость которых была подтверждена ими для частных случаев и влекла бы решение проблемы в общем случае. На основе идей, свяазанных с опровержением этих гипотез, в книге доказана квадратичная оценка для класса однокластерных автоматов. Вторая часть книги посвящена основным вопросам,...