Синхронизируемые автоматы

Книга посвящена исследованию вопросов оптимальности в теории синхронизируемых автоматов. В связи с различными приложениями конечных автоматов как моделей дискретно работающих устройств возникает естественная задача восстановления контроля над устройством в условиях неопределенности. Теоретически эта задача решается с помощью понятия синхронизирующего слова, которое переводит автомат в одно и то же состояние, независимо от его первоначального состояния. В книге исследуются задачи оптимизации длины кратчайших синхронизирующих слов для синхронизируемых автоматов с выделенным неподвижным состоянием и для автоматов с конечным числом минимальных синхронизирующих слов. Для последнего класса автоматов изучается возможность построения эффективных алгоритмов, проверяющих принадлежность этому классу данного синхронизируемого автомата. Кроме того, в книге рассматриваются сжимающие слова, обобщающие понятие синхронизирующих слов. Для них также исследуются некоторые оптимизационные задачи.