Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 25
Текст из файла (страница 25)
Далее вводятся еще одна позиция з, и два новых перехода, сл и 1в. Начальная маркировка всей сети (включая А и В как подсети с общими позициями; позиции гл, гв и з; переходы 1л и Ьв) определяется одной фишкой в з и нулем в остальных. Переход ~„имеет в качестве входа з, а выход его порождает начальную маркировку сети А плюс фишку в гл; переход Ув в качестве входа также имеет з, а выход его создает начальную маркировку сети В плюс фишку в гв.
Следовательно, если запустится 1л, то подсеть А приобретает Слотсяоств и Разрешимость свою начальную маркировку, н все ее переходы могут запускаться, какобычно, поскольку в г„нмеется фяшка. Подсеть В, однако, полностью запрещена, поскольку фишки в гв нет. Если первым запустнтся гв, то сможет действовать подсеть В, а подсеть А будет запрещена. Тогда множество последовательностей для С вЂ” это любая последовательность вида У, (любая последовалылвность запускав в А) нлн любая последовательность вида (в, (лтобая последовательность запусков в В). Сеть т'.) получается нз С введением одного нового перехода ув.
Он имеет в качестве входа позицию тв, выход его пуст. Заметим, что дв может запуститься, только если первым был запущен переход 1в, если же первым напустятся переход (л, то тв будет пустой н дв не сможет запуститься. Сеть Е строятся нэ .0 добавлением нового перехода дл.
Он в ка; честве входа имеет позицию т„, выхода не имеет. Переход может запуститься, только если первым был запущен (л. Подчеркнем, что сеть Е строится нз Х), а не(непосредственно) нз С. Поэтому Е имеет н переход дл, н переход дв. Рассмотрим теперь множества достижнмостн сетей Петри С, О н Е. Множество достяжнмостн С вЂ” это все маркировки вида: Рт ° ° ° Р„ О,...,О ! О Любаямаркировкаиск(А,мл) (если запустится 1Л) Любая маркировка р ~ й(В, (ьз) (если запустится 1в ) в Сеть Петри в) добавляет к этому множеству один новый класс мар' кнровок: О,...,О Любая марьппювка и Г й(А, рл) (если запустится гл) Любая маркировка и с Ю(В.Р в) (если запусппся тз) Любая маркировка р Е И(В,из) (если запустится ов) !42 Глава б Сеть Петри Е добавляет еще один класс Рт ° ° ° ° рв 'в о, .
. ., о Любая маркировка р С 1е (И,р.и) (если запустится 1 л) Любая маркировка ИС м(В,р.в) (если запустится 1 ~) Любая маркировка р(Гс(В,ри) (если запустится Чв) Любав маркировка и. б Л(я,р 1) (если запустится Чл) Теперь, если й(А, р„,) ы й(В, рв), то последний класс в й(Е„ра) (маркировки вида (О, 0,0, р), где р 6 й(А, рл)) включен в последний класс й(Р, ро) (маркировки вида (О, О, О, р), где р б й(В, р„)). Поскольку все другие маркировки совпадают, то й(Р, ро) = = й(Е, рп), если й(А, рл]из й(В, рв).
Аналогично, если й(Р, ро) =й(Е, ри), то й(А, ил)ы й(В, рв), так как для всякой маркировки (О, О, О, р), где р б й(А, рл), в й(Е, рв) должна существовать такая же маркировка в й(Р, ро). Но все маркировки с р(з, и,, гв) = (О, О, О) имеют вид (О, О, О, р), где р б й(В, рв), поэтому й(А. рл) — й(В рв). Таким образом, на основе этой конструкции доказано следующее. Теорема 5.10.
Задача подмножества для множеств достижимосги сетей Петри сводима к задаче равенства для множеств достижимости сетей Петри. Последние три теоремы приводят к следующему результату, Теорема 5.11. Следукпцие задачи неразрешимы: 1. Задача включения графов полнномов. 2. Задача подмножества для множеств достижимости сетей Петри. 3. Задача равенства для множеств,постижимости сетей Петри. Эти теоремы и их доказательства принадлежат Хэку Ш4, 116). 5.о. Спожносп задачи достижимости Поскольку задачи подмножества и равенства для множеств достижимости сетей Петри неразрешимы, то возможно, что неразрешима также и сама задача достижимости. Однако в настоящее 144 Глава 5 Для небольшнх чисел Й можно проверить, равна лн маркировка позняка числу й, делая позицию входом перехода й раз (рнс.
5.15). Однако этн дуги увелнчнвак>т размерность вадачн, поэтому в общем случае тзк поступать нельзя. Липтон показал, что если постоянная сУмма двУх познцнй (Р„, Рл) Равна й н А ЯвлЯетсЯ пРоизведением двух целых сомножителей й = й, йк, которые являются постоянными сУммами ДвУх ДРУгих паР позиций (Рвм Рл, н Рл, Рл,)> н мы можем проверить, выполняется лн р(Рл,) = — О н )((Рл„) =- О, то можно проверить, выполняется лн )( (Рд) =- О.
Это позволило Лнптону строить подсети так, как показано на рнс. 6.16. Такие сети затем использовались для контроля сетей умножения, подобных сетям, используемым для слабого вычнслення графОв полнномов (см. рнс, 5.10). Проверка на нуль подсети позволяет сети Петри вычислять точное ппонзведенне (а не слабое пронзведенне, которое только ограничено сверху действнтельным произведением). Этн простые сети позволили Лнптону постронтьсегь, которая для данного и может порождать точно л фишек в позиции (Р) с нулем фишек в Р' н в которой можно проверить р(Р) на равенство нулю.
Число используемых позиций равно произведению константы на и. Существование сегн Петри, подобной этой, показывает, что задача достнжнмостн требует по крайней мере экспоненцнальных времени н памяти„н, следовательно, затраты на вычисление ее решения слишком велики. и0» о л(л1 1 и(>) 2 Рлс. В>,1о Проверка маркировки ограниченной позиции на совпаденнесО. 1 или 2. Все перекоды должны лондер>кивать сумму маркировки. 14о Сложность и раз)хчллхюсть Конструкция сети Петри, которая меже) пересчитывать числа до 2а ° имеет е)це и важное следствие.
Построенная таким образом сеть Петри ограниченна, поскольку число фишек в любой позиции не может превысить 2а'. Это означает, что любой алгоритм определения ограниченности сети Петри также должен требовать экспоненциальных времени и памяти. Следовательно, даже простые задачи для сетей Петри, хотя и являются разрешимыми, могут требовать для поиска решения больших затрат времени н памяти. р) 40 Рис.
5.16. Вид сетей Петри, используемых Липтоном для построения оольщнх сетей. допускающих проверку оольглего счетчика на нуль. я(л) = о Необходимо напомнить, что описанные границы являются нижними для наихудшего случая поведения алгоритма. Но может оказаться, что многие интересные задачи решаются для большинства сетей Петри сравнительно эффективно. Оценка сложности показывает, что, даже если для большинства сетей алгоритм требует малых затрат памяти и времени, сущсствйаи сеть Петри, которая для анализа потребует гораздо больше времени и объема памяти. Хотя оценки сложности получены для наихудшего случая (это означает, что в среднем они намного лучше), они являются, кроме того, нижней границей.
Мы знаем, что задача достижимости требует экспоненциального объема памяти, не льсяее. Возможно, что сложность определения достижимостн даже не экспоненциальная. Ракофф 1253) предложил алгоритм определения ограниченности за экспоненциальное время, поэтому задача ограниченности известна теперь как имекхцая экспоненциальную сложность. Задача достижимости известна как по крайней мере экспопенциально сложная (и, возможно, даже неразрешимая).
Последний результат Майра П83) показал, что задачи подмножества и равенства для множеств достижимости ограниченных сетей Петри имеют сложность непримитивной рекурсии. Это означает, что некоторые задачи для сетей Петри, несмотря на разрешимость, требуют иа вычисление значительных затрат. 1 Упражнении 1. Покажите, что задача достижнмосги для ординарных сетей Петри эквивалентна задаче достюкимости нуля в одной позиции для сетей Петри без петель З.
Пусть для сети Петри Сг = (Рь Ть Ть Ог) определена новая сеть Петри Сз = (Рэ, Тт, йн Оз) с Р =Р ()(р.~!>ЕТг), Т =-Т, !з= Тю О,(~,) =О,(())О[Р') . Такое определение вводит по одной дополнительной позиции в качестве выхода каждого перехода. а) Каков смысл числа фишек в каждой нз этих позиций? Какова граница на маркировку этих позиций для активной сети Пегрнй б) Допустим, мы ввели в сеть один дополнительный переход, имеющин в качестве входа кагкдую позицию р~ и ие имеющий выхода.
Покажите, что сеть активна тогда н только тогда, когда активен этот новый переход. в.У. Замечании и иитературе Теория аычислимости — начало теории вычислений — была развита из работ Тьюринга, Клини, Геделя и Черча. Девис [69] и Минский [200) предлагщот хорошие введения в нее. Карп [1461 показал, как сводимость можно использовать для получении результатов по разрешимости и сложности. Задача достижимости впервые поставлена в П48[, как исследовательский вопрос она ставилась в [213), Предварительные результаты сообщены в [299, 129[, но они не обобщены. Болыпинство результатов, изложенных в этой главе, взяты из работ Хэка [111, 113, 114, 116[.
Хэк — один нз основных исследователей по задачам разрешимости в сетях Петри. В числе других работ по свойствам разрешимости ПЗ, 183[. Результаты по сложности получены Липтоном [176), Ракоффом [233[ н Джоунсом и др. [144[. Некоторые работы [47, 48[ косвенно связаны с сетями Петри. 5.8. Темы для дальненшего изучения !. Сеть Петри называется обратимой, если для каждого перехода 1 ~ Т найдется переход (а ~ Т.
такой, что 41 (Р„Т (1,)) = ~. (Р„О((,)), -)) (рм 0(Ь)) = Ф (рм 7((~))- Иными словами, для каждого перехода существует другой переход с обратными входами н выходами. Это позволяет «уничтожать выполненноеэ последовательностью переходов путем запуска в об- Сломыость и разреши чосп !47 ратном порядке их дополнительных переходов.
Установлено П291, что для обратимых сетей Петри задачи достнжимости и покрываемости разрешимы. Этот результат основан на работах по коммутативным полугруппам 1471. Установите на основе нзаимосвязи между обратимымн сетями Петри и коммутатнвными полугруппзми разрешимость достижнмости и эквивалентности для обратимых сетей Петри. Для развития теории обратимых сетей Петри рассмотрите также задачу активности, вопросы сложности и языки обратимых сетей Петри.
2. Представляется весьма полезной связь сетей Петри с арифлегликой 77рссбюргера. Арифметика Пресбюргера — эта арифметическая теория, использующая сложение н вычитание целых чисел. Показано, что можно установить истинность нли ложность всех высказываний, образованных из квзнторов первого порядка, равенства, операций сложения и вычитания и целых чисел. Первоначальное доказательство было представлено в 12521 н использовалось в качестве основы для автоматического доказательства теорем 163, 5Я. Связь арифметики Пресбюргера с полулинейными множествами упоминалась в 199, 1011, а взаимосвязь полулииейных множеств с достижнмостью — в ~299, 61, 161, 129, 137], Предположительно арифметику Пресбюргера можно использовать для решения задач анализа сетей Петри.
Исследуйте этот вопрос. ГЛАВА 6 ЯЗЫКИ СЕТЕЙ ПЕТРИ ;:р ь11 1 э Материал гл. 4, 5 касался в основном вопросов, связанных с задачей достижимасги, т. е. с достижимыми маркировками. Родственный, но совершенно отличный подход заключается в рассмотрении не того, какие маркировки достижимы, а того, как их можно достичь. Поэтому главным обтектом внимания являются переходы и, в частности, последовательности переходов, переводящих одну маркировку сети Петри в другую.