Книжка по сетям Петри, страница 7

Суигастеует алгоритм, с помощью которого можно установить для произвольного вектора М Е (чч, и для проиэволыюго переходе т в сети Петри с п местами, яеллетсл ли вектор М т-тупиковым. Д о к а з а т е л ь с т в о. Заменим в сети )У начальную разметку Мь на разметку М, после чего построим полное покрывающее дерево для полученной сети с начальной разметкой М, являющейся корнем этого дерева. Ясно, что М вЂ” г-тупиковый вектор тогда и только тогда, когда построенное полное покрывающее дерево не содержит дуги, помеченной символом г. П Следующие теоремы легко доказать, исходя из основных свойств (пол.

ных) покрывающих деревьев. Т е о р е м а 2.б. Проблема безопасности се)ад Патри разрешима. (Сеть с и местами безопасна, если и только если все вершины ее покрывающего дерева представляют собой векторы из множества ( О, 1)", т.е. векторы составленные из О и 1) . Пример безопасной сети дан на рис.

2.4. Теорема 2.6. Проблема потенииальнод живости переходов разрешима. (Переход г потенциально живой, если и только если он метит некого. рую дугу в полном покрывающем деРнс. 2тд реве сети хотя бы адин раз.) Т е о р е м а 2Л. Сущестеуег алгоритм, с помощью которого можно узнать, получи тли денное место в сети хотя бы одну (дишк у: (Если хотя бы в одной вершине покрывающего дерева позиция. соответствующая месту р, содержит число и > О, то место р может получить фишку в процессе функционирования сети.) Т е о р е м а 2.8. Сущестеуег алгоритм, с поающью которого можно узнать, может ли данкыд переход сработать сколь угодно большое число раз. (Достаточно присоединить к данному переходу новое "висячее" выходное место р и затем выяснить, является ли оно неограниченным.) 5 2.3.

Проблемы гт-включеннл н М-эквнвалентностн Обе проблемы не являются разрешимыми. Доказательства были проведены Рабином (не опубликовано) и Хаком [43, 46) сведением 10-й проблемы Гильберта к рассматриваемым проблемам. Неразрешимость 10 й проблемы была установлена Матиясевичем [11) . Проблема Гильберта формулируется следующим образом: существует пи алгоритм, с помощью которого можно выяснить, имеет ли попиком 0(х,,..., х„) с целыми рациональными коэффициентами целое рациональное решение, т.е, существует ли вектор чисел (у,,..., у„) такой,что г(у,,...,уч) =О? Метод сведения состоит в том, что устанавливается такая связь между решенной и решаемой проблемой, при которой допущение о разрешимости решаемой проблемы приводит к разрешимости проблемы, о которой известно, что она неразрешима.

В сведении Рабина и Хека используется промежуточная проблема включения графов полиномов, в которой рассматриваются полиномы с целыми неотрицательными коэффициентами. Эта проблема состоит в следующем. Пусть е (О обозначает множество ( (хы..., х„, г) Е (цп+~ ) г < У(хы..., х„)) . Можно ли для двух произвольных полиномов Р, и гз с одинаковым числом переменных выяснить, имеет ли место включение ()(Р, ) ~ д(уз)? Сведением проблемы Гипьберта к данной проблеме показано, что последняя неразрвиима [45) . Дпя сведения проблемы включения графов полиномов к проблемам В-включения и Я-эквивалентности Рабин предложил использовать сети в качестве абстрактных машин, "слабо вычисляющих" полиномы.

Машина слабо вычисляет полипом Р (х,,..., х„), если для произвольного "входного" вектора чисел (у,,..., у„) результатом на "выходе" машины может быть любое число г такое, что О <г < У(у,,..., у„) . Это означает, что машина недетерминирована в том смысле. что вместо единственного результата, однозначно определяемого входным вектором (у,,..., у„), она может выдать любой из векторов, не превьниающих Р(у,,..., у„) .

Недетерминированность разупьтата работы машины отражает недетерминированность функционирования сети Петри. Конечная сеть (Р, Т, Р, гУ), "слабо вычисляющая" полипом г (х,,...,х„), должна удовлетворять следующим условиям: 1) в ней выделены л "входных" мест (п,,..., )п„, кахщое из которых сопоставлею соответствующему аргументу полинома, и одно "выходное" масте оит; 2) для Управления работой сети вьщелены специальные места: "стартовое" оп и "выключающее" оН; 3) произвольному вектору у Е Э) Я можно сопоставить начальную размет- куМ такую,что Мх(оп) 1 )г!' 1 ~(~п' Мгбп() уг все остальные места имеют нулевую разметку; 27 ! хех, \ Х, Хр, Рнс. 2.а. 4) для любой разметки М, достижимой в сети (Р, Т, Р, Иг, М„), М(оц!) < г (у!,....

у„); б) для любого целого )г, 0 <х < г (у„..., у„), существует достижимая в сети с начальной разметкой Мх тупиковая разметка М такая, что М (сит) = д, м(о(т) 6 работах (46, 46) показано, что дпя любого полинома с неотрицательными коэффициентами можно конструктивно построить слабо вычисляющую его сеть. Опуская технические детали доказательства, представим только его идею. Полином г (х,, ..., х„) является конечной суммой адночленов вида х Х Ь! (х!,..., х„) .

где й! (х„..., х„) представляет собой произведение )= ! и! и.„ с~ х, ... х„с неотрицательным козффициентом с!. Таким образом, чтобы построить сеть, слабо вычисляющую полипом, нужно уметь моделировать сетями умножение и сложение неотрицательных чигк сел, умножение на константу, 1 сравнение на равенство и суперпозицию сетей. На рис.2.6,а и б и 2.6, а показаны сети. слабо вычисляющие сумму а) х, + х,, произведания х, х, и с х. На рис.2.6,бпоказана сеть, слабо вычисляющая одно.

