5.5.3. Задача равенства

Теперь нам осталось только показать, что задача подмножества для множеств достижимости сетей Петри сводится к задаче равенства.

Предположим, чіо имеются две сети Петри Л и В, и мы хотим определить, выполняется ли R{A, |Aa)s R(B, |ів) (задача подмножества). Покажем сейчас, что можно определить такие две сети Петри D и Е, что R(A, цА) е R(B, р,в) тогда и только тогда, когда R(D, рс) = R(E, (if). Основой построения доказательства служит тот факт, что R{A, уА) <= R(B, рБ) тогда и только тогда, когда R(B, М = R(A, цА) U R(B, рв).

D и Е строятся из общей подсети С. Сеть С представляет множества достижимости Л и В для получения их объединения. Кон-

струкция иллюстрируется рис. 5.14. Позиции ри ..., рп действуют или как позиции сети А, или как позиции сети В. Первоначально они не имеют маскировки. Вводятся две новые позиции гА и гБ, служащие позициями действия для сети А и сети В соответственно. Все переходы сети А модифицируются с тем, чтобы включать в качестве входа и выхода гА, а все переходы сети В модифицируются с тем, чтобы включать в качестве входа и выхода гБ.

Далее вводятся еще одна позиция s, и два новых перехода, tA и tB. Начальная маркировка всей сети (включая А и В как подсети с общими позициями; позиции гА, гв и s; переходы tA и tB) определяется одной фишкой в s и нулем в остальных. Переход tA имеет в качестве входа s, а выход его порождает начальную маркировку сети А плюс фишку в гА\ переходов в качестве входа также имеет s, а выход его создает начальную маркировку сети В плюс фишку в гв. Следовательно, если запустится tA, то подсеть А приобретает