Главная » Просмотр файлов » Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984

Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 25

Файл №1184511 Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984) 25 страницаПитерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511) страница 252020-08-20СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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 касался в основном вопросов, связанных с задачей достижимасги, т. е. с достижимыми маркировками. Родственный, но совершенно отличный подход заключается в рассмотрении не того, какие маркировки достижимы, а того, как их можно достичь. Поэтому главным обтектом внимания являются переходы и, в частности, последовательности переходов, переводящих одну маркировку сети Петри в другую.

Характеристики

Тип файла
DJVU-файл
Размер
5,47 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6531
Авторов
на СтудИзбе
301
Средний доход
с одного платного файла
Обучение Подробнее