Оптимизация многокомпонентных дискретных систем на основе решения автоматных уравнений тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Тихомирова, Светлана Владимировна

• Тихомирова, Светлана Владимировна
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Тихомирова, Светлана Владимировна

Введение.

1. Основные определения. Постановка задачи оптимизации на основе автоматной модели.

1.1 Основные определения.

1.1.1 Конечные автоматы.

1.1.2 Операции над автоматами и полуавтоматами.

1.1.3 Синхронная композиция двух автоматов.

1.1.4 Многокомпонентная синхронная композиция.

1.2 Постановка задачи оптимизации на основе решения автоматных уравнений.

1.2.1 Задача оптимизации.

1.2.2 Определение автоматного уравнения для двухкомпонентной сети.

1.3 Методы решения бинарных автоматных уравнений.

1.3.1 Решение уравнения на основе безразличных последовательностей.

1.3.2 Решение уравнения на основе Е-автомата.

1.3.3 Языковый подход к решению автоматных уравнений.

1.4 Критерии оптимизации.

1.5 Выводы по главе.

2. Использование автоматных уравнений для оптимизации многокомпонентной композиции.

2.1 Многокомпонентная синхронная композиция.

2.1.1 Методы построения многокомпонентной синхронной композиции.

2.1.2 Свойства многокомпонентной композиции.

2.2 Автоматные уравнения для многокомпонентной композиции.

2.2.1 Решение автоматных уравнений для многокомпонентной композиции.

2.2.2 Сведение автоматного уравнения для многокомпонентной композиции к бинарному автоматному уравнению.

2.2.3 Разрешимость автоматного уравнения относительно различных алфавитов.

2.3 Упрощенные методы решения автоматных уравнений для оптимизации автоматных сетей.

2.3.1 Комбинационное решение автоматного уравнения.

2.3.2 Экспериментальные результаты по нахождению комбинационного решения.

2.3.3 Решение автоматного уравнения на основе безразличных последовательностей.

2.3.4 Экспериментальные результаты по нахождению безразличных последовательностей.

2.4 Основные результаты главы.

3. Покомпонентная оптимизация дискретных систем относительно различных критериев.

3.1 Глобальная оптимизация.

3.2 Локальная оптимизация.

3.2.1 Локальная оптимизация посредством решения множества автоматных уравнений.

3.2.2 Локальная оптимизация посредством решения системы уравнений

3.3 Критерии оптимизации.94*

3.3.1 Число связей в автоматной сети.

3.3.1.1 О минимизации числа связей на основе решения автоматного уравнения.

3.3.1.2 Нахождение наибольшего решения автоматного уравнения с заданным множеством входных алфавитов.

3.3.1.3 Минимизация числа входных переменных компоненты.98'

3.3.2 Отказоустойчивость компоненты.

3.3.3 Число вентилей в логической реализации компоненты.

3.4 Основные результаты главы.

4. Прогрессивные решения автоматных уравнений и систем автоматных уравнений.

4.1 Наибольшее прогрессивное решение автоматного уравнения.

1 4.2 Характеризация прогрессивных решений.

4.3 Прогрессивные решения системы уравнений.

4.4 Экспериментальные результаты по существованию прогрессивных решений.

4.5 Основные результаты главы.

Введение диссертации (часть автореферата) на тему «Оптимизация многокомпонентных дискретных систем на основе решения автоматных уравнений»

Актуальность проблемы

