автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов

ВВЕДЕНИЕ.

1. ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ, ОБЗОР ЛИТЕРАТУРЫ.

1.1. Устройства управления техническими объектами.

1.1.1. Синтез цифровых устройств управления.

1.1.2. Контроллеры.

1.1.3. Корректировка алгоритма управления.

1.2. Основные определения и обозначения.

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

1.2.2. Отношения между автоматами.

1.2.3. Полностью определенные формы автомата.

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

1.2.5. Пример конечно-автоматного компенсатора.

1.2.6. Синтез компенсаторов и автоматные уравнения.

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

1.3.1. Алгоритм нахождения наибольшего решения автоматного уравнения.

1.3.2. Алгоритм решения автоматного уравнения на основе отношения моделирования.

1.3.3. Сложность решения автоматного уравнения для топологии контроллера. щ 1.3.4. Синтез оптимальных компенсаторов.

1.3.5. Синтез тестов для конечно-автоматных компенсаторов.

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

2. СИНТЕЗ ОПТИМАЛЬНОГО КОМПЕНСАТОРА ДЛЯ АБСТРАКТНЫХ АВТОМАТОВ.

2.1. Эквивалентность разрешимости уравнений для топологии контроллера и последовательной топологии.

2.2. Синтез наибольшего решения для полностью определенных детерминированных автоматов.

2.3. Синтез наибольшего согласованного конечно-автоматного

• компенсатора.

2.4. Минимальные детерминированные редукции недетерминированных автоматов.

2.4.1. Редукции и подавтоматы.

2.4.2. г-несовместимые состояния.

2.4.3. Сохраняемое покрытие автомата.

2.4.4. Достаточное условие эквивалентности минимальной редукции некоторому подавтомату исходного автомата.

2.4.5. Алгоритм построения редукции недетерминированного автомата с наименьшим числом состояний, эквивалентной подавтомату.

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

3. СИНТЕЗ ОПТИМАЛЬНОГО КОМПЕНСАТОРА ДЛЯ ПОСЛЕДОВАТЕЛЬНОЙ КОМПОЗИЦИИ АВТОМАТОВ.

3.1. Синтез компенсатора для последовательной композиции абстрактных автоматов.

3.2. Синтез компенсаторов для микропрограммных автоматов.

3.2.1. Микропрограммные автоматы и композиции микропрограммных автоматов.

3.2.2. Наибольший микропрограммный компенсатор.

3.2.3. Оптимальный микропрограммный компенсатор.

3.2.4. Эксперименты по синтезу оптимальных компенсаторов для микропрограммных автоматов.

3.3. Синтез компенсатора для структурных автоматов.

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

3.3.2. Структурные автоматы и последовательная композиция структурных автоматов.

3.3.3. Решение уравнения для последовательной композиции автоматов с памятью.

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

4. СИНТЕЗ ТЕСТОВ ДЛЯ КОНЕЧНО-АВТОМАТНЫХ КОМПЕНСАТОРОВ

4.1. Синтез проверяющих тестов при безусловном эксперименте с проверяемым автоматом.

4.1.1. Отличающий автомат.

4.1.2. Описание отличающего автомата.

4.1.3. Построение проверяющего теста.

4.1.4. Сокращение длины проверяющего теста.

4.2. Результаты экспериментов.

4.3. Метод тестирования на основе условного эксперимента с проверяемым автоматом.

4.4. Сокращение функции неисправности.

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

Общая характеристика работы

Актуальность проблемы. Из всех этапов проектирования дискретных систем алгоритмическое и логическое проектирование управляющих систем наиболее

• трудно поддаются автоматизации вследствие их сложности. В последнее 50-летие САПР систем логического управления на основе различных формальных спецификаций были разработаны представителями школ Гаврилова М.А., Глушкова В.М., Закревского А.Д., Агибалова ГЛ., Чистова В.П., Брайтона Р., Санджиованни-Винчентелли А. и других [1-13]. Большие возможности для реализации систем управления открыли достижения микроэлектроники. Современные устройства управления технологическими процессами (контроллеры) обычно реализуются на базе микропроцессорной техники, или по принципу жесткой логики, т.е. на базе микроэлектронных ИС разной степени интеграции [14-17].

