Введение в архитектуру компьютеров


Здесь: – переход; O – место - часть 3


Сети N1 и N2

называются эквивалентными (N1~N2), если Ll (N1) = Ll(N2). Говорят, что класс сетей ?1 мощнее класса ?2 (?2 Í?1), если  для любой N2Î?2 существует N1Î?1 и N1~N2. Классы сетей ?1 и ?2 называются эквивалентными (?1~?2), если ?1Í?2 и ? 2Í?1.

Известно, что структурированные сети, приоритетные сети, сети с переключателями и дизъюнктивными правилами, ингибиторные сети эквивалентны. Докажем, что введенные здесь ПМ-сети обладают не меньшими выразительными способностями, чем отмеченные выше классы. Обозначим ?(И) – класс ингибиторных сетей, ?(ПМ) – класс ПМ-сетей.

Теорема. Имеет место следующее значение ?(И)Í?(ПМ).

Для доказательства необходимо показать, что по любой N1Î?(И) можно построить эквивалентную сеть N2Î?(ПМ).

Пусть N1 – ингибиторная сеть с начальной разметкой M0 и помечающей функцией s. Разобъем сеть N1 на n фрагментов (n – число мест в сети N1), каждый из которых включает одно место и переходы, инцидентные данному месту. Обозначим pk = {t|H(t, p)>0};

 – множество переходов, для которых pk является входным местом, причем между pk и этими переходами не существует ингибиторных дуг;
 –
множество переходов, для которых pk является входным местом и существуют ингибиторные дуги между pk

и данными переходами.

Для каждого фрагмента ингибиторной сети будем строить эквивалентный фрагмент ПМ-сети. Если исходный фрагмент не содержит ингибиторных дуг, то он остается без изменений. Если же некоторый k-й фрагмент включает хотя бы одну ингибиторную дугу, то выполняются следующие построения. В новом фрагменте будут соответственно те же переходы и то же место, что и в исходном, по-другому задаются связи между ними и разметка места.

1. Если в исходном фрагменте переход tÎ*pk, то в новом фрагменте каждой исходной дуге из t в pk будут соответствовать две дуги, ведущие из t в pk и помеченные плюсом.

2. Если в исходном фрагменте переход

 то в новом фрагменте строим минус-дугу из pk в t и минус-дугу из t в pk.




Начало  Назад  Вперед