Алгебра асинхронных процессов. Одноместные и многоместные операции.

Репозиция задаёт механизм перехода от результантов к инициаторам. Описание такого механизма нужно для получения эффекта возобновления АП, его повторных активизаций.

Репозиция асинхр. процесса P = < S, F, I, R > – эффективный АП P’ = <S’, F’, I’, R’ >, такой, что S’ Í I È R È S^Д (где S^Д – нек. дополн. ситуации, отстутствовавшие в описании исходного АП: S^Д Ç S = Æ), I’ Í R, R’ Í I. Отношение F’ задаёт траектории переходов от элементов из I’ к элементам из R’, возможно, через доп. ситуации из S^Д. Если I’ = R & R’ = I, то репозиция полная. Если F’ = Æ, то репозиции не существует. Иначе она частичная.

Приведенный пр-сс – это пр-сс P^П = <S^П, F^П, I^П, R^П>, такой, что S^П= ­S È S^Д,
F^П = F È ( F’ \ ( F’ Ç (S’ ´ I) ) ), I^П ÍI, R^П = R È S^Д.

Иными словами, приведенный пр-сс – это объед-е АП и его репозиции, в котором из отношения F’ выброшены пары, задающие переходы к иниц-рам пр-сса (образующие пары F’ Ç (S’ ´ I)). В зав-ти от того, какую репозицию имеет Р, соотв-й приведенный пр-сс Р^П называется полностью или частично приведенным.

Редукция. Суть редукции состоит в сведении данного АП к более простому. Такая операция нужна, когда из полного описания пр-сса хочется выделить некую его часть, рассмотрение кот-ой интересно по тем или иным причинам.

Пусть задан непрер. АП P = < S, F, I, R >, ситуации которого структурированы так, что мн-во ситуаций S представимо упорядоченной тройкой S = (X, Y, Z), где X, Y и Z – соответственно, множества значений входной компоненты, выходной компоненты и компоненты, не являющейся ни входной ни выходной.

Образуем р-оболочное разбиение p мн-ва S пр-сса Р, в ситуациях каждого блока которого вх. компонента принимает фиксированное значение x_j, 1 £ j £ р. Выберем r < p различных значений вх. компоненты (составляющих мн-во Х* Ì Х). Ситуации, входящие в те блоки разбиения p, которые соответствуют выбранным значениям входной компоненты, составляют подмн-во S* Ì S.

Для каждого иниц-ра s_i построим мн-во ситуаций S(s_i), встречающихся на траекториях пр-сса Р, ведущих из s_i. Образуем мн-во . Построим также , , .

Назовём пр-сс P(X*) = < S(X*), F(X*), I(X*), R(X*) > редукцией неприведенного пр-сса P = < S, F, I, R > по выбранному мн-ву Х* значений вх. компоненты. Аналогично определяется редукция P(Y*) по выходной компоненте.

Последовательная композиция необязательно приведенного процесса Р₁ и приведенного Р^П₂ – это АП Р₃, (его ситуации: s³ = (s¹, s²)) образованный отождествлением значений входной и выходной компонент ситуаций редуцированных пр-ссов P₁(Y*₁) и P₂(X*₂) соотв-но при выполнении следующих ограничений:
1) s¹ Î S₁(Y*₁), s² Î S₂(X*₂), т.е. S₃ Í S₁(Y*₁) ´ S₂(X*₂);
2) выходная компонента у¹ ситуации s¹ равна входной компоненте х² ситуации s²;
3) если в s³ компонента s² Î I₂(X*₂), то s¹ Î R₁(Y*₁);
4) если (s¹_i , s²_j ) F₃ (s¹_k , s²_l ), то:
либо (s¹_i F₁ s¹_k ) & (s²_j F₂ s²_l ), либо (s¹_i F₁ s¹_k ) & (s²_j = s²_l ), либо (s¹_i = s¹_k ) & (s²_j F₂ s²_l ).

Смысл ограничения 1) состоит в том, чтоб при функционировании пр-сса Р^П₂ в составе пр-сса Р₃ в редукции P^П₂(X*₂) не встречались ситуации, не принадлежащие мн-ву S₂(X*₂). Ограничение 4) говорит о том, что для редукции P^П₂(X*₂) пр-сса P₂ в составе Р₃ не могут возникнуть новые траектории.

Параллельная композиция асинхр. пр-ссов Р₁ и Р₂ – это пр-сс Р₃, образованный отождествлением значений входных компонент ситуаций редуцированных пр-ссов P₁(Х*) и P₂(X*) при выполнении след. ограничений:
1) s¹ Î S₁(Y*₁), s² Î S₂(X*₂), т.е. S₃ Í S₁(Y*₁) ´ S₂(X*₂);
2) вх. компоненты х¹ и х² ситуаций s¹ и s² эквивалентны: х¹ = х² = x.