Автоматизация синтеза дискретных систем [1—3], в частности, цифровых схем, таких как большие интегральные схемы (БИС) и сверхбольшие интегральные схемы (СБИС) [4-9], была и остается одной из актуальных задач систем автоматизированного проектирования (САПР). Как известно, большинство из существующих автоматизированных методов [1013] синтеза многокомпонентных дискретных систем не позволяют синтезировать оптимальную систему. Проблема осложняется тем, что понятие оптимальности зависит от целей решаемой задачи, и, соответственно, задача оптимизации является многокритериальной. В некоторых случаях система должна соответствовать сразу нескольким критериям, причем некоторые из них являются взаимоисключающими. Например, отказоустойчивость систем обеспечивается за счет введения избыточности, таким образом, отказоустойчивая система не может иметь минимальное число элементов. Достаточно часто в качестве критерия оптимальности выступают число внутренних состояний системы [14-17], число различных библиотечных модулей [11, 12], количество связей между модулями [18 - 20] и другие [21, 22]. Однако и для данных критериев задача построения оптимальной системы не является решенной. Одним из подходов к оптимизации является итеративный подход, когда компоненты оптимизируются последовательно, и на каждом шаге проверяется, что новая реализация компоненты сохраняет внешнее поведение системы и улучшает предыдущую реализацию. Как известно [23 - 26], при использовании автоматной модели все допустимые реализации компоненты содержатся в наибольшем решении соответствующего автоматного уравнения. Поэтому исследование возможностей оптимизации дискретных систем и разработка соответствующих алгоритмов на основе решения автоматных уравнений является актуальной задачей.

Цель работы

Разработка методов оптимизации многокомпонентных дискретных систем на основе решения автоматных уравнений.

Основные задачи

1. Разработка методов решения автоматных уравнений для многокомпонентной композиции конечных автоматов.

2. Разработка упрощенных алгоритмов решения автоматных уравнений и оптимизации многокомпонентных автоматных сетей.

3. Исследование различных критериев оптимизации и разработка алгоритмов оптимизации компонент автоматной сети согласно заданным критериям.

4. Полное описание прогрессивных решений автоматных уравнений и систем автоматных уравнений. Только такие решения находят практическое применение.

Методы исследования

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

Научная новизна

1. Для снижения сложности оптимизации многокомпонентных дискретных систем предложен локальный подход, при котором компонента оптимизируется не относительно всей системы, а относительно соседних с нею компонент. Показано, что в этом случае для более эффективной оптимизации компоненты можно использовать совокупность автоматных уравнений и/или систему автоматных уравнений.

2. Предложен алгоритм нахождения наибольшего решения в наибольшем алфавите многокомпонентного автоматного уравнения. Такое наибольшее решение содержит все оптимальные решения как специальные редукции.

3. Предложен метод нахождения наибольшего, в том числе наибольшего прогрессивного, решения системы автоматных уравнений. Метод нахождения наибольшего прогрессивного решения системы автоматных уравнений расширяет известный метод нахождения наибольшего прогрессивного решения одного автоматного уравнения.

4. Сформулированы необходимые и достаточные условия того, что полностью определенная редукция наибольшего прогрессивного решения является прогрессивным решением.

5. Разработан алгоритм минимизации числа связей в автоматной сети на основе синтеза компоненты, которая зависит от меньшего числа входных переменных.

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

Основные положения, выносимые на защиту

1. Метод нахождения наибольшего решения в наибольшем алфавите для многокомпонентного автоматного уравнения. Такое наибольшее решение содержит все оптимальные решения как специальные редукции; в частности, наибольшее решение в заданном алфавите (если такое решение существует) может быть получено как специальная редукция наибольшего решения в наибольшем алфавите.

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

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

Достоверность результатов

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

Практическая значимость работы

Предложенные в работе методы могут быть использованы на этапе логического проектирования для синтеза и оптимизации многокомпонентных дискретных систем. В частности, метод, основанный на использовании безразличных последовательностей, был опробован на контрольных примерах из сети Интернет (benchmarks). Результаты показали, что число не определенных переходов в соответствующем частичном автомате для оптимизируемой компоненты Л'может достигать 80% от числа возможных переходов, и, соответственно, использование автоматных безразличных последовательностей в ряде случаев приводит к более эффективной реализации компоненты по числу вентилей.

Реализация полученных результатов

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

