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

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


               1.3. Аналитическое представление
               недетерминированных автоматов
                     на стандартном языке
         Если с каждой вершиной направленного графа НДА связать
предикатную переменную Sj(t), с каждым входным сигналом -предикатную
переменную Xi,j(t), а с каждым выходным сигналом — предикатную
переменную Yj(t), где t пробегает ряд целых неотрицательных чисел (t = 0, 1,
2, ...), то функционирование НДА может быть задано системой рекуррентных
бескванторных предикатных формул вида (1.1), описывающих все
реализуемые в автомате частные события Sj:
                  Yj
                 S j (t  1)  V X i , j (t ) & S i (t )  V X j , j (t ) & S j (t )   (1.1)
                                i, j                         j

                              S0(0) = I,       j  0, m ,
где (m +1) — число вершин графа (число всех событий, реализуемых НДА);
   Si(t) — сокращенное обозначение выражения, описывающего событие Si,
            непосредственно предшествующее событию Sj, при этом каждая
            предикатная формула Si(t) должна быть либо тождественно
            истинной предикатной формулой, либо удовлетворять условию
            Si(t)Sj(t) и определяться также выражением вида (1.1);
   Xi,j — частный входной сигнал, представляющий собой сочетание
          элементарных входных сигналов из алфавита Х, в результате
          воздействия которых осуществляется переход от вершины графа
          НДА с номером i к вершине графа с номером j (в новых
          обозначениях переход от события Si к событию Sj);

                                                                                               13