В последнее время появился ряд работ [18-25], направленных на возможность использования ранее созданных устройств управления с добавкой специального «корректирующего автомата». Такая ситуация часто возникает при модернизации устаревших устройств управления. В ряде случаев достаточно синтезировать подходящий «корректирующий автомат», компенсатор, таким образом, чтобы его совместное поведение со старым устройством управления удовлетворяло необходимым требованиям, т.е. можно говорить о синтезе управляющего автомата путем специальной декомпозиции, одна из компонент которой известна. Соответствующая декомпозиция может быть получена на основе решения автоматного уравнения. Однако, решения, предлагаемые в работах [18-20], не содержат описания всех возможных альтернатив, удовлетворяющих заданным требованиям, что, в частности, не позволяет строить оптимальные в различных смыслах компенсаторы, а соответственно и управляющие, автоматы. Кроме того, решения предлагаются только для абстрактных полностью определенных автоматов, в то время как для описания поведения реальных устройств управления используются микропрограммные и структурные автоматы. Данная работа продолжает исследования в этом направлении и посвящена разработке алгоритмов синтеза и тестирования оптимальных конечно-автоматных компенсаторов.

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

Научная новизна. Предложены два подхода к полному описанию множества конечно-автоматных компенсаторов для специальной топологии автоматной сети, называемой топологией контроллера [21]. Во-первых, показано, что если поведение старого устройства управления, известной компоненты декомпозиции, описано детерминированным автоматом, то корректирующий автомат, компенсатор, можно выбрать таким, чтобы его поведение не зависело от выхода управляющего автомата. Иными словами, автомат-компенсатор можно синтезировать для композиции без обратной связи. Однако в этом случае компенсатор может оказаться более сложным. Поэтому для топологии контроллера предложен метод построения недетерминированного автомата, редукции которого и только они могут быть выбраны в качестве корректирующего автомата. Предложенный метод адаптирован для случая, когда поведение известной компоненты описывается частичным автоматом. В этом случае компенсатор должен быть согласован с корректируемым автоматом, т.е. его выходные последовательности должны быть допустимыми для корректируемого устройства. Технология декомпозиции управляющих автоматов адаптирована на случай микропрограммных и структурных автоматов.

Под оптимальным компенсатором в работе понимается автомат-компенсатор с минимальным числом состояний. Как известно [26-27], построение такого автомата-компенсатора связано с нахождением минимальной детерминированной редукции недетерминированного автомата. Предложены достаточные условия, при которых такая редукция эквивалентна подавтомату исходного автомата, и предложен алгоритм нахождения минимальной редукции в этом случае.

Предложен метод синтеза проверяющего теста для недетерминированного автомата, основанный на условном эксперименте с детерминированной реализацией. Предложенный метод может быть использован для синтеза тестов для конечно-автоматных компенсаторов. Достоверность результатов. Все научные положения и выводы, содержащиеся в диссертации, основаны на утверждениях, доказанных с использованием аппарата общей алгебры и теории конечных автоматов. Практическая ценность работы. Методы, разработанные в диссертации, могут использоваться в системах логического синтеза дискретных управляющих систем, в том числе для их оптимизации и диагностики. Реализация полученных результатов. Исследования, результаты которых изложены в настоящей диссертации, проводились в рамках следующих грантов и научно-исследовательских проектов.

Грант РФФИ 99-01-00337 "Решение автоматных уравнений и неравенств".

Программа МО РФ 2000 г. "Научные исследования высшей школы в области производственных технологий", раздел "Интеллектуальные системы автоматизированного проектирования и управления производством", НИР "Разработка интеллектуальной системы автоматизированного проектирования и тестирования цифровых контроллеров".

Обменный Грант НАТО PST.CLG 979698 «Logic synthesis and analysis through automata and FSM equation solving» совместно с университетом Беркли США (Научная группа проф. Р. Брайтона).

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

Результаты проведенных исследований включены в курс лекций по теории автоматов, которые читаются на радиофизическом факультете ТГУ. Апробация работы. Результаты, вошедшие в работу, обсуждались на заседаниях совместного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ, кафедр программирования и защиты информации и криптографии факультета прикладной математики и кибернетики ТГУ. Кроме того, они докладывались на конференциях, в том числе международных, в Новосибирске, Воронеже, Иркутске, Саратове, Белеке (Турция) и Томске.