Проект УР.04.01.018 «Алгебра автоматов и полуавтоматов: отношения, операции, решения уравнений и неравенств» по программе «Университеты России», 2002-2003 гг.

Грант конкурса исследовательских проектов в области автоматизации проектирования интегральных схем компании INTEL, НИР «Оптимизация цифровых схем на основе решения автоматных уравнений», 2003 г.

НИР «Оптимизация декомпозиций конечных автоматов на основе решения автоматных уравнений» по гранту №А04-2.8-730 для поддержки научно-исследовательской работы аспирантов государственных образовательных учреждений высшего профессионального образования, находящихся в ведении Федерального агентства по образованию, 2004 г.

НИР «Синтез цифровых узлов схем управления многофазными инверторами» по заказу НПО «Полюс» в рамках Студенческого научно-исследовательского инкубатора по программе Международной организации IREX (International Research & Exchanges Board), 2004-2005 гг.

Совместный российско-тайваньский проект «Оптимизация цифровых схем посредством решения автоматных уравнений» по гранту РФФИ-NSC 06-08-89500, 2006-2008 гг.

НИР «Оптимизация цифровых схем посредством решения уравнений для структурных автоматов» по гранту РФФИ 07-08-12243, 2007-2008 гг.

Апробация работы

Научные результаты, составившие основу данной работы, обсуждались на заседаниях объединенного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ, кафедры программирования и кафедры защиты информации и криптографии "факультета прикладной математики и кибернетики ТГУ.

Результаты работы докладывались на Международных конференциях: «Euromicro symposium on digital system design» (Турция, 2003; Франция,

2004); «Дискретные модели в теории управляющих систем» (Москва, 2004); «East-west design and test workshop» (Сочи, 2006); «Синтез и сложность управляющих систем» (Новосибирск, 2004); Всероссийской конференции с международным участием «Новые информационные технологии в исследовании сложных структур» (Томск, 2000, 2002; Иркутск 2004); Сибирской научной школе-семинаре «Проблемы компьютерной безопасности и криптография» (Томск, 2003, 2005).

По результатам проведенных исследований опубликовано 9 статьей в научных журналах [27-35], а также 16 докладов и тезисов докладов на конференциях различного уровня [36 - 51].

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения и списка литературы из 93 наименований; изложена на 145 страницах текста, набранного в редакторе MS Word (шрифт - Times New Roman, размер шрифта - 14 pt, междустрочный интервал - 1,5 строки), включая 72 рисунка, 5 таблиц.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Тихомирова, Светлана Владимировна

4.5 Основные результаты главы

В данной главе исследуются прогрессивные решения автоматных уравнений и систем автоматных уравнений, которые гарантируют отсутствие тупиковых ситуаций при синтезе и оптимизации автоматных сетей с обратными связями, то есть на любую внешнюю входную последовательность сеть вырабатывает внешнюю выходную последовательность. Известно, любое муровское решение является прогрессивным. Однако не каждое прогрессивное решение является автоматом Мура. Для построения прогрессивного решения используется специальный автомат, называемый совершенным. Показано, как для любого решения уравнения можно построить эквивалентный совершенный автомат такой, что наибольшая прогрессивная редукция решения (если существует), является его подавтоматом, и предложен алгоритм построения наибольшей прогрессивной редукции. В общем случае наибольшее прогрессивное решение содержит полностью определенные редукции, которые не являются решениями уравнения. Кроме того, удалив, любую последовательность из наибольшего прогрессивного решения, можно потерять некоторые прогрессивные • решения. Поэтому все полностью определенные прогрессивные решения уравнения нельзя характеризовать в терминах редукций. Для полной характеризации прогрессивных решений каждому-состоянию наибольшего прогрессивного решения приписана система подмножеств пар «вход-выход» и сформулированы необходимые и достаточные условия того, что полностью определенная редукция наибольшего прогрессивного решения является прогрессивным решением. Поскольку в некоторых случаях при оптимизации компонент автоматной сети возникает необходимость решения системы автоматных уравнений, предложенный алгоритм нахождения наибольшего прогрессивного решения одного уравнения распространен на систему автоматных уравнений. Наибольшее решение системы уравнений находится как пересечение наибольших решений всех уравнений. Показано, что любой подавтомат совершенного автомата является совершенным, и пересечение совершенного автомата с любым автоматом, определенным в тех же входо-выходных алфавитах, сохраняет свойство совершенности-. На основе данных свойств предложен алгоритм нахождения наибольшего прогрессивного решения для системы автоматных уравнений, то есть решения, которое является прогрессивным для каждого уравнения системы.

