Общая характеристика работы 2
Положения, выносимые на защиту 5
Степень достоверности и апробация результатов 6
Основное содержание работы 7
Заключение 15
Список литературы 17
Актуальность темы и степень ее разработанности. Одной из самых простых и в то же время эффективных моделей дискретных систем являются конечные автоматы. Конечным автоматом называется тройка А = (ф, Е, 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), а вероятность бережной синхронизируемости растет намного медленней.
• Для двух новых бесконечных серий медленно синхронизируемых частичных детерминированных автоматов с двумя входными буквами и одним неопределенным переходом найдены длины кратчайших бережно синхронизирующих слов (как функции от числа состояний).
Проведенное исследование позволяет сделать вывод об адекватности подхода к задачам синхронизации частичных детерминированных и недетерминированных автоматов с помощью БЛТ-решателей.
Рекомендации, перспективы дальнейшей разработки темы. Представляется перспективным применение разработанных в диссертации алгоритмов в сочетании с более производительными БЛТ-решателя- ми. Возможность такого применения обеспечена тем, что все современные БЛТ-решатели оперируют входными данными, представленными в одном и том же формате. При экспериментах по синхронизации случайных автоматов возможно использование вычислительных кластеров, поскольку автоматы можно обрабатывать параллельно.
Большой интерес представляют также разработка дизайна новых вычислительных экспериментов и дальнейший теоретический анализ уже накопленного массива экспериментальных результатов.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
