Теория процессов
 Скачать 1.62 Mb.
|
|
= f (α)? • f (τ ) def = τ Теорема 7. Пусть P – процессы вида P = P 1 [f 1 ] | . . . | P n [f n ] \ L где для каждого i ∈ {1, . . . , n} P i ∼ n i X j=1 a ij . P ij Тогда P сильно эквивалентен сумме 1. всех процессов вида f i (a ij ). P 1 [f 1 ] | . . . . . . | P i−1 [f i−1 ] | P ij [f i ] | P i+1 [f i+1 ] | . . . . . . | P n [f n ] \ L где a ij = τ или name(f i (a ij )) 6∈ L, и 2. всех процессов вида τ. P 1 [f 1 ] | . . . . . . | P i−1 [f i−1 ] | P ik [f i ] | P i+1 [f i+1 ] | . . . . . . | P j−1 [f j−1 ] | P jl [f j ] | P j+1 [f j+1 ] | . . . . . . | P n [f n ] \ L где 1 ≤ i < j ≤ n, a ik , a jl 6= τ , и f i (a ik ) = f j (a jl ). Доказательство. Данная теорема непосредственно следует из • предыдущей теоремы, • теоремы 3, • свойств 6, 9, 10, 16 и 17 из параграфа 3.7, и • первого утверждения из теоремы 4. 82 4.6 Распознавание сильной эквивалент- ности 4.6.1 Отношение µ(P 1 , P 2 ) Пусть заданы два процесса P i = (S i , s 0 i , R i ) (i = 1, 2) Определим функцию 0 на множестве всех отношений из S 1 в S 2 , которая сопоставляет каждому отношению µ ⊆ S 1 × S 2 отношение µ 0 ⊆ S 1 × S 2 , определяемое следующим образом: µ 0 def = (s 1 , s 2 ) ∈ ∈ S 1 × S 2 ∀a ∈ Act ∀s 0 1 ∈ S 1 : (s 1 a → s 0 1 ) ∈ R 1 ∃s 0 2 ∈ S 2 : ( (s 2 a → s 0 2 ) ∈ R 2 (s 0 1 , s 0 2 ) ∈ µ ∀s 0 2 ∈ S 2 : (s 2 a → s 0 2 ) ∈ R 2 ∃s 0 1 ∈ S 1 : ( (s 1 a → s 0 1 ) ∈ R 1 (s 0 1 , s 0 2 ) ∈ µ Нетрудно доказать, что для каждого µ ⊆ S 1 × S 2 µ удовлетворяет условиям 1 и 2 из определения БМ ⇔ µ ⊆ µ 0 Следовательно, µ – БМ между P 1 и P 2 ⇔ ( (s 0 1 , s 0 2 ) ∈ µ µ ⊆ µ 0 Нетрудно доказать, что функция 0 монотонна, т.е. если µ 1 ⊆ µ 2 , то µ 0 1 ⊆ µ 0 2 Обозначим символом µ max объединение всех отношений из совокупности {µ ⊆ S 1 × S 2 | µ ⊆ µ 0 } (4.30) Заметим, что отношение µ max принадлежит совокупности (4.30), так как для каждого µ ∈ (4.30) из 83 • включения µ ⊆ ( S µ∈(4.30) µ) = µ max , и • монотонности функции 0 следует, что для каждого µ ∈ (4.30) µ ⊆ µ 0 ⊆ µ 0 max Поэтому µ max = S µ∈(4.30) µ ⊆ µ 0 max , т.е. µ max ∈ (4.30). Заметим, что имеет место равенство µ max = µ 0 max так как из включения µ max ⊆ µ 0 max и из монотонности функции 0 следует включение µ 0 max ⊆ µ 00 max т.е. µ 0 max ∈ (4.30), откуда, в силу максимальности µ max , следует включение µ 0 max ⊆ µ max Таким образом, отношение µ max является • наибольшим элементом совокупности (4.30), и • наибольшей неподвижной точкой функции 0 Мы будем обозначать это отношение знакосочетанием µ(P 1 , P 2 ) (4.31) Из теоремы 2 следует, что P 1 ∼ P 2 ⇔ (s 0 1 , s 0 2 ) ∈ µ(P 1 , P 2 ) Из определения отношения µ(P 1 , P 2 ) вытекает, что данное от- ношение состоит из всех пар (s 1 , s 2 ) ∈ S 1 × S 2 , таких, что P 1 (s 1 ) ∼ P 2 (s 2 ) Отношение µ(P 1 , P 2 ) можно рассматривать как меру близо- сти между P 1 и P 2 84 4.6.2 Полиномиальный алгоритм распознавания сильной эквивалентности Пусть P 1 и P 2 – процессы вида P i = (S i , s 0 i , R i ) (i = 1, 2) Если множества S 1 и S 2 конечны, то задача проверки истин- ности соотношения P 1 ∼ P 2 (4.32) очевидно является алгоритмически разрешимой: например, мож- но перебрать все отношения µ ⊆ S 1 × S 2 и для каждого из них проверить условия 0, 1 и 2 из определения БМ. Алгоритм закан- чивает свою работу, когда • нашлось хотя бы одно отношение µ ⊆ S 1 × S 2 которое удо- влетворяет условиям 0, 1 и 2 из определения БМ, в этом случае он выдаёт ответ P 1 ∼ P 2 или • все отношения µ ⊆ S 1 × S 2 перебраны, и ни одно из них не удовлетворяет условиям 0, 1 и 2 из определения БМ, в этом случае он выдаёт ответ P 1 6∼ P 2 Если P 1 6∼ P 2 , то вышеприведённый алгоритм выдаст ответ после перебора всех отношений между S 1 и S 2 , число которых – 2 |S 1 |·|S 2 | , т.е. данный алгоритм имеет экспоненциальную слож- ность. Данную задачу можно решить гораздо более эффективным алгоритмом, который имеет полиномиальную сложность. Для построения такого алгоритма мы рассмотрим следующую после- довательность отношений между S 1 и S 2 {µ i | i ≥ 1} (4.33) 85 где µ 1 def = S 1 × S 2 , и ∀ i ≥ 1 µ i+1 def = µ 0 i Из соотношения µ 1 ⊇ µ 2 и монотонности функции 0 следует, что µ 2 = µ 0 1 ⊇ µ 0 2 = µ 3 µ 3 = µ 0 2 ⊇ µ 0 3 = µ 4 и т.д. Таким образом, последовательность (4.33) монотонна: µ 1 ⊇ µ 2 ⊇ . . . Поскольку все члены последовательности (4.33) являются под- множествами конечного множества S 1 × S 2 , то данная последо- вательность не может бесконечно убывать, она стабилизируется на некотором члене, т.е. для некоторого i ≥ 1 имеет место соот- ношение µ i = µ i+1 = µ i+2 = . . . Докажем, что член µ i , на котором наступает стабилизация, сов- падает с отношением µ(P 1 , P 2 ). • Т.к. µ i = µ i+1 = µ 0 i , т.е. µ i – неподвижная точка функции 0 , то µ i ⊆ µ(P 1 , P 2 ) (4.34) поскольку µ(P 1 , P 2 ) – наибольшая неподвижная точка функ- ции 0 • Т.к. для каждого j ≥ 1 имеет место включение µ(P 1 , P 2 ) ⊆ µ j (4.35) поскольку – включение (4.35) верно для j = 1, и – если включение (4.35) верно для некоторого j, то, в силу монотонности функции 0 , имеем соотношения µ(P 1 , P 2 ) = µ(P 1 , P 2 ) 0 ⊆ µ 0 j = µ j+1 т.е. включение (4.35) будет верно для j + 1 86 то, в частности, (4.35) верно для j = i. Из (4.34) и (4.35) для j = i следует равенство µ i = µ(P 1 , P 2 ) (4.36) Таким образом, задача проверки истинности соотношения P 1 ∼ P 2 может быть решена путём • нахождения первого члена µ i последовательности (4.33), который удовлетворяет условию µ i = µ i+1 , и • проверки для этого µ i соотношения (s 0 1 , s 0 2 ) ∈ µ i (4.37) Алгоритм выдаёт ответ P 1 ∼ P 2 тогда и только тогда, когда выполняется (4.37). Для вычисления членов последовательности (4.33) можно ис- пользовать нижеследующий алгоритм, который по отношению µ ⊆ S 1 × S 2 вычисляет отношение µ 0 : µ 0 := ∅ цикл для каждого (s 1 , s 2 ) ∈ µ включить := > цикл для каждого s 0 1 , a : s 1 - a s 0 1 найдено := ⊥ цикл для каждого s 0 2 : s 2 - a s 0 2 найдено := найдено ∨ (s 0 1 , s 0 2 ) ∈ µ конец цикла включить := включить ∧ найдено конец цикла цикл для каждого s 0 2 , a : s 2 - a s 0 2 найдено := ⊥ цикл для каждого s 0 1 : s 1 - a s 0 1 найдено := найдено ∨ (s 0 1 , s 0 2 ) ∈ µ конец цикла включить := включить ∧ найдено конец цикла если включить то µ 0 := µ 0 ∪ {(s 1 , s 2 )} конец цикла 87 Заметим, что данный алгоритм корректен только в том случае, когда µ 0 ⊆ µ (что имеет место в том случае, когда этот алго- ритм используется для вычисления членов последовательности (4.33)). В общей ситуации внешний цикл должен иметь вид цикл для каждого (s 1 , s 2 ) ∈ S 1 × S 2 Оценим сложность данного алгоритма. Обозначим символом A чиcло A def = max(|Act(P 1 )|, |Act(P 2 )|) + 1 • Внешний цикл делает не более |S 1 | · |S 2 | итераций. • Оба цикла, содержащиеся в во внешнем цикле, делают не более |S 1 | · |S 2 | · A итераций. Поэтому сложность этого алгоритма можно оценить функцией O(|S 1 | 2 · |S 2 | 2 · A) Поскольку для вычисления того члена последовательности (4.33), на котором наступает её стабилизация, нужно вычислить не боль- ше чем |S 1 |·|S 2 | членов этой последовательности, то, следователь- но, искомое отношение µ i = µ(P 1 , P 2 ) может быть вычислено за время O(|S 1 | 3 · |S 2 | 3 · A) 4.7 Минимизация процессов 4.7.1 Свойства отношений вида µ(P, P ) Теорема 8. Для каждого процесса P def = (S, s 0 , R) отношение µ(P, P ) яв- ляется эквивалентностью. Доказательство. 1. Рефлексивность отношения µ(P, P ) следует из того, что диагональное отношение Id S = {(s, s) | s ∈ S} удовлетворяет условиям 1 и 2 из определения БМ, т.е. 88 Id S ∈ (4.30). 2. Симметричность отношения µ(P, P ) следует из того, что если отношение µ удовлетворяет условиям 1 и 2 из опреде- ления БМ, то обратное отношение µ −1 тоже удовлетворяет этим условиям, т.е. если µ ∈ (4.30), то µ −1 ∈ (4.30). 3. Транзитивность отношения µ(P, P ) следует из того, что произведение µ(P, P ) ◦ µ(P, P ) удовлетворяет условиям 1 и 2 из определения БМ, т.е. µ(P, P ) ◦ µ(P, P ) ⊆ µ(P, P ) Обозначим символом P ∼ процесс, компоненты которого име- ют следующий вид. • Множество состояний процесса P ∼ представляет собой со- вокупность классов эквивалентности, на которые разбива- ется множество S по отношению µ(P, P ). • Начальным состоянием является класс [s 0 ], который содер- жит начальное состояние s 0 процесса P . • Множество переходов процесса P ∼ состоит из всех перехо- дов вида [s 1 ] - a [s 2 ] где s 1 - a s 2 – произвольный переход из R. Процесс P ∼ называется фактор-процессом процесса P по эк- вивалентности µ(P, P ). Теорема 9. Для каждого процесса P отношение µ def = { (s, [s]) | s ∈ S} 89 является БМ между P и P ∼ Доказательство. Проверим для µ свойства из определения БМ. Свойство 0 верно по определению начального состояния про- цесса P ∼ . Свойство 1 верно по определению множества переходов процесса P ∼ Докажем свойство 2. Пусть P ∼ содержит переход [s] - a [s 0 ] Докажем, что существует переход в R вида s - a s 00 такой, что (s 00 , [s 0 ]) ∈ µ, т.е. [s 00 ] = [s 0 ], т.е. (s 00 , s 0 ) ∈ µ(P, P ) Из определения множества переходов процесса P ∼ следует, что R содержит переход вида s 1 - a s 0 1 (4.38) где [s 1 ] = [s] и [s 0 1 ] = [s 0 ], т.е. (s 1 , s) ∈ µ(P, P ) и (s 0 1 , s 0 ) ∈ µ(P, P ) Так как µ(P, P ) – БМ, то из • (4.38) ∈ R, и • (s 1 , s) ∈ µ(P, P ) следует, что R содержит переход вида s - a s 00 1 (4.39) где (s 00 1 , s 0 1 ) ∈ µ(P, P ). 90 Так как µ(P, P ) транзитивно, то из (s 00 1 , s 0 1 ) ∈ µ(P, P ) и (s 0 1 , s 0 ) ∈ µ(P, P ) следует (s 00 1 , s 0 ) ∈ µ(P, P ) Таким образом, в качестве искомого s 00 можно взять s 00 1 Из теоремы 9 следует, что для каждого процесса P P ∼ P ∼ 4.7.2 Минимальные процессы относительно ∼ Процесс P называется минимальным относительно ∼, если • каждое его состояние достижимо, и • µ(P, P ) = Id S (где S – множество состояний процесса P ). Ниже минимальные процессы относительно ∼ называются про- сто минимальными процессами. Теорема 10. Пусть процессы P 1 и P 2 минимальны, и P 1 ∼ P 2 Тогда P 1 и P 2 изоморфны. Доказательство. Пусть P i (i = 1, 2) имеет вид (S i , s 0 i , R i ), и пусть µ ⊆ S 1 × S 2 – БМ между P 1 и P 2 Поскольку µ −1 тоже является БМ, и композиция двух БМ – тоже БМ, то • µ ◦ µ −1 – БМ между P 1 и P 1 • µ −1 ◦ µ – БМ между P 2 и P 2 91 откуда, используя определение отношений µ(P i , P i ), и определе- ние минимальности процесса, получаем включения µ ◦ µ −1 ⊆ µ(P 1 , P 1 ) = Id S 1 µ −1 ◦ µ ⊆ µ(P 2 , P 2 ) = Id S 2 (4.40) Докажем, что отношение µ является функциональным, т.е. для каждого s ∈ S 1 существует единственный элемент s 0 ∈ S 2 , такой, что (s, s 0 ) ∈ µ. • Если s = s 0 1 , то полагаем s 0 def = s 0 2 • Если s 6= s 0 1 , то, поскольку каждое состояние в P 1 достижи- мо, то в P 1 существует путь s 0 1 - a 1 - a n s Так как µ - БМ, то в P 2 существует путь s 0 2 - a 1 - a n s 0 причём (s, s 0 ) ∈ µ. Таким образом, в обоих случаях существует элемент s 0 ∈ S 2 , такой, что (s, s 0 ) ∈ µ. Докажем единственность элемента s 0 со свойством (s, s 0 ) ∈ µ. Если для некоторого элемента s 00 ∈ S 2 имеет место соотношение (s, s 00 ) ∈ µ, то (s 00 , s) ∈ µ −1 , откуда следует (s 00 , s 0 ) ∈ µ −1 ◦ µ = Id S 2 поэтому s 00 = s 0 По аналогичным соображениям, отношение µ −1 тоже являет- ся функциональным. Из условий (4.40) нетрудно вывести биективность функции, которая соответствует отношению µ. По определению БМ, отсю- да вытекает изоморфность P 1 и P 2 Теорема 11. Пусть 92 • процесс P 2 получается из процесса P 1 удалением недости- жимых состояний, и • P 3 def = (P 2 ) ∼ Тогда процесс P 3 минимален, и P 1 ∼ P 2 ∼ P 3 Доказательство. Так как каждое состояние в P 2 достижимо, то из определе- ния множества переходов процесса вида P ∼ следует, что каждое состояние P 3 тоже достижимо. Теперь докажем, что µ(P 3 , P 3 ) = Id S 3 (4.41) т.е. предположим, что (s 0 , s 00 ) ∈ µ(P 3 , P 3 ), и докажем, что s 0 = s 00 Из определения процесса вида P ∼ следует, что существуют состояния s 1 , s 2 ∈ S 2 , такие, что s 0 = [s 1 ] s 00 = [s 2 ] где [·] обозначает класс эквивалентности по отношению µ(P 2 , P 2 ). Из теоремы 9 следует, что (s 1 , s 0 ) ∈ µ(P 2 , P 3 ) (s 00 , s 2 ) ∈ µ(P 3 , P 2 ) Поскольку композиция любых БМ тоже является БМ, то ком- позиция µ(P 2 , P 3 ) ◦ µ(P 3 , P 3 ) ◦ µ(P 3 , P 2 ) (4.42) является БМ между P 2 и P 2 , поэтому (4.42) ⊆ µ(P 2 , P 2 ) (4.43) Поскольку (s 1 , s 2 ) ∈ (4.42), то, ввиду (4.43), получаем: s 0 = [s 1 ] = [s 2 ] = s 00 В заключение отметим, что • соотношение P 1 ∼ P 2 тривиально, и • соотношение P 2 ∼ P 3 следует из теоремы 9. 93 4.7.3 Алгоритм минимизации процессов Описанный в параграфе 4.6.2 алгоритм можно использовать так- же для решения задачи минимизации конечных процессов, которая заключается в том, чтобы по заданному конечному про- цессу P построить процесс с наименьшим числом состояний, ко- торый сильно эквивалентен P . Для построения такого процесса сначала строится процесс P 0 , получаемый из P удалением недостижимых состояний. Искомый процесс имеет вид P 0 ∼ Множество состояний процесса P 0 может быть построено, на- пример, следующим образом. Пусть P имеет вид P = (S, s 0 , R) Рассмотрим последовательность подмножеств множества S S 0 ⊆ S 1 ⊆ S 2 ⊆ . . . (4.44) определяемую следующим образом. • S 0 def = {s 0 } • для каждого i ≥ 0 множество S i+1 получается добавлением к S i всех состояний s 0 ∈ S, таких, что ∃s ∈ S, ∃a ∈ Act : ( s - a s 0 ) ∈ R Поскольку множество S по предположению конечно, то последо- вательность (4.44) не может неограниченно возрастать. Пусть S i – тот член последовательности (4.44), на котором эта последова- тельность стабилизируется. Очевидно, что • все состояния из S i достижимы, и • все состояния из S \ S i недостижимы. Поэтому множеством состояний процесса P 0 является множество S i Пусть S 0 - множество состояний процесса P 0 . Заметим, что при вычислении отношения µ(P 0 , P 0 ) требуется вычислить не бо- лее чем |S 0 | членов последовательности (4.33). Это верно потому, 94 |