Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 4 стр.

      Математические модели устройств управления, принятые в работе и
основанные на использовании концепции параллелизма и недетерминизма,
являются достаточно простыми и универсальными, позволяющими их
использовать для широкого круга применения как по управлению
процессами и ресурсами, так и для моделирования событий, начиная от
простейших устройств и кончая функциями управления операционных
систем.
      В первых трех главах учебного пособия рассмотрены основные
понятия и определения из теории недетерминированных автоматов (НДА) и
методы их эквивалентных преобразований на основе операций
детерминизации, минимизации кодирования и композиции.
      В четвертой главе рассматриваются начальные языки, используемые
для представления управляющих алгоритмов параллельной обработки. К ним
относятся: язык регулярных выражений алгебры событий (РВАС), язык
исчисления предикатов первого порядка с ограниченными кванторами и его
связь с языком РВАС, язык операторных схем алгоритмов с параллельными
ветвями. Рассматриваются также и обычные (непараллельные) языки – язык
граф-схем алгоритмов (ГСА) и язык логических схем алгоритмов (ЛСА), т.к.
они являются основой для построения параллельных языков. Для каждого
начального языка рассматривается методика преобразования описания на
начальном языке на описание на стандартном языке в виде системы
канонических уравнений для всех событий, реализуемых в алгоритме
управления.
      Отличительной особенностью формализации управляющих алгоритмов
на начальных языках заключается в том, что в качестве входного алфавита
используется множество элементарных двоичных сигналов. При этом
реализуемые в автомате события могут зависеть либо от всех, либо от части
элементарных входных сигналов и эта зависимость событий от элементарных
входных сигналов на разных шагах работы алгоритма управления может
быть различной. Поэтому в качестве входных сигналов на каждом шаге
работы алгоритма управления используются частные входные входы,
которые образуются сочетаниями только тех элементарных двоичных
входных сигналов, которые действуют на данном переходе. Это
обстоятельство, наряду с использованием для описания управляющих
алгоритмов частных событий, а не состояний, позволяет значительно
уменьшить критичность формального описания к ее размерности,
определяемой как произведение состояний системы на число входных
сигналов.
      В пятой главе рассматриваются вопросы структурной реализации
алгоритмов логического управления, заданных моделью НДА. При этом
отмечаются недостатки классических методов структурного синтеза систем
управления на основе использования моделей детерминированных конечных
автоматов. Обращается особое внимание структурной реализации систем
управления на основе разбиения частных событий, реализуемых в автомате,

                                                                        4