LAP LAMBERT Academic Publishing GmbH & Co. KG (Saarbrucken) издало монографию Павла Мартюгина «Синхронизация конечных автоматов. Оценки длины и вычислительной сложности» (151 стр.).

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

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

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