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

• Буфалов, Сергей Анатольевич
• кандидат технических наук
• 2002

Оглавление диссертации кандидат технических наук Буфалов, Сергей Анатольевич

Введение

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.5.1 Живое решение.

1.2.5.2 Безопасное решение.

1.2.6 Обзор существующих подходов, к решению уравнений и неравенств на множестве полуавтоматов.

1.3 Конечные автоматы

1.3.1 Определения.

1.3.2 Взаимосвязь между полуавтоматами и автоматами.

1.3.3 Параллельная композиция автоматов.

1.3.4 Уравнения и неравенства на множестве автоматов.

1.3.5 Обзор существующих подходов к решению уравнений и неравенств на множестве автоматов.

1.4 Обзор задач, сводящихся к решению уравнений и неравенств

1.4.1 Логический синтез.

1.4.2 Диагностика компоненты автоматной сети.

1.4.3 Оптимизация компоненты автоматной сети.

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

2 Полуавтоматные уравнения и неравенства

2.1 Решение неравенства/АС

2.1.1 Множество решений неравенства.

2.1.2 Живые решения.

2.1.2.1 Живые решения, реализующие конечный язык.

2.1.2.2 Совершенный полуавтомат.

2.1.2.3 Отношение ^^-моделирования.

2.1.2.4 Харакгеризация редукций живого решения, являющихся живыми решениями.

2.1.2.5 Наибольшая редукция решения, являющаяся живым решением.

2.1.3 Безопасные решения.

2.1.4 Живые безопасные решения.

2.2 Результаты компьютерных экспериментов

2.2.1 Теоретические оценки сложности наибольшего и наибольшего живого решений.

2.2.2 Зависимость числа состояний решений от числа состояний в контексте и спецификации.

2.2.3 Зависимость числа состояний решений от мощности алфавитов.

2.3 Выводы по главе

3 автоматные уравнения и неравенства

3.1 Решение автоматного неравенства А0Х< С

3.1.1 Множество решений неравенства.

3.1.2 Живые решения.

3.1.3 Безопасные решения.

3.1.4 Живые безопасные решения.

3.2 Решение неравенства А 0Х< С для полностью определённых автоматов

3.2.1 Множество решений неравенства.

3.2.2 Живые решения.

3.2.3 Безопасные решения.

3.2.4 Живые безопасные решения.

3.3 Решение уравнения А0Х= С

3.4 Решение неравенства А0Х>С

3.5 Выводы по главе

Введение диссертации (часть автореферата) на тему «Исследование живых и безопасных решений параллельных уравнений и неравенств на множестве полуавтоматов и автоматов»

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

Актуальность проблемы. Сложные системы логического управления обычно реализуются сетью из взаимодействующих компонент [1 - 4]. Благодаря этому в теории дискретных систем решение ряда задач логического синтеза [3, 5 - 21], управления [4, 22 - 32] и оптимизации [10, 33] может быть сведено к решению уравнения А°Х&С. Здесь А и X описывают поведение, соответственно, известной и неизвестной компонент синтезируемой системы, - оператор композиции и - отношение (конформности), в котором должны находиться поведение синтезируемой системы и (эталонное) поведение реализуемой системы С (спецификации).

Подобным образом, например, формализуются задачи синтеза цифровых контроллеров [23] и покомпонентной оптимизации дискретных систем [34]. В первом случае А описывает поведение множества компонент, которыми контроллер должен управлять так, чтобы реализовать нужное поведение С. Поведение же самого контроллера описывается одним из решений уравнения А°Х&С. Если уравнение обладает хотя бы одним решением, то имеет смысл говорить о нахождении оптимального (например, в смысле числа состояний) решения, т.к. наибольший интерес представляют именно оптимальные реализации контроллера. Во втором случае предполагается, что все компоненты, кроме одной, реализованы оптимально, и А описывает их совместное поведение, а свободная переменная X соответствует компоненте, подлежащей оптимизации. Среди решений уравнения находится оптимальное (которое и подставляется вместо оптимизируемой компоненты), и процесс продолжается до тех пор, пока все компоненты не будут оптимизированы.

Следует заметить, что не всякое решение уравнения А°Х&С пригодно с точки зрения практики. Особый интерес представляют те решения, которые позволяют оптимизировать компоненту (синтезируемую посредством решения логического уравнения А°Х&С) в смысле её внутреннего взаимодействия с другими компонентами сети. К классу таких решений относятся рассматриваемые в работе живые и безопасные решения.

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