Публикации. По теме диссертации опубликовано 10 печатных научных работ, из них 2 статьи в журнале «Вестник ТГУ», 2 рецензируемых доклада и 6 тезисов докладов в трудах Российских и международных конференций. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка цитированной литературы. Объем диссертации составляет . страниц текста, набранного в редакторе MS Word 97 (Шрифт -Times New Roman Cyr, размер шрифта - 14 pt, межстрочный интервал — 1,5 строки), в том числе: титульный лист - 1с., оглавление - 2с., основной текст, включающий 34 рисунка, - 124с., библиографический список из 109 наименований - 1 Ос. Основное содержание работы

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

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

Заключение

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

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

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

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

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

На защиту выносятся следующие положения:

1. Эквивалентность разрешимости автоматного уравнения для топологии контроллера и последовательной композиции, которая позволяет свести задачу синтеза конечно-автоматного компенсатора к синтезу компенсатора для последовательной композиции.

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

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

4. Метод синтеза условных проверяющих тестов относительно редукции для недетерминированных автоматов при детерминированной реализации.

1. Глушков В.М. Синтез цифровых автоматов. Изд-во "Физ.-мат. Лит-ры".-М.-1962.-476с.

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

3. Баранов С.И., Килленберг X. Декомпозиция микропрограммных автоматов // АиВТ.- №6.- 1978.- С.5-11.

4. Закревский А.Д. Алгоритмический язык ЛЯПАС и автоматизация синтеза дискретных автоматов. — Изд-во Томского университета.- Томск.- 1966.

5. Гаврилов М.А. Автоматизация проектирования.- Вестн. АН СССР.- №12.1976.- С.90-97.

6. Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов,- М.: "Наука".- 1977.- 352с.

7. Гаврилов М.А. Современное состояние и проблемы автоматизации проектирования // Труды VII Всесоюзного совещания по проблемам управления.- М.- Ин-т пробл. управл.- кн.2.- 1977.- С.6-9.

8. Лазарев В.Г., Пийль Е.И. Синтез асинхронных конечных автоматов.- Изд-во "Наука".- М.- 1964.

9. Поспелов Д.А. Логические методы анализа и синтеза схем.- Изд-во "Энергия".- М.-Л.- 1964.

10. Ю.Скляров В.А., Новиков C.B., Ярмолик В.Н. Автоматизация проектирования ЭВМ // Учебное пособие для вузов.- Мн.- Высш.шк.- 1990.- 356с.

11. T.Karn, T.Villa, R.Brayton, A. Sangiovanni-Vincentelli. Synthesis of finite state machines: functional optimization. Kluwer Academic Publishers, 1997. 283 p.

12. Huffman D.A. The synthesis of sequential switching circuits // Journal of the Franklin Inst.- v.257.- №3 and №4.- 1954.- P.161-190, 275-303.

13. М.Гусев С. Современные технологии автоматизации. Краткий курс в историю промышленных сетей. №4. - 2000. - С. 78-84.

14. Современные микроконтроллеры. Архитектура, средства проектирования, примеры применения, ресурсы сети Интернет. М: АКИМ. — 1998. — 250с.

15. Любашин А. Н. Краткий обзор промышленных сетей по материалам конференции "Field Comms'95", АО РТСофт.

16. Коваленко В. Современные индустриальные системы. ИПН РАН, Москва, 1997.

17. Григорян А. К. Метод декомпозиции конечных автоматов // Автоматика и телемеханика, 1968. №5. - С. 101-109

18. Григорян А. К. Метод декомпозиции конечных автоматов с выделением выходного и входного автоматов // Автоматика и телемеханика, 1968. -№10-11.-С. 113-118.

19. Амбарцумян А. А., Григорян А. К. Эквивалентные преобразования управляющих автоматов, генерируемых по описанию поведения объектов управления // Автоматика и телемеханика, 1978. -№12. С. 130-138.