ЗАКЛЮЧЕНИЕ

Диссертация посвящена разработке методов оптимизации многокомпонентных дискретных систем на основе решения автоматных уравнений. Введено понятие автоматного уравнения для автоматной сети с произвольной структурой и произвольным числом компонент. Показано, что операция синхронной композиции является ассоциативной, что позволяет свести многокомпонентное автоматное уравнение к бинарному автоматному уравнению и использовать известные методы решения. Поскольку разрешимость автоматного уравнения существенно зависит от выбора1 алфавитов решения, то показано, что существует в некотором смысле наибольший алфавит. Если уравнение не разрешимо в этом алфавите, то оно не разрешимо и в любом другом алфавите. Оптимальное решение в заданных алфавитах может быть найдено как специальная редукция наибольшего решения в наибольшем алфавите. Существующие методы нахождения наибольшего решения автоматного уравнения имеют экспоненциальную сложность, что затрудняет их применение для оптимизации многокомпонентных автоматных сетей. Поэтому предложены алгоритмы полиномиальной сложности для построения части наибольшего решения автоматного уравнения. В частности, предложены достаточные условия существования комбинационного решения автоматного уравнения, а также алгоритм оптимизации компоненты на основе безразличных входных последовательностей распространен на сети с обратными связями. Для снижения сложности оптимизации многокомпонентных автоматных сетей предложено- от глобальной оптимизации перейти к локальной, то есть рассматривать не всю сеть, а только фрагмент, содержащий оптимизируемую компоненту и непосредственно связанные с ней компоненты. При локальном подходе задача оптимизации сводится к решению множества и/или системы автоматных уравнений. Как показали эксперименты, при локальном подходе остается достаточно возможностей для оптимизации, что в ряде случаев приводит к более эффективной реализации компоненты по числу используемых вентилей. В качестве критериев оптимизации рассмотрены число связей в автоматной сети, отказоустойчивость компоненты и число вентилей в логической реализации. Показано, что задача минимизации связей в автоматной сети сводится к задаче поиска специальной редукции наибольшего решения автоматного уравнения, которая существенно зависит от меньшего числа входных переменных, и предложен алгоритм построения такой редукции (если существует). Предложен новый алгоритм нахождения наибольшего прогрессивного решения автоматного уравнения. Прогрессивные решения наиболее интересны с практической точки зрения, так как гарантируют отсутствие тупиков в оптимизируемой сети. Сформулированы необходимые и достаточные условия того, что полностью определенная редукция наибольшего прогрессивного решения является прогрессивным решением. Так как в зависимости от топологии автоматной сети в некоторых случаях задача оптимизации сводится к решению системы автоматных уравнений, то предложенный метод нахождения наибольшего прогрессивного решения 1 одного уравнения распространен на систему уравнений.

Список литературы диссертационного исследования кандидат технических наук Тихомирова, Светлана Владимировна, 2008 год

1. Глушков В.М. Синтез цифровых автоматов / В.М. Глушков. -М.: Физматгиз, 1962.-476 с.

2. Скобцов Ю.А. Логическое моделирование и тестирование цифровых устройств / Ю.А. Скобцов, В.Ю. Скобцов. Донецк: ИПММ НАН Украины, ДонНТУ, 2005. - 436 с.

