Тема: СИНХРОНИЗАЦИЯ ЧАСТИЧНЫХ И НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ: ПОДХОД НА ОСНОВЕ 8АТ-РЕШАТЕЛЕЙ

Актуальность темы и степень ее разработанности. Одной из самых простых и в то же время эффективных моделей дискретных си­стем являются конечные автоматы. Конечным автоматом называется тройка А = (ф, Е, 5), где Q - конечное множество состояний, Е - конеч­ный входной алфавит, 5 - функция переходов автомата, определяющая то, как буквы входного алфавита действуют на состояния.
При моделировании систем конечными автоматами состояния авто­мата соответствуют возможным состояниям системы, а буквы входного алфавита соответствуют допустимым операциям системы. В силу внеш­них воздействий или внутренних причин в таких системах могут проис­ходить некорректные переходы. Для того чтобы можно было вернуть контроль над системой после некорректных переходов, целесообразно проектировать систему таким образом, чтобы она обладала некоторой «перезагрузочной» последовательностью операций. Поэтому вопрос о су­ществовании такой перезагрузочной последовательности и вопрос о том, насколько короткой ее можно выбрать, являются существенными.
В теории автоматов идея перезагрузочной последовательности фор­мализуется с помощью понятия синхронизирующего слова. Для самого простого случая полных детерминированных автоматов (ДКА) это по­нятие вводится так: для А = (@, Е, 5) слово т £ Е* называется синхро­низирующим, если 5(д,т) = 5(р, т) для всех ц,р £ ф. Синхронизируе­мость ДКА хорошо изучена, см. обзоры [16,18]. В частности, известен алгоритм, который по данному ДКА А с п состояниями проверяет за время О(п2), имеет ли А синхронизирующее слово, и в случае положи­тельного ответа строит такое слово длины < п ~п за время О(п3).
В приложениях, однако, часто возникают более сложные типы ко­нечных автоматов: частичные детерминированные автоматы (ЧКА) и недетерминированные автоматы (НКА). Для них понятие синхронизи­руемости «расщепляется». В литературе рассматриваются две основных разновидности синхронизируемости для ЧКА - бережная синхронизиру­емость и точная синхронизируемость — и три разновидности синхро­низируемости для НКА, для которых пока не установились словесные названия и которые принято именовать П1-, П2- и П3-синхронизируемо­стью, см. монографию [11]. Для каждого из этих пяти вариантов за­дача проверки данного автомата на синхронизируемость оказывается РБРАСЕ-полной и существуют такие серии автоматов с неограниченно растущим числом состояний, что минимальная длина соответствующей разновидности синхронизирующего слова для автоматов этой серии экс­поненциально зависит от числа состояний.
В последние десятилетия стал популярным подход к труднорешае­мым задачам, основанный на их сведении к задаче ВЫПОЛНИМОСТЬ. В задаче ВЫПОЛНИМОСТЬ дан набор клозов (дизъюнкций булевых переменных и их отрицаний) и требуется определить, существует ли на­бор значений переменных, обращающий все эти клозы в истинные вы­сказывания. Специализированные программы для решения задачи ВЫ­ПОЛНИМОСТЬ, которые принято называть БЛТ-решателями, способ­ны успешно оперировать с экземплярами задачи ВЫПОЛНИМОСТЬ, включающими сотни тысяч переменных и миллионы клозов. В то же время, в силу классической теоремы Кука-Левина задача ВЫПОЛНИ­МОСТЬ КР-полна, т.е. к ней может быть сведена любая задача из класса КР. Более того, во многих случаях удается построить достаточно «эко­номное» сведение, при котором размеры возникающих экземпляров за­дачи ВЫПОЛНИМОСТЬ не слишком велики по сравнению с размера­ми экземпляров исходной задачи. Таким образом, можно решать труд­ные задачи так: сводим интересующую нас задачу к задаче ВЫПОЛ­НИМОСТЬ и запускаем БЛТ-решатель на получающихся экземплярах задачи ВЫПОЛНИМОСТЬ. В обзоре [8] и справочной книге [3] можно найти выразительные примеры эффективного применения такого подхо­да в самых разных областях.
В вопросах синхронизации ДКА подход, основанный на БЛТ-решате- лях, был впервые применен в [17] и затем в [9]. Для изучения синхрониза­ции ЧКА и НКА сведение к задаче ВЫПОЛНИМОСТЬ и БЛТ-решатели до работ автора и М.В.Волкова не применялись...
Купить

В заключении подведены итоги диссертационной работы, сформу­лированы основные результаты и выводы.
• Построены масштабируемые сведения задач о существовании син­хронизирующего слова к задаче ВЫПОЛНИМОСТЬ. С помощью об­ширных экспериментов продемонстрировано, что построенные сведения позволяют даже при использовании простейшего БЛТ-решателя и скром­ных вычислительных ресурсов находить кратчайшие синхронизирующие слова для всех разновидностей синхронизации частичных детерминиро­ванных и недетерминированных автоматов в пределах до 100 состояний.
• Проведены экспериментальные исследования бережной и точной синхронизируемости частичных детерминированных автоматов и О1-, О2- и О3-синхронизируемости недетерминированных автоматов. Даны теоретические обоснования ряда экспериментальных наблюдений. Пока­зано, что для случайного частичного детерминированного автомата с п состояниями, двумя входными буквами и одним неопределенным перехо­дом вероятность точной синхронизируемости при п ^ то асимптотиче­ски равна 1 — 0(п1), а вероятность бережной синхронизируемости растет намного медленней.
• Для двух новых бесконечных серий медленно синхронизируемых частичных детерминированных автоматов с двумя входными буквами и одним неопределенным переходом найдены длины кратчайших бережно синхронизирующих слов (как функции от числа состояний).
Проведенное исследование позволяет сделать вывод об адекватно­сти подхода к задачам синхронизации частичных детерминированных и недетерминированных автоматов с помощью БЛТ-решателей.
Рекомендации, перспективы дальнейшей разработки темы. Представляется перспективным применение разработанных в диссерта­ции алгоритмов в сочетании с более производительными БЛТ-решателя- ми. Возможность такого применения обеспечена тем, что все современ­ные БЛТ-решатели оперируют входными данными, представленными в одном и том же формате. При экспериментах по синхронизации слу­чайных автоматов возможно использование вычислительных кластеров, поскольку автоматы можно обрабатывать параллельно.
Большой интерес представляют также разработка дизайна новых вы­числительных экспериментов и дальнейший теоретический анализ уже накопленного массива экспериментальных результатов.
Купить