20. DiBenedetto М. D., Saldanha A., and Sangiovanni-Vincentelli A. Strong Model Matching for Finite State Machines with Nondeterministic Reference model // Proc. of 34rd Conf. Decision and Control (New Orleans, LA, USA), December 1994, pp. 422-426.

21. DiBenedetto M. D., Saldanha A., and Sangiovanni-Vincentelli A. Model Matching for Finite State Machines // Cadence Berkeley Laboratories Technical Report, 1996.

22. DiBenedetto M. D., Saldanha A., and Sangiovanni-Vincentelli A. Model Matching for Finite State Machines // Cadence Berkeley Laboratories Technical Report, 1999.

23. DiBenedetto M. D., Saldanha A., and Sangiovanni-Vincentelli A. Model Matching for Finite State Machines // Proc. of 33rd Conf. Decision and Control (Lake Buena Vista, FL, USA), December 1994, pp. 3117-3124.

24. DiBenedetto M. D., Saldanha A., and Sangiovanni-Vincentelli A. Strong Model Matching for Finite State Machines // Proc. of 3rd Europian Control Conference (Rome, Italy), September 1995, pp. 2027-2034.

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

26. А. Petrenko, N. Yevtushenko., G.v. Bochmann. Testing Deterministic1.plementations from Nondeterministic FSM Specifications. Proceedings ofit.

27. IP TC6 9 International Workshop on Testing of Communicating Systems, Germany, 1996, pp. 125-140.

28. Kurshan R.P., Merritt M., Orda A., and Sachs S.R. Modelling asynchrony with a synchronous model // Formal Methods in System Design.- v. 15.- №3.- 1999.-P.175-199.

29. Евтушенко H., Вилла Т., Петренко А., Брайтон P., Санджованни-Винцентелли А. Решение уравнений в логическом синтезе. Препринт. -Томск: Изд-во "Спектр" ИОА СО РАН, 1999. 27 с.

30. Евтушенко H.B., Лебедев A.B., Петренко А.Ф. О проверяющих экспериментах с недетерминированными автоматами // Автоматика и Вычислительная техника.-1991.- № 6.- С. 81-85

31. A.Petrenko, N. Yevtushenko, G.v.Bochmann. Experiments on nondeterministic systems for (with respect to) the reduction relation, Dept.Publ.\#932 of Universite de Monreal, 1991, 24 p.

32. A. Petrenko, N. Yevtushenko, G.v. Bochmann. Experiments on nondeterministic systems with respect to the reduction relation. University of Montreal, Dept. Publ. #932, 1994.

33. Лукьянов Б.Д. О различающих и контрольных экспериментах с недетерминированными автомата // Кибернетика и системный анализ, 1995, №5, с. 69-76.

34. S. Boroday. Distinguishing tests for nondeterministic finite state machines. -Testing of Communicating Systems. Proceedings of 11th International Workshop on Testing of Communicating Systems. Kluwer Academic Publishers, 1998. -pp. 101-107.

35. Куфарева И. Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов в системах логического проектирования. ТГУ, Томск, диссертационная работа, 2000.

36. Евтушенко Н. В., Лебедев А. В. О контрольном эксперименте с детерминированными реализациями и недетерминированным эталоном // Кибернетика и системный анализ, 1998. №1. - С. 57-65

37. M. Ghriga, P.G. Frankl. Adaptive testing of nondeterministic communication protocols // Proceedings of the IFIP 6th International Workshop on Protocol Test Systems, 1993.-pp. 349-363.

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

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

40. Гаврилов М.А. Развитие и современное состояние теории и техники дискретной телемеханики // Промышленная телемеханика.- М.- Изд-во АН СССР.- 1960.- С.5-33.

41. Гаврилов М.А. Новая система диспетчерского телеуправления.-Электричество.- №13.- 1934.- С. 17-22.

42. Гаврилов М.А. Устройство телеуправления и телесигнализации // Бюл. Мосэнерго.- №3.- 1935.- С. 18-24.

43. Гаврилов М.А. Диспетчерское управление в энергосистемах // Автоматика и телемеханика.- №5.- 1937.- С.53-68.