3. Закревский А. Д. Алгоритмы синтеза дискретных автоматов / А.Д. Закревский. М.: Гл. ред. физ.-мат. лит., 1971. - 416 с.

4. Колдуэлл С. Логический синтез релейных устройств / С. Колдуэлл. — М.: ИЛ, 1962.-740 с.

5. Лазарев В.Г. Синтез управляющих автоматов / В.Г. Лазарев, Е.И. Пийль. М.: Энергия, 1970. - 400 с.

6. Закревский А.Д. Логический синтез каскадных схем / А.Д. Закревский. -М.: Наука, 1981.-416 с.

7. Автоматизированное проектирование цифровых устройств / С.С. Бадулин и др.. М.: Радио и связь, 1981. - 240 с.

8. Киносита К. Логическое проектирование СБИС / К. Киносита, К. Асада, О. Карацу. М.: Мир, 1988. - 309 с.

9. Черемесинова Л.Д. Синтез и оптимизация комбинационных структур СБИС / Л.Д. Черемесинова. Минск: ОИПИ НАН Беларуси, 2005. -241 с.

10. Gao M. The optimization of multi-valued multi-level networks / M. Gao, J-H. Jiang, Y. Jiang, Y. Li, A. Mishchenko, S. Sinha, T. Villa, R. Brayton // Proceedings of the 32nd IEEE ISMVL. 2002. - P. 168-177.

11. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации / А.А. Шалыто. СПб.: Наука, 2000. - 780 с.

12. Grasselli A. A method for minimizing the number of internal states in incompletly specified sequential networks / A. Grasselli, F. Luccio // IEEE Transactions on electronic computers. 1965. - Volume EC-14. - №3. -P. 350-359.

13. Devadas S. Approaches to multi-level sequential logic synthesis // Proceedings of the 26th design automaton conference. USA, 1989. -P. 270-276.

14. PaulinP.G. Algorithms for high-level synthesis / P.G. Paulin, J.P. Knight // IEEE design & test. 1989. - Volume 6. - Issue 6 - P. 18-31.

15. Jozwiak L. An efficient method for the decomposition of sequential machines / L. Jozwiak, J. Kolsteren // Microprocessing and microprogramming. 1991. -Vol. 32.-P. 657-664.

16. Yang W.-L. Multi-way FSM decomposition based on interconnect complexity / W.-L. Yang, R.M. Owens, M.J. Irwin // Proceedings of the design automation conference. 1993. - P. 390-395.

17. Baumgartner J. Min-area retiming on flexible circuit structures / J. Baumgartner, A. Kuehlmann // Proceedings of the ICCAD. 2001. -P. 176-182.

18. Jiang J.-H. Retiming and resynthesis: A complexity perspective / J.-H. Jiang, R. Brayton // IEEE TCAD. 2006. - Volume 25 (12). - P. 2674-2686.

19. Petrenko A. Nondeterministic state machines in protocol conformance testing / A. Petrenko, N. Yevtushenko, A. Lebedev, A. Das // Proceedings of the IFIP 6th IWPTS. France, 1993. - P. 363-378.

20. Watanabe Y. The maximum set of permissible behaviors for FSM networks / Y. Watanabe, R.K. Brayton // Proceedings of the 1993 IEEE/ACM international conference on computer-aided design. USA, 1993. - P. 316320.

21. Petrenko A. Testing strategies for communicating finite state machines / A. Petrenko, N. Yevtushenko, R. Dssouli // Proceedings of the International-workshop on protocol test systems. Tokyo, Japan, 1994. Chapman & Hall, 1995.-P. 193-208.

22. Решение уравнений в логическом синтезе / Н. Евтушенко и др.. -Томск: Изд-во "Спектр", 1999. 27 с.

