Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 24
Текст из файла (страница 24)
Таким обра- зом, мы убедились в том, что 6(1'1, + 1) 6(6,) тогда н только тог- да, когда не существует таких х,, ..., х„, для которых Р(х„..., х„) = О, б. Итак, для определения того, что уравнение Р(хь хз, ..., х„) = = 0 имеет решение, необходимо показать только, что не вьпюлня- ется 6Я«+ 1) 6(Я,). 5.5.2. Слабое аычисление Теперь нам необходимо показать, что сети Петри могут (в определенном смысле) вычислять значение полннома 6(х,, хм ..., х„). Мы осмотрительно ограничили полином Я до неотрицательных значений полинома, неотрицательных коэффициентов и неотрицательных значений переменных.
Это позволяет нам представить значения переменных и значение полинома числом фишек в позициях сети Петри. Общая схема показана на рис. 5З. Входные значения х,, ..., х„(представляются х; фишками в ос для с =- 1, ..., и. Первоначально фишка помещается также,в позицию «действиям Выполнение сети будет закончено помещением фишки в позицию останова.
В это время «выходная» позиция будет иметь д фишек, где р < < 9(хо ..., х„). Эта сеть Петра слабо вычисяявлт значение 6(хо ...., х„). Слабое вычисление означает, что вычисленное значение не будет превышать аахм ..., х„), но может быть любым (неотрицательным) значением, меныпнм Я(хо, х„). Слабое вычисление обязательно для сетей Петри вследствие рпзресиави(гй природы запусков переходов: сеть Петри нельзя заставить остановиться. При определении графа полинома 6Щ) зто особенно учитывалось. Сейчас мы хотим показать, что можно построить подсеть, слабо вычисляющую функцию умножения (двух чисел).
На ее основе мы можем построить составную сеть, которая слабо вычисляет значение каждого члена полинома путем последовательной композиции подсетей умножения. Выход подсети для каждого члена будет 134 помещаться в выходную позипию для полинома. Таким образом, число фишек в выходной позиции будет суммой выходов для каждого члена. Подсеть умножения показана на рис. 5.10. Эта сеть слабо вычисляет произведение чисел х н у, представимых фишками в ее входных позициях, помещая множество фишек в свой выход.
Действует сеть совсем просто. Для вычисления произведения х и у 4~ейглтЖР ЮхатзтнФ Рис. бхк Базовая структура сети Петри, слабо вычислназщей значение полн- нома Я(х1, хз, ..., ха). сначала запускается переход 1„перемещая одну фишку нз р, в ра. Эта фишка разрешает запуск перехода 1а, который может теперь копировать у фишек из позиции рв, помещая их в лз и вкладывая в выходную позицию р „у фишек. Теперь можно запустить |а, возвращая фишку из ра в рь Это разрешает запуск 1,, который копирует у фишек из ра обратно в р„. Весь этот процесс можно повторить точно х раз, помещая каждый раз в р, „у фишек.
После этого маркировка р становится нулевой н сеть останавливается. Общее число фишек в позиции р „ равно произведению х и у. Мы описали наилучший случай в том смысле, ото число выходных фишек в точности равно х у. Однако фишка в р„разрешает и переход 11 и переход 1,, а переход 1, можно запустить до того, как все у фишек будут скопированы из р„в ра н добавлены в р, а. В этом случае число фишек„помещенных в р „, будет меньше,чем х . у. Поскольку 11 можно запустить не более у раз для каждого запуска г„а 11 можно запустить не более х раз, мы можем гарантировать, что число фишек в р„„никогда не превысит х ° у, но вследствие разрешающей природы запусков переходов мы не можем гараичи- Сложность н разрешимость 135 рь.у дллгол Рнс.
б 1О. Подсеть уииожителя. Эта подсеть слабо вичнсляет произведение л н у. ровать, что число фишек в Р„„будет в точности равно х д; опо может быть меньше. Следовательно, зтасеть Петри слабо вычисляет произведение х и у. Теперь для того, чтобы слабо вычислить член Яь являющийся произведением ас хи - х„° ... ° х,, построим сеть Петри показанного на рис. 5.11 вида. Поскольку каждая подсеть слабо вычисляет произведение двух членов, вся подсеть слабо вычисляет значение члена 1сь Далее на рнс. 5.12 показано, как можно слабо вычислять полипом Р =- Р~ —' ,лез+ ... + Рь. Каждая подсеть имеет внд, изображенный на рнс. 5.11, и слабо вычисляет значение одного члена полинома.
Выходы А подсетей для отдельных членов объединяются вместе, давая общее значение суммы. Теперь для создания конкретных необходимых множеств достижимости вводится несколько управлякяцих переходов и позиций. Сначала необходимо обеспечить получение произвольного значения для каждой нз переменных (хь ..., хв) н запись зтого значения в (з 1~ 13Б Глана 5 Ел~хо~У ахи хв '' х 1 хх Рнс. 5.11. Сеть Петри, слабо вычисляющая член днафантова уравнения.
Каждый блок в сети имеет внд, изображенный на рнс. 5.10. позиции ры ..., р„. Для каждой р~ создается переход 1~ с пустым входом и выходами в р; и всякую позицию, являющуюся входом, соответствующим х, в члене Ят, использующем х,. Следовательно, в полиноме л, + х,хя мы должны иметь переход 1а с выходами в р, и во входы х, в двух членах х, и х,х„используихцих х,; 1, будет иметь выходы в рз и во вход ха в члене х,х,. Эти переходы могут запускаться произвольное число раз, созданая любые значения в р„..., р„.
Следовательно, для всякого у ( < Р(хы ..., хв) Достижима маРкиРовка Р, с Р(Р,) = х„..., 1х(Р„) = = хв и р(выход) = у. Значение у = Р(х„..., хв) может быть достигнуто сначала запуском х, раз перехода 11, помещая х, фишек в ро затем запуском хя раз перехода 1я и т. д., пока не будет запущен хв раз переход 1„. Далее можно выполнить подсеть для каждого члена Я, полинома, в результате чего значение полииома помеслится в выходнуо позицию. Сложность и раареижиость Рис. 5Л2. Сеть Петри, слабо вычпслязощая Р(ж, ле, ..., л„иугев исиольаоваиия иабора подсетей вида, изображенного иа ргзс. 5.!1. Для сведения задачи включении графов полиномов к задаче подмножества выполнив следукицие шаги.
Пусть мы хотим определить для полиномов А и В, выполняется ли б(А)~ б(В). 1. Построим сеть Петин С„, слабо вычисляющую А(х„, х„), и сеть Петри Си, слабо вычисляющую В(хь, х„). 2. Если число позиций в этих сетях не равно, добавим позиции в ту сеть, где их меньше с тем, чтобы уравнять число позиций. Эти позиции не имеют начальной маркировки н не связаны с какими- либо переходами в сечи. 3. Теперь мы должны устранить влияние всех внутренних позиций на множества дсстижимости И в С„, и в Си различимо множество из п + 1 позиций — и позищзй, соответствующих значениям х,, ..., х„, и (и+ 1)-я позиция, соответствующая выходу каждой сети Все другие позиции являются внутренними, маркировка их 138 Глава в Выход д Внутренние позиции Рз ° - .Р» у<А(хз,...х„) Некоторая произволь- ная маркировка х,...х„ и' Внутренние позиции Выход Р1-.
-Рз Некоторая произволь- ная маркировка хт . . .х„ у кВ(х„ ...,х») у~В(хз, . ,х„) Произвольная марки- ровка Н Одну фишку. — Прил. перев. з) Г н д' не считаются внутренними. — Прим. перев. неважна. Однако может оказаться, что .пля внутренней позиции р, в С„н соответствующей позиции р; в Св существуют неравные маркировки р, в тт(С», р„) н р' в Я(Сп, р,и), поскольку р(рД ~ ть (ь"(р~') для всех (з в Я(Си, рп). Для того чтобы обойти это препятствие, введем по две новые позиции: (т и г в С,„(получая Сл) и и' и г' в С„(получая Сп). В Сл позиции д и г не связаны с переходами и первоначально г пуста, а д имеет одну фишку.
Позиция г' в Сп служит позицией «действияз. Она получает начальную маркировкуп, а каждый переход модифицируется с тем, чтобы включать г' в качестве входа и в качестве выхода. Следовательно, пока фишка остается в г', сеть Сп может функционировать, как и прежде. Введем в Сн новый переход, переводящий разрешающую фишку из г' в д', запрещая все переходы Сп и «замораживая» маркировку.
Теперь для каждой внутренней познцтпР введем по два новых перехода. Один из зтих переходов, вводимых для каждой внутренней позиции Ро маРкиРовка котоРой неважна, имеет в качестве входов позиции д' н Р,, а в качестве выхода — только д' (уменьшая при запуске на! маркировку вРД, другой переход в качестве входа имеет д', а в качестве выхода и д', и р; (увеличивая при запуске на 1 маркировку в РД. Эти переходы благодаря соответствующей последовательности прибавляющих илн убавляющих запусков обеспечивают каждой внутренней позиции возможность иметь произвольную маркировку.
4. Описанная конструкция показана на рис. 5.!3. Для двух сетей Петри Сл и Св с начальной маркировкой рл и )ьп соответственно, 6(А) ы 6(В) тогда и только тогда, когда Й(Сл, рл) ш Й(Св, (ьв). Сл и Сь имеют следующие множества достижимости: Сложность и ралреансиость с„' Рис. 5.13. Сеть Петри, построенная для проверки включения трафоя полиномов. Следовательно, если 6(А)ы 6(В), то )т(Сл, )сл)ы гг(Св, рз) и, обратно, если К(Сл, рл)ы Д(Са, рз), то 6(А)ы 6(В).
Таким образом, мы показали справедливость следующего. Теорема 6.9. Задача включения графов полиномов сводима к задаче подмножества для множеств достижимости сетей Петри. Доказательство взято из П14, Пб). 5.5.3. Задача равенства Теперь нам осталось только показать, что задача подмножества для множеств достижимости сетей Петри сводится к задаче равенства. Предположим, что имеются две сети Петри А и В, и мы хотим определить, выполняется ли Я(А, р„) = 1ч(В, )сп) (задача подмно- 1 жества).
Покажем сейчас, что можно определить такие две сети Петри .0 и Е, что Е(А, и„) ы Е(В, рл) тогда и только тогда, когда Й(В, рп) = й(Е, рв). Основой построения доказательства служит тот факт, что Я(А, рл) ы Й(В, ри) тогда и только тогда, когда )г(В, р ) = 1~(А, р„) (1Е(В, р ). 1т и Е строятся из общей подсети С. Сеть С представляет мно- жества достижимости А и В для получения их обьедннення. Кои- ыо Глава Б Рис. 5А4. Построение сетей Петри С, лз н Е из А и и, используемое "для доказательства сводимости задачи подмножества для множеств достижимости к задаче равенства. струкция иллюстрируется рис. 5.14. Позиции р„..., р дейсзву1от илн как позиции сети А, нли как позиции сети В.
Первоначально они не имеют маокировкн. Вводятся две новые позиции гл и гв, служащие позициями действия для сети А и сети В соответственно. Все переходы сети А модифицируются с тем, чтобы включать в качестве входа и выхода гл, а все переходы сети В модифицируются с тем, чтобы включать в качестве входа и выхода гв.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