44. Гаврилов М.А. Дистанционное управление задвижками панелей подземной газификации углей // Автоматика и телемеханика.- №4.- 1939.- С.45-64.

45. Гаврилов М.А. Состояние и задачи телемеханизации управления производственными процессами // Автоматизация производственных процессов.- М.- Изд-во АН СССР.- гл.23.- 1956.- С.441-468.

46. Гаврилов М.А. Применение телемеханики в управлении энергитическими установками промышленных предприятий.- М.- Моск. дом науч. пропаганды.- 1957.- 32с.

47. Гаврилов М.А., Рогинский В.Н., Лазарев В.Г. и др. Теория релейных устройств.- М.- ИАТ.- 1965.- 72с.

48. Гаврилов М.А. Структурная теория релейных устройств. Синтез таблиц состояний.- М.- ВЗЭИ.- ч.4.- 1964.- 157с.

49. Гаврилов М.А. Теория релейно-контактных схем.- М.-Л.- Изд-во АН СССР.- 1950.-304с.

50. Гаврилов М.А. Современное состояние теории релейных устройств и конечных автоматов // Теория конечных и вероятностных автоматов.- М.-Наука.- 1965.- С.17-39.

51. Гаврилов М.А. Релейные устройства и конечные автоматы // Техническая кибернетика СССР.- М.- 1968.- С.157-178. (сер. "Советская наука и техника за 50 лет").

52. Гаврилов М.А. Теоретические проблемы практического приложения теории конечных автоматов // Труды международного семинара по прикладным аспектам теории автоматов.- Варна.- Инст-т техн.кибернетики БАН.- 1971.-С.5-34.

53. Гаврилов М.А. Теоретические проблемы применения теории конечных автоматов.- Probl. Control and Inform. Theory.- Hungary.- v.l.- 1972,- P.8-28.

54. Gavrilov M.A. Development of the finita automata theory in the discrete circuit design.- Probl. Control and Inform. Theory.- Hungary.- v.3.- 1975.- P.451-470.

55. Гаврилов М.А. Основные проблемы синтеза дискретных управляющих устройств // Информ. Материалы АН СССР.- М.- Наука.- 1968.- С.27-52.

56. Гаврилов М.А. Декомпозиция комбинационных автоматов // Математические структуры, вычислительная математика, математическое моделирование.- Труды, посвященные 60-летию акад. JI. Илиева.- Изд-во Болг. АН.- София.- 1975.- С.37-57.

57. Гаврилов М.А. Композиция и декомпозиция комбинационных автоматов // Теория автоматов.- М.- Наука.- 1976.- С.34-71.

58. Гаврилов М.А. Основные формулы синтеза цифровых автоматов.-ЖВМиМФ.- т. 1.- №3.- 1961.- С.371-441.

59. Муравьева Е.А. Разработка логических структур большой размерности с помощью расширенных булевых матриц // Автореферат диссертации.

60. Горбатов В.А. Теория частично-упорядоченных схем.- М.- Сов.радио.-1976.- 336с.

61. Баранов С.И. Синтез микропрограммных автоматов.- М.- Энергия.- 1974.

62. Гаврилов М.А. Минимизация булевых функций, характеризующих релейные цепи // Автоматика и телемеханика.- №9.- 1959.- С.1217-1237.

63. Шеннон К. Синтез двухполюсных переключательных схем // Работы по теории информации и кибернетике.- М.- ИЛ.- 1963.- С.59-105.

64. Ashenhurst R. The decomposition of switching functions // Ann. Comput. Lab. Harvard Univ.- v.29.- 1969.- P.74-116.

65. Поваров Г.Н. О функциональной разделимости булевых функций.- ДАН СССР.- т.94.- №5. 1954.- С.801-805.

66. Curtis Н. A new approach to the design of switching circuits. Princeton.- N.J.-D.Van Nostrand Co.- 1962.- 635p.

67. Питерсон Дж. Теория сетей Петри и моделирование системы.- М.- Мир.-1984.- 264с.

68. Kumar R. Holloway L.E. Supervisory Control of Petrinets with Regular Specification Languages // IEEE Transactions on Automatic Control.- v.41.-№2.- 1996.- P.245-249.

