Редукция процесса

Операция редукции состоит в сведении данного АП к более простому.

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

Пусть задан неприведенный АП Р = <S, F, I, R>, ситуации которого структурированы по 2-му способу, т.е. множество S представимо упорядоченной тройкой

S = (X,Y,Z), где X,Y,Z - соответственно множества значений входной, выходной компоненты и компоненты, не являющейся ни входной ни выходной.

Образуем р-блочное разбиение множества S процесса Р, в ситуациях каждого блока которого входная компонента принимает фиксированное значение x_j, 1≤j≤p.

Выберем r < p различных значений входной компоненты и составим множество X*Ì X.

Ситуации, входящие в те блоки разбиения, которые соответствуют выбранным значениям входной компоненты, обозначим S*, S*Ì S.

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

Образуем множество S(X*) как объединение тех множеств S(s_i), для которых справедливо S(s_i) Í S*, т.е. в S(X*) включаем те ситуации из S*, для которых существуют траектории, начинающиеся в инициаторах:

S(X*) =

Постоим также F(X*) = F Ç (S(X*)´S(X*))

I(X*) = I Ç S(X*), R(X*) = R Ç S(X*).

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

Аналогично определяется редукция P(Y*) неприведенного процесса по выбранному множеству Y* значений выходной компоненты.

Пример: построим возможную редукцию неприведенного асинхронного процесса работы лазерного принтера. Используем, описанное выше структурирование ситуаций АП по входным компонентам, и построим редукцию процесса по выбранному множеству Х^* значений входных компонент.

Множество входных компонент: Х = {10, 11}.

х = (М Р), где М – память,P – бумага для печати;

S₁ = (1,0,0,0,0,0,0)

S₂ = (1,1,0,0,0,0,1)

S₃ = (1,0,0,0,0,0,1)

S₄ = (1,1,1,0,1,0,0)

S₅ = (1,1,0,1,1,0,0)

S₆ = (1,1,0,0,1,1,0)

S₇ = (1,1,0,0,1,0,1)

Выберем значения входных компонент для построения редукции: Х^* = {11}.

Такой выбор означает, что необходимо выделить подпроцесс непосредственной печати, когда все внешние условия выполнены.

Тогда множество S^* будет включать следующие ситуации:

S^* = { s₂, s₄, s₅, s₆, s₇ }.

Рассмотрим траектории АП, начинающиеся в инициаторах процесса:

S(s₁):

S(s₂):

Очевидно, что все ситуации S^* принадлежат траектории s₂ M s₇ и, следовательно, S(X^*) = S^*.

Таким образом, редукцией данного АП по выбранному множеству Х^* значений входных компонент является асинхронный процесс

P(X^*) = <S(X^*), F(X^*), I(X^*), R(X^*)>, где

S(X^*) = { s₂, s₄, s₅, s₆, s₇ },

F(X^*) = {(s_2, s₄), (s_4, s₅), (s_5, s₆), (s_6, s₇)},

I(X^*) = { s₂ },

R(X^*) = { s₇ }.

Конец примера.

Репозиция редукции

Рассмотрим теперь репозицию редукции Р(Х*) процесса Р.

Образуем р-блочное разбиение ситуации S’ процесса Р’, каждый блок которого соответствует фиксированному значению x_j, 1≤j≤p, входной компоненты.

Образуем множество S’* как объединение тех блоков, в ситуациях которых x_jÎХ*.

Далее для каждого инициатора i_j’ÎR(X*) процесса Р’ и каждого результанта r_m’ÎI(X*) рассмотрим множество ситуаций S_k’(i_j’,r_m’), принадлежащих каждой траектории i_j’ в r_m’.

Построим:

1) множество S’(X*) =

2) отношение F’(X*), задающее следование ситуаций на этих траекториях

F’(X*) = F’ Ç (S’(X*)´S’(X*))

3) множества I’(X*) = I’ Ç S’(X*), R’(X*) = R’ Ç S’(X*).

Процесс P’(X*) = <S’(X*), F’(X*), I’(X*), R’(X*)> и будет искомой репозицией редукции Р(Х*) процесса Р.

Аналогично, по репозиции Р’ процесса Р строится репозиция редукции Р(Y*) по выходным компонентам.

Пример: построим возможную репозицию редукции АП, соответствующего работе лазерного принтера. Построенная выше репозиция имеет вид:

P’=<S’, F’, I’, R’>,

где S’ = { s₁, s₂, s₃, s₇, s₈^Д, s₉^Д }, { s₁, s₂, s₃, s₇ } Í S,

F’ = {(s_7, s₁), (s_7, s₂), (s₇, s₉),(s₉,s₁),(s_3, s₈),(s_8, s₂)}

I’ = { s₃, s₇ },

R’ = { s₁, s₂ }.

Граф отношения F’:

Рис.10

s₁ = (1,0,0,0,0,0,0)

s₂ = (1,1,0,0,0,0,1)

s₃ = (1,0,0,0,0,0,1)

s₇ = (1,1,0,0,1,0,1)

s₈ = (1,1,0,0,0,0,0)

s₉ = (0,0,0,0,0,0,0)

Образуем 3-блочное разбиение ситуации S’ процесса Р’, каждый блок которого соответствует фиксированному значению x_j, j=1,2,3 входной компоненты:

s₁ = (1,0,0,0,0,0,0) s₂ = (1,1,0,0,0,0,1) s₉ = (0,0,0,0,0,0,0)

s₃ = (1,0,0,0,0,0,1) s₇ = (1,1,0,0,1,0,1)

s₈ = (1,1,0,0,0,0,0)

Выберем Х^*={11}.

Образуем S^*={ s₂, s₇, s₈ }.

Рассмотрим траектории репозиции:

s₇ ® s₁

s₇ ® s₉ ® s₁

s₇ ® s₂

s₃ ® s₈ ® s₂

Тогда искомая репозиция редукции будет иметь вид:

S’(X^*) = { s₂, s₇ }

F’(X*) = F’ Ç (S’(X*)´S’(X*)) = {(s₇, s₂)}

I’(X*) = I’ Ç S’(X*) = { s₇ },

R’(X*) = R’ Ç S’(X*) = { s₂ }.

Рис.11

Конец примера.

Редукция приведенного процесса Р^п строится по редукции неприведенного процесса Р и репозиции редукции Р’(X*).

Очевидны следующие утверждения:

1. Редукция неэффективного процесса может быть эффективным процессом.

2. Редукция эффективного процесса (если она существует) - всегда эффективный процесс.

3. Редукция управляемого процесса (если она существует) - всегда управляемый процесс.

4. Редукция частично приведенного процесса может быть полностью приведенным процессом, а редукция полностью приведенного процесса может оказаться частично приведенным и даже неприводимым процессом.

ЗАМЕЧАНИЕ. Из правил построения редукции следует, что редукция Р(Х^*) процесса Р может быть определена не на всем множестве Х^*, а на некотором подмножестве Х^**, Х^**Ì Х^*, так как при построении редукции из исходного процесса исключаются не отдельные ситуации, а пучки траекторий. При этом Р(Х^**)=Р(Х*).