23. Жарикова (Тихомирова) С. Оптимизация элементов цифровых схем посредством решения систем автоматных уравнений // Вестник ТГУ. Приложение. 2002. - № 1 (Ц). - С. 255-259.

24. Жарикова (Тихомирова) С. К синтезу отказоустойчивых элементов цифровых схем // Вестник ТГУ. Приложение. 2003. - № 6. - С. 114— 118.

25. Вилла Т. Характеризация живых решений синхронного- автоматного уравнения / Т. Вилла, Н. Евтушенко, С. Жарикова (Тихомирова) // Вестник ТГУ. Сентябрь 2003. - № 278. - С. 129-133.

26. Жарикова (Тихомирова) С. Решение автоматных уравнений в различных приложениях / С. Жарикова, Н. Евтушенко // Вестник КрасГУ. Физико-математические науки. 2004. -№3. - С. 35-39.

27. Жарикова (Тихомирова) С. Автоматные уравнения и минимизация связей в автоматных сетях // Вестник ТГУ. Приложение: — 2004. -№ 9 (I). С. 209-213.

28. Жарикова (Тихомирова) С.В. Оптимизация бинарной композиции автоматов // Вестник ТГУ. Приложение. 2005. - № 14. - С. 222-225.

29. Ветрова М.В. Исследование отношений совместимости между недетерминированными автоматами / М.В. Ветрова, Н.В. Евтушенко, С.В. Жарикова (Тихомирова), Н.В. Спицына // Вестник КрасГУ. Физико-математические науки. 2006. - № 4. - С. 20-27.

30. Жарикова-(Тихомирова) С.В. Метод нахождения прогрессивного решения системы автоматных уравнений // Вестник ТГУ. Приложение. -2006.-№17.-С. 20-24.

31. Жарикова (Тихомирова) С.В. Решение автоматного уравнения для многомодульной композиции / С.В. Жарикова, Н.В. Евтушенко // Вестник ТГУ. Приложение. 2007. - № 23. - С. 62^65.

32. Жарикова (Тихомирова) С. Решение автоматных уравнений в различных приложениях / С. Жарикова // Тезисы докладов региональной научной конференции студентов, аспирантов, молодых ученых «Наука. Техника. Инновации». Новосибирск, 2001. - С. 6-7.

33. Yevtushenko N. Multi component digital circuit optimization by solving FSM equations / N. Yevtushenko, S. Zharikova (Tikhomirova), M. Vetrova // Proceedings of the Euromicro symposium on digital system design. Turkey,2003. P. 62-68.

34. Zharikova (Tikhomirova) S. Minimization of communication wires by FSM equations solving / S. Zharikova, N. Yevtushenko // Proceedings of the work in progress session, Euromicro symposium on digital system design. France,2004.

35. Евтушенко Н.В. Достаточные условия существования комбинационного решения автоматного уравнения / Н.В. Евтушенко, С.В. Жарикова (Тихомирова) // Труды VI Международной конференции «Дискретные модели в теории управляющих систем». М., 2004. — С. 100-103.

36. Жарикова (Тихомирова) С.В. К оптимальной реализации цифровых схем // Сборник тезисов 11-й Всероссийской научной конференции студентов-физиков и молодых ученых. Екатеринбург, 2005. - С. 461— 462.

37. Kolomeets A.V. Digital controller for multiphase inverters / A.V. Kolomeets, M.L. Gromov, S.V. Zharikova (Tikhomirova), D.D. Popov // Proceedings of IEEE east-west design & test workshop. Ukraine, 2005. - P. 165-168.

38. Zharikova (Tikhomirova) S.V. Minimization of Communication Wires in FSM Composition / S.V. Zharikova, N.V. Yevtushenko // Proceedings of IEEE east-west design & test workshop. -Sochi, 2006. P. 397-402.