69. Achasova S., Bandman O., Markova V., Piskunov S. Parallel Substitution Algorithm. Theory and Application.- Singapore.- World Scientific.- 1994.- 240p.

70. Yevtushenko N., Villa Т., Brayton R., Petrenko A., Sangiovanni-Vincentelli A. Logic Synthesis by equation solving // Proceedings of XVI Intern. Workshop on Logic Synthesis.- USA.- 2000.- P. 11-14.

71. Braudt R.D., Garg V.K., Kumar R., Liu E., Marcus S.I., and Wonham W.M. Formulas for Calculating Supremal Controllable and Normal Sablanguages // Systems and Control Letters.- v. 15.- №3.- 1990.- P.l 11-117.

72. Wonham W.M., Ramadge P.J. On the Supremal Controllable Sublanguage of a Given Language // SIAM J. Control. Optim.- v.25.- №3.- 1987.- P.637-659.

73. M. Yannakakis, D. Lee. Testing finite state machines: fault detection // Journal of Computer and System Sciences, 1995, 50, pp. 209-227.

74. Евтушенко H. В., Петренко А. Ф. Синтез проверяющих экспериментов в некоторых классах автоматов // Автоматика и вычислительная техника. -1990.-№4.-С. 59-64.

75. Р.Н. Starke. Abstract Automata, North-Holland/American Elsevier, 1972, 419 p.

76. Peyman Gohari, Wonham W.M. On the Complexity of Supervisory Control Design in the RW Framework // IEEE Transactions on Systems.- Man and Cybernetics.- Special Issue on DES.- 2000.- (http:// odin.control.toronto.edu/gohari/np.ps.loader.shtml).

77. Unger S.H. Asynchronous Sequential switching circuits.- wiley interscience.

78. Тренькаев B.H. Разработка методов синтеза проверяющих тестов для сетей из конечных автоматов // Диссертация, представленная на соискание ученой степени кандидата технических наук.- Томск.- 2000.

79. Watanabe Y., Brayton R.K. The maximum set of permissible behaviors for FSMs network // Trans. Of IEEE / ACM Int. Conf. on Computer-aided design.-1993.- P.316-328.

80. Евтушенко H.B., Петренко А.Ф., Тренькаев B.H. Метод тестирования автоматных сетей, основанный на тестируемом поведении компоненты // АиВТ.-№2.- 1996.- С.48-59.

81. A. Petrenko, N.Yevtushenko, R.Dssouli. Testing strategies for communicating FSMs // Proc. of the IFIP 7th International Workshop Protocol Test Systems.-Japan.- 1994, P. 181-196.

82. Евтушенко Н.В., Куфарева И. Б. Отношения между недетерминированными автоматами. Томск: Изд-во "Спектр" ИОА СО РАН, 2001.-26с.

83. Hartmanis J., Stearns R. Algebraic structure theory of sequential machines. -Prentice-Hall, New York, 1966, 210 p.

84. Агибалов Г. П., Оранов А. М. Введение в теорию конечных автоматов

85. Василевский М.П. О распознавании неисправностей автомата // Кибернетика. 1973, № 4. - С. 93-108.96.3акревский А.Д. Комбинаторные методы оптимизации решений системы линейных логических уравнений // Вестник ТГУ.- №6.- 2003.- С.4-8.

86. Маракин В.В. Синтез диагностических тестов для конечных автоматов // Вестник ТГУ.- №6.- 2003.- С.178-182.

87. Ветрова М.В. Синтез контроллеров для микропрограммных автоматов // III Всероссийская конференция с международным участием "Новые информационные технологии в исследовании дискретных структур". 1214.09.2000. Томск. С. 194-199.

88. М.Ветрова, Н.Евтушенко, М.Косарева, И.Куфарева, В.Тренькаев, О.Штарнова Система автоматизированного проектирования и тестирования цифровых контроллеров. Воронеж, 2001.

89. Ветрова М.В. Синтез контроллеров для структурных автоматов // XL Международная научная студенческая конференция "Студент и научно-технический прогресс", 16-18.04.2002. Новосибирск.

90. Ветрова М.В. Синтез контроллеров для структурных автоматов // Компьютерные науки и информационные технологии. Тезисы докладов