Методы решения, т.е. характеризации живых и безопасных решений, логического уравнения А °Х»С зависят от выбора математической модели поведения систем А, X и С, операции композиции и отношения конформности Известно, что для описания поведения дискретных систем управления часто используют конечные автоматы и полуавтоматы [35 - 41], а для описания их асинхронного (параллельного) функционирования - операцию параллельной композиции, соответственно, автоматов [13] "О" и полуавтоматов [9] "<W\ Здесь Ext - непустое множество действий, доступных в композиции для внешнего наблюдения. В качестве отношения конформности часто рассматриваются отношения эквивалентности и редукции ">" (или "<") [6, 7, 13]. Отношение эквивалентности позволяет описать ситуацию, когда поведение композиции совпадает с поведением реализуемой системы, и приводит к рассмотрению параллельных уравнений АОе^Х^С и AOXsC на множестве полуавтоматов и автомагов, соответственно. В свою очередь, отношение редукции позволяет описать ситуацию, когда поведение композиции должно содержаться в поведении реализуемой системы или, наоборот, содержать его. Благодаря этому становится возможным рассматривать параллельные неравенства A<>ExtX<С и A§EXtX>C на множестве полуавтоматов и параллельные неравенства А(>Х<С иА0Х>С - на множестве автоматов.

Таким образом, для решения ряда задач, возникающих при синтезе и оптимизации дискретных систем управления, актуальной является проблема разработки методов и алгоритмов нахождения оптимальных живых и безопасных решений (полу)автоматных уравнений и неравенств. Кроме того, данная проблема актуальна при решении некоторых задач технической диагностики [42 - 49], криптографии [50] и теории игр [51].

Цель работы состоит в установлении условий существования жи6 вых и безопасных решений (полу)автоматных уравнений относительно операции параллельной композиции и в разработке методов и алгоритмов характеризации таких решений. Существование полной характеризации живых и безопасных решений служит основой для синтеза оптимальных систем логического управления.

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

Результаты, выносимые на защиту. На защиту выносятся следующие научные результаты:

1. Необходимые и достаточные условия существования живого решения полуавтоматного неравенства С и алгоритм нахождения в произвольном его решении наибольшей редукции, которая является живым решением. Необходимые и достаточные условия существования (полностью определённого) живого решения автоматного неравенства А 0Х< С и алгоритм построения его наибольшего (полностью определённого) живого решения.

2. Новое отношение ^-моделирования на множестве полуавтоматов и метод полной характеризации живых решений полуавтоматного неравенства А0Ех1Х<С и (полностью определённых) живых решений автоматного неравенства А О Х< С с использованием этого отношения. Предложенный метод служит основой для разработки технологий выбора оптимальных решений.

3. Необходимые и достаточные условия существования наибольшего безопасного решения полуавтоматного неравенства АЪеяХ^С и автоматного неравенства А 0Х<С.

4. Необходимые и достаточные условия существования решения автоматного неравенства А0Х>С. Метод характеризации решений уравнения А0Х=С и неравенства А0Х>С в классе полностью определённых автоматов в случае, когда автомат С является детерминированным.

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

Научная новизна результатов, полученных в работе, состоит в следующем. Расширены и обобщены известные результаты [32] по построению наибольшего живого решения уравнений и неравенств на множестве полуавтоматов. Показано, что с использованием существующих методов [15] невозможно охарактеризовать все живые решения полуавтоматного неравенства в связи с чем в работе предложен оригинальный подход к данной проблеме, на основе которого впервые осуществляется полная харакгеризации живых решений полуавтоматного неравенства А§е*Х<С и автоматного неравенства А0Х<С. Получены необходимые и достаточные условия существования наибольшего безопасного решения и охарактеризованы безопасные решения неравенств АОе^Х^С и А0Х<С. Предложен оригинальный метод построения наибольшего (полностью определённого) живого решения неравенства А0Х<С, и охарактеризованы все его (полностью определённые) живые решения. Получены новые результаты по разрешимости автоматных уравнений и неравенств.

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

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

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

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

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

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

Публикации. По теме диссертации опубликовано 5 печатных работ [52 - 56]: 1 статья в центральном издании, 1 рецензируемый доклад и 3 тезисов докладов в трудах Российских и международных конференций.

Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения и списка цитируемой литературы. Объем диссертации составляет 144 страниц текста, набранного в гарнитуре Times New Roman 14 pt с межстрочным интервалом в 1.5 строки, в том числе: титульный лист - 1 е., оглавление - 2 е., основной текст, включающий 44 рисунка, -135 е., библиографический список из 79 наименований - 6 с.

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

3.5 Выводы по главе

