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

     Для таких соединителей алгоритмический процесс распространяется за
соединитель при окончании его в любой из соединяемых ветвей, т.е. имеем:
                   S в  S k1    S ki    S kn ,                 (4.66)
      Из выражения (4.66) следует, что если по инициативе какой-либо ветви
процесс распространился за вершину соединения, а в это время в другой
ветви процесс достигает соединителя, то возможна неоднозначность
выполнения алгоритма. Если это недопустимо, то должны быть
предусмотрены меры устранения такой неоднозначности. Для этой цели
выполняют коррекцию алгоритма таким образом, чтобы при достижении
алгоритмическим процессом в любой ветви соединителя, он распространялся
бы за соединитель с одновременной ликвидацией алгоритмических
процессов во всех параллельных ветвях. Это обеспечивается коррекцией
описания частных событий во всех параллельных ветвях с учетом того, что
все частные события в любой i-ой ветви должны быть несовместимы с
событиями, отмечающими окончание алгоритмического процесса во всех
других ветвях. В общем случае коррекцию частных событий в любой i-ой
ветви можно представить таким образом:
                            S i (t  1)  S i (0)  S в ,           (4.67)
где S i (0) - сокращенное обозначение события Si без учета коррекции.
      Соединитель комбинированный J(&,v).
      Для комбинированного соединителя функция SВ имеет вид:
                               ~      ~
                       S в  V S k1  S ki  S kn ,                   (4.68)
      Из (4.68) следует, что S в есть дизъюнктивная нормальная форма от
переменных типа S ki .
      Для такого типа соединителя однозначность выполнения алгоритма
также требует коррекции всех частных событий во всех параллельных
ветвях, как и для дизъюнктивного соединителя. Это означает, что для всех
частных событий всех параллельных ветвей правая часть их описания
должна быть умножена на S В в соответствии с выражением (4.67).
     В тех случаях, когда выход за соединитель J(&,v) в соответствии с
алгоритмом может осуществляться не обязательно при одновременном
появлении событий типа S ki , то эти события после их зарождения следует
сохранять до тех пор, пока не будет истинным комбинационное событие S B .
В связи с этим в описаниях событий типа S ki должны быть предусмотрены
условия сохранения событий S ki в соответствии с выражением (4.65).




                                                                               101