щ-и, !з1 м( ... гв гю„' член с ° х, ... ° х„. Эта сеть представляет собой комбина. цию сетей, представленных на рис. 2.6 и 2.6, а. Сеть, слабо вычисляющая полипом с х м)г!д '"' '"",и'и!" одночленами, строится как суммирующая комбинация се- тей, типа построенной на рис. 2.6, б (суммирование Ф аь-м ) згг-!!4 слагаемых обобщеет пример на рис. 2.6, а) . зн . г.е 24 Л а м м а 2.3. Дл» любого лг лолинома Г(х,, ..., кч) с неотрицательными целыми коэффициентами мам»о лосгрои гь сеть Петро И такую, что У(П = = Я„(И), где д(г) — граф лолинома С а Яч(И) — множество проекций векторов из Я(И! на их первые л + 1 координату. Ю тл (Множество проекций В„(И! = рнс.

Зл, = (М(Р„, ~ )(МЕЯЧЧ)), гдарч+1 вектор, составленный из первых л + 1 координат вактора мест Р, и л ~ <А =(Р!), Д о к а з а т е л ь ст во. Основой для построамия сети Петри Ислужит сеть Иу, слабо вычисляющая полином Л. К атой сети добавляются переходы Ге, Г,,..., Г„И МЕСта Р,, Рз,..., Р„. МЕСТУ ОЦ1СЕтн Иг ПРИСВанаавтСЯ МО- вый символ рн~,.

Дуги связывают добавленные места и переходы друг с другом, а также с входными местами Ьы ..., М„и местом оп сети ИЛ так, как показано на рнс. 2.7. Место ре имеет разметку Ме (ре) 1. Стартовое место оп сети ИЛ получает фишку после срабатывания перехода ге. Однако до зтого момента могут сработать любые из переходов ты..., г„ произвольное число раз каждый, пареслев во входные места (и,,.... (и„ и дополнительные места р,,...,р„соответствующее число фишек. Таким образом, к моменту, когда стартовое место оп помучает возможность запустить в работу сеть ЛП каждое входное место )пг, 1 <г' ~л, имеет разметку М(»п~), каждое место рь 1 <! Сл, имеет разметку М(р1» и Мбп;) "М(р~).

8 процесса дальнейшей работы сети ЧМ ЕВ(И): 0< чМ (Рч+1! ~ г(М(Р1). ° ° °, М(Р ) ) ° Следовательно. проекции достижимьп разметок на места Р ы..., Р„, Р„+ ~ образуют множество Вч(И! = ()(г). Е) Т е о р е м а 2.9. Проблема В-включения неразрешима. До к а за тельство.

Для двух произвольных полиномов л ил содинаковым числом переменных л можно построить сети Петри И и И такие, что (г(П й у(Л! ч В(И) ь. Я(И') . Пусть ИЛ и Из — сети, слабо вычисляющие полиномы г и соответственно Л, причем, р(Г) =В„(ИЛ) и Р(Л) Я„(Из! (см. лемму 2.3) . Если первая сеть имеет Л мест, а вторая (, то число мест в обеих сетях можно уравнять, добавив ! Л вЂ” ( ! мест в сеть с меньшим числом мест.

Чтобы зти места не изменили множество достижимых разме. ток, начальмая разметка каждого из них полагается равной О,они не связываются дугами ни с одним иэ переходов сети и добавляется новый (мертвый! переход, для которого они являются входными местами. Сети И и И строятся по сетям Иу и Иь (одна из них имеет дополнительные места! так, как показано на рис. 2.8. Сети Иу и Иа представлены прямоугольниками, в которых показаны все их переходы и места, но не указаны связывающие их дуги. 8 каждую из сетей добевляются места Р„,1 И Р„З, ГДЕ Г=ГПах(г,(!. К сети ИЛ Добавлен также переход ге, который никогда не сработает, позтому разметка мест р, +, и р, +з постоянна в сети М К сети И„добавлены новые переходы, место р„„является входным и выходным дЛЯ всех переходов сети Иь, переходы Гг и Г,, где л + 1 < .ч(<г, связаны с макетами р,',+,,...,р,' так.

как показано на рис. 2 8. Пока переход гч не сработал и не перевел фишку из места р, +1 в рг+з, сеть И функционгйгует точно так же, как и сеть Иь. После срабатывания ге 2З ни один из переходов сети (уа не может сработать и размет. ка мест р1,..., р„не может измениться. В то же время "новые" переходы гг и г,', л + 1 < У < г, могут произвольным образом изменять разметку мест р„,,,..., р,. Если вектор ХЕ йл и вектор УЕ й' ",гдел~г,то через 2' будем обозначать "конкатенацию" векторов Х и У, т.е.

вектор х Е й', первые л компонент которого совпадают с Х, а комяонанты с (л+ 1) й по г-й совпадают с компонентами вектора У. Если (à — множество векторов Рмс. 2.8. из й", а У вЂ” множество век- торов из йл ', то через УХ У будем обозначать множество попарных конкатенаций векторов из ()и У. Из анализа функционирования сети ДГ следует, что Я(д(') - Я()У„) Х (П, О) ) н Я„(аь) Х й™ Х((О, П) . Из анализа функционирования сети (У следует, что Я(Д() Я(Л(г) Х ( (О, 1)) Таким обРазом, Я((У) ~ Я(М ) «» Я()УГ) С Ял(Щ,! Х (У™, ПРаваЯ часть эквивалентна отношению Яч(д(г! ь.

Яч()уь) . Следовательно, Я()У) а Я(Д( ! Я„(Ц) а Я„(ал) . Это означает, что для решения проблемы включения графов двух произвольных полиномов г и Ь достаточно построить сети Лlг, Д(», Д( )У, убедиться, имеет ли место включение Я ВУ) ь, Я (д) ), на основании этого сделать заключение о том, имеет ли место Яч (Фг) ь. Ял ()Уа), и ма основании леаамы 2.3 установить, содержится лн д(у) ад (И) . Таким образом, если предположить разрешимость проблемы включения для множеств достижимых разметок сетей Петри, получаем разрешимость проблемы включения тра.

фов полиномов с неотрицательными коэффициентами, что не верно. С) Т е о р е м а 2.10. Проблема Я.эквивалентности неразрешима. Д о к а з а т е л ь с т во. Для доказательства: .разрешиыости методом сведения достаточно показать, что проблема Я-включения сводится к проблеме Я-зквивалентностн. Это означает, что нужно указать способ, с помощью которого для любых двух сетей А и В можно построить сети А и В такие, что Я(А) й Я(В) «=«Я(А ) = Я(В ) .