В главе исследована структура множеств решений автоматных уравнений и неравенств и сформулированы необходимые и достаточные условия их разрешимости. В классе полностью определённых автоматов для случая детерминированного автомата С сформулированы необходимые и достаточные условия, при которых автомат является живым решением уравнения А<)Х=С, и достаточные условия, при которых автомат является решением неравенства А 0Х> С.

Сформулированы необходимые и достаточные условия существования наибольшего (полностью определённого) живого решения неравенства А0Х<С\ показано, что оно существует, если и только если неравенство обладает живым (полностью определённым) решением, и предложен алгоритм построения наибольшего (полностью определённого) живого реше

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

В главе сформулированы необходимые и достаточные условия существования наибольшего безопасного решения неравенства А 0Х< С и показано, что классы эквивалентных автоматов, упорядоченные по отношению редукции, образуют решётку на множестве безопасных решений. Показано, что в классе детерминированных автоматов любое живое решение является безопасным, а в классе детерминированных полностью определённых автоматов решение является безопасным, если и только если оно является живым. Таким образом, показано, что в данных случаях множество решений, которые одновременно являются живыми и безопасными, совпадает с множеством живых решений.

137

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

138 туациях вероятность получения "хорошего" решения достаточно велика.

Следует отметить, что задача решения уравнений и неравенств на множестве (полуавтоматов остается по-прежнему актуальной. Дальнейшие исследования в рамках данной задачи, в частности, включают разработку методов решения уравнения А<>Х= С и неравенства А <>Х>С на множестве автоматов и характеризации их живых и безопасных решений. Также актуальной является задача характеризации безопасных решений (по-лу)автоматных уравнений и неравенств в случае, когда наибольшего безопасного решения не существует. Более того, как уже отмечалось, интересной и до сих пор нерешённой остаётся задача характеризации решений, которые одновременно являются живыми и безопасными. га

Список литературы диссертационного исследования кандидат технических наук Буфалов, Сергей Анатольевич, 2002 год

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

2. Скляров В. А., Новиков С. В., Ярмояина В. И. Автоматизация проектирования ЭВМ. М.: Высшая школа, 1990. - 356 е.

3. Merlin P., Bochman G. v. On the Construction of Submodule Specifications and Communication Protocols // ACM Trans. On Programming Languages and Systems. 1983. - Vol. 5. - No. 1. - P. 1 - 25.

4. Wonham W. M. Supervision of DES. www.control.utoronto.ca.

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

6. Yevtushenko N., Villa Т., Brayton R. К., Petrenko A., Sangiovanni-Vincentelli A. Solving a Parallel Language Equation // Proceedings of the ICCAD'Ol. USA, 2001. P. 103 -110.

7. Yevtushenko N., Villa Т., Brayton R. Logic Synthesis by Equation Solving // Proc. of 16th Intern. Workshop on Logic synthesis.- USA, 2000. P. 107 -114.

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

9. Petrenko A., Yevtushenko N. Solving Asynchronous Equations // IFIP TC6 WG6.1 Joint International Conference. France, 1998. P. 231 - 247.

10. Kam Т., Villa Т., Brayton R., Sangiovanni-Vincentelli A. Synthesis of Finite State Machines: Functional Optimization. Boston: Kluwer Academic Publishers, 1997. - 284 p.

11. Kim G. Larsen, Liu X. Compositionality Through an Operational Semantics of Contests If J. Logic Computation. -1991. Vol. 1. - No. 6. - P. 761 - 795.

12. Watanabe Y., Brayton R. The Maximal Set of Permissible Behaviors for FSM Network // Trans, of IEEE/ACM Intern. Conf. on Computer-Aided Design. USA, 1993. P. 316 - 328.

13. Qin H., Lewis P. Factorization of Finite State Machines under Strong and Observational Equivalencies ft Formal Aspects of Computing. 1991. - No. 3.-P. 284-307.

14. Kim G. Larsen, Liu X. Equation Solving Using Modal Transition Systems //140

15. Proc. of 5й1 Symp. on Logic in Computer Science. Philadelphia, PA, USA, 1990. P. 108-117.

16. Drissi J., Bochmann G. V. Submodule Construction for Systems of I/O Automata. ftp://beethoven.site.uottawa.ca/Publications/Dris99b.pdf.

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

18. DiBenedetto M. D., Saldanha A., Sangiovanni-Vincentelli A. Strong Model Matching for Finite State Machines // Proc. of 3rd Europian Control Conference. Rome, Italy, 1995. P. 2027 - 2034.

19. DiBenedetto M. D., Saldanha A., Sangiovanni-Vincentelli A. Strong Model Matching for Finite State Machines with Nondeterministic Reference model 11 Proc. of 34rd Conf. Decision and Control. New Orleans, LA, USA, December 1994. P. 422 - 426.

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

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

22. Khatri S. P., Narayan A., Krishnan S. C. An Engineering Change Methodology Using Simulation Relations. Technical Report, ERL-95-50, Univ. of California, Berkeley, 1999.

23. Богомолов A. M., Грунекий И. С., Сперанский Д. В. Контроль и преобразование дискретных автоматов. Киев: Наукова думка, 1975.- 174 с.

24. Ветрова М. В. Синтез контроллеров для микропрограммных автомагов // Новые информационные технологии в исследовании дискретных структур. Тез. III Веерое. конф. 12-14 сентября 2000. Томск, 2000. С. 194 -199.

25. Wonham W. M., Ramadge P. J. On the Supremal Controllable Sublanguage141of a Given Language 11 SIAM J. Control. Optim. 1987. - Vol. 25. - No. 3. -P. 637-659.

26. Aziz A., Balarin. F., Brayton R., DiBenedetto M., and Saldanha A. Supervisory Control of Finite State Machines // Proc. of the 7th International Conference CAV'95. Belgium, 1995. P. 279-292.

27. Barret G, Lafortune S. Bisimulation, the Supervisiory Control Problem and Strong Model Matching for Finite State Machines // Discrete Event Dynamic Systems: Theory and Applications.- 1998,-Vol. 8,-No. 4,- P. 377-429.

28. Giua A., DiCesare F. Petri Nets For Supervisory Control Of Discrete Events Systems: A Structural Approach.- World Scientific Publishing, 2001,- 200 p.

29. Yamalidou K., Moody J., Lemmon M., Antsaklis P. Feedback Control of Petri Nets Based on Place Invariants. Technical Report ISIS-91-002 of the ISIS Group, University of Notre Dame, 1991. - 33 p.

30. Kumar R., Holloway L. E. Supervisory Control of Petri Nets with Regular Specification Languages // IEEE Transactions on Automatic Control. 1996. -Vol. 41.-No. 2.- P 245 -249.

31. Overkamp A. Supervisiory Control Using Failure Semantics and Partial Specifications // IEEE Transactions on Automatic Control. 1997. - Vol. 42. -No. 4.-P. 498-510.

32. Kumar R., Nelvagal S., Marcus S. I. A Discrete Event Systems Approach for Protocol Conversion // Discrete Event Dynamical Systems: Theory and Applications. 1997. - Vol. 7. - No. 3. - P. 295-315.

33. Kim J., Newborn M. The Specification of Sequential Machines with Input Restrictions H IEEE Trans, on Computers. -1992. C-20. - P. 1440 - 1443.

34. Rho J. K., Hachtel G., Somentzi F. Don't Cares Sequences and The Optimization of Interacting Finite State Machines // Proc. of the IEEE Conference on Computer Aided Design, Santa Clara. -1991. P. 414 - 421.

35. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978, том 2. - 612 с.

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

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

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

39. Starke P. Н. Abstract Automata. New-York: Elsevier Publishing, 1972.142

40. Агибалов Г. П. Дискретные автоматы на полурешётках. Томск: Издательство ТГУ, 1993. - 227 с.

41. Агибалов Г. П., Оранов А. М. Лекции по теории конечных автоматов. -Томск: Издательство ТГУ, 1984. 185 с.

42. Negulescu R. Process Spaces and Formal Verification of Asynchronous Circuits: Ph.D. Thesis. University of Waterloo, Canada, 1998. 248 p.

43. Negulescu R. Process Spaces // Proc. of 11th International Conference on Concurrency Theory. Pennsylvania, USA, August 22-25,2000.

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

45. Евтушенко Н. В., Лебедев А. В., Петренко А. Ф. Построение проверяющего множества для компоненты последовательной автоматной сети // Автоматика и телемеханика. 1994. - № 8. - С. 145 - 153.

46. Petrenko A., Yevtushenko N., Bochmann G. Experiments on Nondeterminis-tic Systems for the Reduction Relation. Dept. Publ. #932 of Universite de Monreal, 1991. - 24 p.

47. Petrenko A., Yevtushenko N., Lebedev A., Das A. Nondeterministic state machines in protocol conformance testing // Proc. of the IFIP 6th International Workshop on Protocol Test Systems. -1993. P. 363-378.

48. Yevtushenko N., Cavali A., and Lima L. Jr. Test Suite Minimization for Testing in Context // Proc. of the 11th IWTCS, Russia, 1998, pp. 127 145.

49. Petrenko A., Yevtushenko N., Bochmann G. v., and Dssouli R. Testing in Context: Framework and Test Derivation // Computer Communications. -1996. Vol. 19. - P. 1236 - 1249.

50. Menezes P., van Oorshot S. Vanstone. Handbook of Applied Cryptography. -CRC Press, Jnc. 1997. 816 p.

51. Буфалов С. А. Решение автоматного уравнения А\\Х>С // Новые информационные технологии в исследовании дискретных структур. Тез. Ш Всеросс. конф. 12-14 сентября 2000. Томск, 2000. С. 189 - 193.143

52. Буфалов С. А. К синтезу дискретных систем посредством решения уравнений // Современные проблемы радиотехники: Труды per. семинара, 26 29 ноября 2001. - Новосибирск, 2001. - С. 95 - 98.

53. Buffalov S. A., Yevtushenko N. V. Studying Solutions to a Parallel FSM Equation // Bulletin of the Novosibirsk Computing Center. 2001. - No. 14. - P. 7 - 17.

54. Буфалов С. А., Евтушенко H. В. Живые решения полуавтоматных уравнений // Проблемы теоретической кибернетики: Тез. Х1П Международной конф. 27 31 мая 2002. - Казань, 2002. - С. 71 - 74.

55. Евтушенко Н. В., Буфалов С. А. К решению автоматных уравнений // ХП Международная конференция по проблемам теоретической кибернетики, 17-22 мая 1999. Нижний Новгород, 1999. - С. 65.

56. Жарикова С. Решение автоматных уравнений в различных приложениях // Наука. Техника. Инновации: Тез. докл. науч. конф. молодых учёных, Новосибирск, 2001. С 87 - 91.

57. Bloom В., Istrail S., Meyer A. R. Bisimulation Can't be Traced. Tech. report TR 90-1150, Cornell University, NY, 1990. - 48 p.

58. Van Glabbeek R. J. Comparative Concurrency Semantics and Refinement of Actions. Center for Mathematics and Computer Science, Amsterdam. Tech. report CS-R9029,1990.

59. Clarke E., Wing J. Formal Methods: State of the Art and Future Directions. -CMU technical report CMU-CS-96-178,1996. 22 p.

60. Lynch N. A., Tuttle M. R. An Introduction to Input/Output Automata // CWI Quarterly. 1989. - Vol. 2. - No. 3. - P. 219-246.

61. 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, August 2000. 9 p.

62. Peyman Gohari, Wonham W. M. Reduced Supervisors for Timed Discrete-Event Systems // 5th Int. Workshop on Discrete Event Systems, 2000. 12 p.

63. Мальцев А. И. Алгебраические системы. M.: Наука, 1970. - 392 с.

64. Watson В. W. A Taxonomy of Finite Automata Construction Algorithms. -Computing Science Note 93/43, Eindhoven University of Technology, The Netherlands, 1993. 88 p.

65. Богомолов A. M., Салий В. H. Алгебраические основы теории дискрет144ных систем. М.: Наука, 1997. - 368 с.

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

67. Рабин М. О., Скот Д. Конечные автоматы и задачи их разрешения // Киб. Сборник. 1962. - Вып. 4. - С. 56 - 91.

68. Клини С. К. Представление событий в нервных сетях / сб. Автоматы. -1956.-С. 15-67.

69. Leslie Т. Efficient Approaches to Subset Construction: Master thesis. Canada: University of Waterloo, Ontario, 1995. - 82 p.

70. Johnson J. H., Wood D. Instruction Computation in Subset Construction. -Technical Report HKUST-CS96-21,1996.

71. Braudt R. D., Garg V. K., Kumar R., Liu F. Formulas for Calculating Supre-mal Controllable and Normal Sublanguages // Systems and Control Letters. -1990. Vol. 15. - No. 3. - P. Ill -117.

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

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

74. Rob Van Glabbeek. On the Expressiveness of ACP // Proc. of ACP94 Workshop on Algebra of Communicating Processes. May 1994. Utrecht, The Netherlands, 1994. P. 188 - 217.

75. Liu X. On Decidability and Small Model Property of Process Equations. -University of Sussex Tech. Report No. 10,1993. 13 p.

76. Drissi J., Bochmann G. Submodule Construction Tool // Proceedings of International Conference on Computational Intelligence for Modeling, Control and Automation. Vienne, 1999. P. 319 - 324.

77. Штарнова О. В. К декомпозиции дискретных систем, описанных сетями Петри // Современные проблемы радиотехники: Труды per. сем. 2629 ноября 2001. Новосибирск, 2001. С. 91 - 94.

78. Chen P., Wonham W. М. Real-Time Supervisory Control of a Processor For Non-preemptive Execution of Periodic Tasks. System Control Group Report No. 9802, 1998.-35 p.