Год выпуска: 2012 Автор: Елена Прибавкина Издательство: LAP Lambert Academic Publishing Страниц: 96 ISBN: 9783847306894
Описание
Книга посвящена исследованию вопросов оптимальности в теории синхронизируемых автоматов. В связи с различными приложениями конечных автоматов как моделей дискретно работающих устройств возникает естественная задача восстановления контроля над устройством в условиях неопределенности. Теоретически эта задача решается с помощью понятия синхронизирующего слова, которое переводит автомат в одно и то же состояние, независимо от его первоначального состояния. В книге исследуются задачи оптимизации длины кратчайших синхронизирующих слов для синхронизируемых автоматов с выделенным неподвижным состоянием и для автоматов с конечным числом минимальных синхронизирующих слов. Для последнего класса автоматов изучается возможность построения эффективных алгоритмов, проверяющих принадлежность этому классу данного синхронизируемого автомата. Кроме того, в книге рассматриваются сжимающие слова, обобщающие понятие синхронизирующих слов. Для них также исследуются некоторые оптимизационные задачи.
