Синхронизация конечных автоматов

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