39. Дорофеева М.Ю. Декомпозиция цифровых схем для оптимизации на основе безразличных последовательностей / М.Ю. Дорофеева, С.В. Жарикова (Тихомирова) // Материалы V Всесибирского конгресса женщин-математиков. Красноярск: РИО СФУ, 2008. - С. 136-139.

40. Мур Э.Ф. Умозрительные эксперименты с последовательными машинами / Э.Ф. Мур . М.: Изд-во иностр. лит., 1956. - С. 179-210.

41. Гилл А. Введение в теорию конечных автоматов / А. Гилл. М.: Изд-во «Наука», 1966. - 272 с.

42. Трахтенброт Б.А. Конечные автоматы: поведение и синтез / Б.А. Трахтенброт, Я.М. Барздинь. М.: Наука, 1970. - 400 с.

43. Агибалов Г.П; Лекции по теории конечных автоматов: учеб. пособие / Г.П. Агибалов, A.M. Оранов. Томск: Изд-во Томского Университета, 1984.- 184 с.

44. Hartmanis J. The algebraic structure theory of sequential machines / J. Hartmanis and R.E. Stearns. N.Y.: Prentice-Hall Inc. Englewood Cliffs, 1966.-210 p.

45. Kim J. The simplification of sequential machines with input restrictions / J. Kim and M.M. Newborn // IRE transactions on electronic computers. -1972.-P. 1440-1443.

46. Hassoun S. Optimization of synchronous circuits / S. Hassoun, T. Villa // Logic synthesis and verification. 2001. - P. 225-253.

47. West C.H. An automated technique of communication protocols validation // IEEE transactions on communications. 1978. - Volume 26. - P. 1271-1275.

48. BochmannG.v. Formal methods in communication protocol design /• G.v. Bochmann, C.A. Sunshine // IEEE transactions on communications. -1980. Volume 28. - P. 624-631. >.

49. Merlin P. On the construction of submodule specification and Communication protocols / P. Merlin, G.v. Bochmann // ACM transactions on programming languages and systems. 1983. - Volume 5. - Issue 1. -P. 1-25.

50. Kumar R. A discrete event systems approach for protocol conversion / R. Kumar, S. Nelvagal, S.I.Marcus // Discrete event dynamic systems: Theory & applications. 1997. - Volume 7 (3). - P. 295-315.

51. MangF. Games in open systems: Verification and synthesis: Ph.D. thesis / F. Mang. England, 1995. - 129 p.

52. Yevtushenko N. Synthesis by language equation solving: extended abstract / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Proceedings of annual Intern, workshop on logic synthesis. -2000.-P. 11-14.

53. Brand D. On communicating finite state machines / D. Brand, P. Zafiropulo I I J. ACM. 1983. - Volume 30 (2). - P. 323-342.

54. Агибалов Г.П. Декомпозиция конечных автоматов / Г.П. Агибалов, Н.В. Евтушенко. Томск: Изд-во Томского Университета, 1985. — 128 с.

55. Synthesis of finite state machines: Functional optimization / Kam T. and et.al.. Kluwer academic publishers, 1997. - 296 p.

56. WonhamW.M. Supervision of DES Электронный ресурс. / W.M. Wonham. Электрон, дан. - Торонто, 1999 - Режим доступа: http://www.control.utoronto.ca/DES, свободный.

57. Евтушенко Н.В. Об одном подходе к синтезу проверяющих последовательностей для автоматных сетей / Н.В. Евтушенко, А.Ю. Матросова // АВТ. 1991. - №2. - С. 3-7.

58. Лялин И.В. О решении автоматных уравнений / И.В. Лялин // Дискретная математика. 2004 - Т. 16, вып. 2. - С. 1-21

59. Yevtushenko N. Solution of synchronous language equations for logic synthesis / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Вестник ТГУ. Приложение. 2002. -№ 1 (II).-С. 132-138.

