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

событий в виде системы рекурсивно определяемых предикатных формул,
имеющих одинаковую структуру вида (4.37).
      Такая система в расширенном исчислении предикатов может быть
преобразована в более удобную для формализации словесных алгоритмов
системы  A p . Под расширенным исчислением предикатов в данном случае
понимается исчисление предикатов с добавлением к нему двух аксиом,
формализующих закон нейтральности пустого слова алгебры событий [9, 22].
      Аксиома 1.
                      F (t )  (τ) F (τ) & ( τ1 )e( τ1 ) .    (4.44)
                                           t                      1 t

       Аксиома 2.
         ( τ ) F ( τ1 )  ( τ1 )e( τ1 )  τ  t & F (t ) & ( τ1 ) F ( τ1 ) ,                                    (4.45)
            1 t              1 t                                                  1 t

где  - знак эквивалентности в расширенном исчислении предикатов,
     F(t) – предикатная формула.
        Для построения новой системы  A p введем понятие рода событий и
ветвей алгоритма.
       Все события -го ранга                             S i,, j  , непосредственно определяющие
                      i
некоторое событие S ,   , разделим на две принципиально разные группы
событий. К одной группе отнесем все события, которые определяют
                                                i
зарождение, т.е. первичное появление события S ,  . Будем называть такие
события событиями 1-го рода.
       К другой группе отнесем все события S i,, j  , которые определяют
возобновление события Si , , т.е. повторное его появление. Будем называть
такие события событиями 2-го рода.
       Аналогично ветви алгоритма, описывающие события 1-го (2-го) рода,
будем называть ветвями 1-го (2-го) рода.
       В связи с изложенным выражение вида (4.37), описывающее в
исчислении предикатов событие Si , , может быть записано так:
                                      j  k1                        j k2
                        i                        [i , j ] (t ) 
                      S  , (t )    V        S  ,                V        S [i,,k1 j ] (t ) ,               (4.46)
                                      j 1                           j 1
где k1 - число ветвей 1-го рода;
    k2 - число ветвей 2-го рода.
      Выполнив подстановку вместо предикатов                                                           выражения     (4.46)
обозначаемые ими предикатные формулы, получим:



                                                                                                                            82