Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 23
Текст из файла (страница 23)
Эта конструкция иллюстрируется рис. 5.6. Далее„если маркировка 1> с р(р ) = О достижима в Р(С» ре), тогда С, также может достичь этой маркировки в позициях Р, путем выполнения той же самой последовательности запусков переходов. Затем можно запустить з„замораживая подмножество С» Поскольку р(р;) = О, з«запустить нельзя и С, пассивна. Таким образом„если ре может стать нулевой — С, неактивна. Справедливо обратное, если С, неактивна, тогда должна быть Главк 5 ав Рис. 5.6. Конструкция, переводящая задачу достижимости нуля в одной позиции (достижима лн маркировка с и(рД = О?) и задачу активности (яаляетсн ли сеть активной?).
достижима маркировка (с с р(г,) = О, из которой недостижимо состояние с фишкой в г . (Если в г есть фишка, то за разрешен, а повторно запуская з, достаточное число раз, можно разрешить любой (илн все) переход, т. е. сеть активна.) Если г, не имеет фишек и не может их получить, тогда маркировка р; также дсижна быть нулевой.
Таким образом, если 6а неактивна, тогда достижима маркировка, в которой маркировка р; нулевая. На основе втой конструкции мы доказали следующую теорему. Теорема 5.5. Задача достижимостн сводится к задаче активности. Для доказательства основного утверждения раздела покажем следующее. Теорема 5.6 Задача активности одного перехода сводится к задаче достижнмости. Сложность и Розреюомость !29 Доказательство того, что задача активности одного перехода сводима к задаче достижимости, опирается на проверку достижимости любой из конечного множества лииссииалоных пассивных для 1~ подларкировок.
Сеть Петри не активна для перехода 1; тогда и только тогда, когда достижима некоторая маркировка, в которой переход 1~ не запускаем и ие может стать запускаемым. Маркировка такого вида называется пассивной для 1;. Для любой маркиРовкн 1ь можно пРовеРить, ЯвлЯетсЯ ли она пассивной ДлЯ 1г построением дерева достижимости с корнем р и проверкой, можно ли Рис. 5.7. Сеть Петри, иллюстрирующая пассивные иерккровки для Ф.. где-либо в дереве запустить переход 1я Если нельзя, то )ь массивна для 1~. Проверка активности 1; в таком случае требует проверки достижимости какой-либо пассивной для 8~ маркировки. В общем случае, однако, может существовать бесконечное число пассивных для 1; маркировок и бесконечное множество маркировок, в котором находятся пассивные для 1т маркировки. Заметив два свойства, сведем множество маркировок, которые необходимо проверить,пля достнжимости, к конечному числу. Во-первых, если маркировка р, пассивна для 1ь то и любая маркировка 1«' ( р пассивна для 1о (Любая последовательность запусков, возможная из )ь', возможна также из 1ь, поэтому если )ь' может привести к запуску 1~, то это может и )ь.) Во-вторых, маркировки некоторых позиций не будут влиять на пассивность для 1~ данной маркировки, поэтому маркировки этих позиций являются «несущественными», они могут быть произвольными.
Заимствуя прием из построения дерева достижимости, заменим «несущественные» компоненты на ю, показывая, что в этпх позициях может быть произвольно большое число фишек, не влияющих на пассивность маркировки для 1я Теперь, поскольку любая 1ь' «= )ь пассивна для 1я если р пассивна для!в намненужно РассматРивать позиции Р; с )ь(Рт) = со. Это означает, что мы пРименяем задачу достижимости подмаркировки с Р = (р|КРь) + то). Рассмотрим в качестве примера сеть Петри на рис.
6.7. Маркировки (2, 0), (1, 0), (О, 0), (О, 1), (О, 2), (О, 3),... являются пассивными для 1«, но их можно представить конечным образом множеством ((2, 0), (1, О), (О, то)). Хэк (!13, 116! показал, что для сети Петри С существует такое конечное множество Р, маркировок (расширенных, т. е. включаю- 5 — 552 щих св), что С активна тогда н только тогда, когда никакая маркировка из Р, недостижима. Если маркировка из Р, содержит а, тогда подразумевается достижимость подмаркировки. Более того, Р~ можно эффективно вычислять. Поскольку Р, конечно, не.сз-компоненты имеют верхнюю границу Ь. Граница Ь определяе1ся как такое наименьшее число, что если пассивна для 1х любая маркировка р, такая, что р(р;) ( Ь + 1 для всех рь то является пассивной для 1~ и подмаркировка р', такая, что '(р;) =- р(р;), если р(йч) ( Ь, и р'(р;) = сз, если р(р;) == Ь+ 1.
ри таком определении Ь можно построить Р, следующим образом. 1. Вычислить Ь. Начать с Ь =. О, увеличивать Ь до тех пор, пока не окажется, что Ь удовлетворяет описанному определению границы. Проверка каждого Ь требует проверки всех (Ь + 2)" маркировок с компонентами, меньшими илн равными Ь -'; 1. 2. Вычислить Р, проверкой всех маркировок н подмаркировок с компонентамй, не превышающими Ь илн равнымн м.
Р, — это множество пассивных для ~ - маркировок нз множества (Ь + 2)" маркировок Построив Р„можно рассматривать задачу достижимости подмаркировки для каждого элемента Рг Если какой-либо элемент Р, достижим из начальной маркировки, сеть Петри неактивна, если же никакой элемент Р, недостижим — сеть Петри активна.
Из доказанных теорем мы получаем следующую. Теорема 0.7. Следующие задачи эквивалентны: 1. Задача достижимости. 2. Задача активности. 3. Задача активности одного перехода. Более формальные доказательства сводимости активности к достижимости можно найти в 1113, 1161. $.5.
Неразрешимые задачи В предыдущем разделе мы показали, что многие задачи достижимости и активности эквивалентны, но никакого результата относительно разрешимости этих задач еще не получили. Для того чтобы показать разрешимость, необходимо свести задачу для сетей Петри к задаче с известным решением, а для того, чтобы показать неразрешимость, нужно свести задачу, которая известна как неразрешимая, к задаче для сетей Петри. Первый важный результат такого рода был получен Рабином (261.
Он показал неразрешимость задачи: выполняется ли )с(Сь )с1) — Р(С„р~) для двух сетей Петри— С, с маркировкой р, и С, с маршировкой р,? Позднее Хэк (1141 показал, что неразрешимой является и задача: выполняется ли )с(С» рч) = )((См рз)? Доказательство этих утверждений основано на десятой проблеме Гильберта. (Д. Гильберт на конференции математиков в 1900 г. поставил 23 проблемы, и та, на которую опирался Хзк, была десятой в списке) Сложность и разрешимость Определение 5.9.
Дан полипом Р от и переменных с целымн коэффициентами; существует ли такой вектор целых (х,, х„..., х„), что Р(х,, х„..., х„) =- 07 Уравнение Р(х„х„, х„) = 0 называется дно фон лювыж. В общем оно представляет собой сумму членов: Р (хм х„..., х„) = „"1', й, (х, х„..., х„), ч Й; (х„х„..., х ) = а . х ° х ° ... ° х, . а а '" з Десятая пробамо 1ильбарта Задача илючения обаров полиномоб | Задача подмножестби дня множеств достажимасти сотом Попри Задачи рабспстба мномостб достажимости сетей Подопри Рис. Ъ.8. Снвдйнип, покззьшзющие, что задача равенства (и подмножестнз) дпя„мно коста досгнжкмостп сетей Петри нерззрвшпмз.
Днофантовымн уравнениями являются х, = — О; Зх, хз + бхз —— = О н т. д. В 1970 г, Матиясевичи доказал, что десятая проблема Гиль- берта неразрешима [70, 71): не существует ойцего алгоритма, определяющего, имеет лн произвольное диофантово уравнение корень (набор значений, для которых полипом равен нулю). Этот результат служит основой доказательства того, что задача равенства множеств достижимости сетей Петри неразрешима.
Стратегия его заключается и построении для днофантоиз полинома сети Петри, которая (в определенном смысле) вычисляет все значения поли- нома. 5.5.1. Задача включения графов полиномов Доказательство неразрешимости задачи равенства состоит из ! трек частей (рис. 5.8). Сначала десятая проблема Гильберта сводится к задаче включения графов лопиножвв. Затем задача включения 1) Советскпй мзтемзтнк. — Прим. пери. зч 332 графов полиномов сводится к задачи псдлгножвства длл множеств дсстижимости сетей Петри.
Наконец, задача подмножества для множеств достижимости сетей Петри сводится к задаче равенства иножвппв достижимости сетей Петри. Это показывает, что десятая пробпема Гильберта, известная как неразрешимая, сводится к задаче равенства, которая поэтому также должна быть неразрешимой. Определение 5.10. Грагр 6(Р) диофантова полинома Р(хь ..., х„) с неотрицательными коэффициентами — это множество О(Р) = ((х„..., хн, у)~ у ~ Р(х„в ..., ~„1 О а- х„..., х„, у). Определение Б.! 1.
Задача внлгсченил графов полинолгов заключается в определении для двух диофантовых полиномов А и В, выполняется лн 6(А) с: — О(В). Покажем сначала, что десятая проблема Гильберта сводится к задаче включения графов полиномов. Теорема 5.8. Задача включения графов полиномов неразрешима. Доназапгвль ство: 1. Ограничим наше доказательство задачами с неотрицательными решениями.
Если (х„..., х„) — решение для Р(х„..., х„) =- = О с х; ( О, то (х„..., — хь ..., х„) решение для Р(х„..., — х„..., х„) = О. Следовательно, для определения того, является ли (х„ ..., х„) решением произвольного полнномап, необходимо толь- ко проверить каждый из 2н полиномов, получающихся в резуль- тате изменения знака у некоторого подмножества переменных для неотрицательного решения. 2. Аналогично, поскольку Р'(х„ ..., х„) = О тогда и только тогда, когда Р(х„ ..., х„) =- О, необходимо рассматривать только поли- номы, значения которых неотрнцательны. 3. Сейчас можно разбить любой полипом Р(х„хн, ..., х„) на два полинома, Я,(х„..., х„) и Ят(хь ..., х„), такие, что Р(хь ..., х„) = = Ихь "., х„) -- ггмхм ..., х„), помещая все члены с положи- тельными коэффициентами в От, а все члены с отрицательными ко- эффициентами в Яа.
Далее, поскольку Р(хь ..., х„) ~ О (по и. 2), имеем, что Щх„..., х„) ъ <;е(хо ..., х„) и Р(х„... х„) = О тогда и только тогда, когда О,(хь ..., х„) = Он(хь ..., х„). 4. Рассмотрим два графа полнномов: О (Я,) = ((х„..., х„, у) (у в= Я, (хм ..., х„)), О(Яд+1) = ((хь -' хнт у)!у»~1+~2а(х.- ~ хи)).
и То есть допускающего рещение с отрииательиыми нначенннии перемеиннх. — Прим. нерва. Сложность и разрешимость Теперь 6(Я«+ 1) 6(6т) тогда и только тогда, когда для всех неотрицательных х,, ..., х„н у из у < 1 + (~з(хо ..., х„) следует, что у< 0,(хо ..., х„). Это справедливо тогда и только тогда, когда не существует х„..., х и у, таких, что Я, (хп ..., хи) < у < 1 + 9з (хп ..., х„). Но нз и. 3 следует, что 1~, '.э. ~„~з, поэтому ~, (х„..., х„) < у < 1 + ~з (х„..., х„) < 1 + Д, (х„..., х„), а поскольку все величины целые, у=1+0«(хт " ° хо) = 1+а1(хм". хь) 1 что справедливо тогда н только тогда, когда (~, =- ~з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