60. Yevtushenko N. Compositionally progressive solutions of synchronous language equations / N. Yevtushenko, T. Villa., R.K. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Proceedings of the IWLS. 2003. - P. 148155.

61. Rho J. Don't care sequences and the optimization of interacting finite state machines / J. Rho, G. Hatchel, F. Somenzi // Proceedings of the International conference on computer-aided design. 1991. - P. 418-421.

62. Спицына Н.В. Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов: дис. . канд. техн. наук / Н.В. Спицына; Томский государственный ун-т. Томск, 2004. -160 с.

63. Gill A. Introduction to the theory of finite state machines / A. Gill. New York: McGraw-Hill, 1962.

64. El-Fakih Kh. Progressive solutions to a parallel automata equation / Kh. El-Fakih, N. Yevtushenko, S. Buffalov, G.v. Bochmann // Theoretical computer science. 2006. - Volume 362. - Issues 1-3. - P. 17-32.

65. Евтушенко H.B. Недетерминированные автоматы: анализ и синтез. Ч. 1. Отношения и операции: учебное пособие / Н.В. Евтушенко, А.Ф. Петренко, М.В. Ветрова. Томск: Томский государственный университет, 2006. - 142 с.

66. Starke Р.Н. Abstract Automata / Р.Н. Starke. N.Y.: American Elsevier publishing company, 1972. - 419 p.

67. Hopcroft J.E. Introduction to automata theory, languages and computation / J.E. Hopcroft, J.D. Ulman. Addison-Wesley publishing company, 1979. -418 p.

68. Khatri S. Engineering change in a non-deterministic FSM setting / S. Khatri, A. Narayan, S.C. Krishnan, K.L. McMillan, R.K. Brayton, A. Sangiovanni-Vincentelli // Proceedings of the IEEE/ACM'design automation conference. -USA, 1996.-P. 451-456.

69. Лукьянов Б.Д. Детерминированные реализации недетерминированных автоматов // Кибернетика и системный анализ. 1996. - № 6. - С. 34-50.

70. Ветрова М.В. Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов: дис. . канд. техн. наук / М.В. Ветрова; Томский государственный ун-т. Томск, 2004. - 150 с.

71. Каравай М.Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // АиТ. 1996. - №6. - С. 159-173.

72. Cohen P.R. Trial by fire: understanding the design requirements for agents in complex environments / P.R. Cohen, M.L. Greenberg, D.M. Hart, A.E. Howe // AI Magazine. 1989. - Volume 10. - Issue 3. - P. 34-48.

73. Corno F. RT-level ITC99 benchmarking and first ATGP results / F. Corno, M. Sonza Reorda, G. Squillero // IEEE design & test. Special issue on benchmarking for design and test. 2000. - P. 44-53.

74. Закревский А.Д. Основы логического проектирования. Оптимизация в булевом пространстве. Кн. 2. / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. Минск: ОИПИ НАН Беларуси, 2004. - 240 с.

75. Benchmarks Электронный ресурс. Электрон, дан. - Режим доступа: http://wwwxbl.ncsu.edu/benchmarks/LGSynth93/testcases/fsm/, свободный.

76. Павлов В.Л. Синтез комбинационных схем в произвольном базисе // Алгоритмы решения задач дискретной математики. 1987. - Вып. 2. -С. 53-58.

77. Синтез асинхронных автоматов на ЭВМ / под общ. ред. А.Д. Закревского. Минск: Наука и техника, 1975. — 184 с.

78. BraytonR.K. The decomposition and factorization of Boolean expressions / R.K. Brayton, C. McMullen // Proceedings of the ISCAS. 1982. - P. 29-54.

79. MishchenkoA. SAT-based complete don't-care computation for network optimization / A. Mishchenko, R. Brayton // Design, automation and test in Europe. 2005. - Volume 1. - P. 412-417.

80. Yevtushenko N. Compositionally progressive solutions of synchronous FSM equations / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Journal of discrete event dynamic systems. -2007.