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

61. Очень неформальный конспект исследований связи между Е-выражениями н сетями Петри. Он послужил отправной точкой для написании работы !163]. 163. Ьаиег Р., Сап1рЬеИ К., А Везет!рИоп о! Ра!Ь Ехргезз1опз Ьу Ре1п НеИь ТесЬп1са1 Керог1 64, СоптриИпй 1.аЬога1огу, Пп!чегя11у о! Л!еисаяИе прои Туле, ЫежсаьИе ирои Тупе, Епя!апй, Мау 1974, рр.

39; РгосееЖпия оу !Ье Бесопй АСМ Бртроятит оп Рг!лс!р!ея о7 Ргойгатт!пй Т.аплиаитв, Неит богат АСМ, Лапттагу, 1975, р. 95 — !05. В работе принят конструктивный подход к доказательству того, что Е- выражения могут быть представлены сетями Петри. Е-выражения являются средством описания последовательности допустимых взаимодействий между параллельными процессамн. !64. 1.аист Р., СатпрЬеИ К., Раппа! БетпапИсз о! а С1аьв о! Н!8ЬЬече! РппиИчея 1ог Соогй!паИпй Сопситгеп1 Ргосезьея, Ас!а Тл7огтаз!са, 5, Л!о. 4, 1975, р. 297 †3. 165. пасет Р., БЫе1йз М., АЬь1тас! Брес!ИсаИоп о! Кезоитсе Ассеятйпд Иве!р11пез: Айет!пасу, 31агчаИоп, Ргюп1у апй 1п1етгирИ, Тесйптса! КероН 117, СогприИпй ЬаЬога!огу.

Т!п!четь!1у о! ЛечгсаИ!е ирои Тупе. ЫетчсаяИе ирои Тупе, Епд!апй, ПесегпЬет 1977„рр. 40. !66. Еаиег Р., Вея1 Е., БЫеййз М., Оп 1Ье РгоЫеш о! АсИеч1пй Айет1иасу о! Сопсиггеп1 Ргойгашз, ТесЬп1са! Керог1 113, СотприИпй 1.аЬога1огу, 13п1- чегзйу о! НежсазИе ирои Тупе, КетгсаьИе ироп Тупе. Епй!апй, батте 1977, рр. 36. 167. Ьаи1епЬасЬ К., Е!чепеья !и Ре1п Л!е1з, !п1егпа1 Керог1 !БР-75- 02.1, 1пзИЬи1 1иг !п!огшаИопззуь1етв!огзсйипй, СеяеИзсЬай !иг Ма1ЬетпаИ!т ипй Па1епчегагЬе16нпд, Вопп, туев! Степпапу, Зи!у 1975, рр. ЗЗ.

Обзор состояния вопроса об активности и тупиках в сетях Петри. В этой работе собрано вместе большинство результатов. 168. Ьаи1епЬасЬ К., БсЬш1й Н., 1!яе о1 Ре1г1 Хе!в !ог Рточ!пя Соггес1- пезз о! Сопспггеп1 Ргосезз Буь!етз, 7л7огвш1!он Ргосезилд 74, Ргосепйпда Анлотироааннал библиография 249 аг Гбг 1974 /РГР Сопйтгяь, Лгпя(егг(аш: Г(ог!ЬЫоИапгГ, Лиань! 1974, р. !87— 191. Системы параллельных процессов с ббльшим трудом поддаются анализу и доказательству корректности, чем последовательные программы. Сети Петри могут использоваться для моделирования таких систем и доказательства свойств моделируемых систем. В этой работе рассматриваются семафоры, ограниченные буфера и задача об обедающих мудрецах, чтобы вновь получить в терминах сетей Петри результаты, найденные ранее независимо.

169. Ьац1епЬасЬ К. ТЫадага(ап Р., Апа1уьВ о1 а йеяопгсе ЛИоса1!оп РгоЫегп ЬГк!пй Ре1п Ке(я, 1п!егпа1 Керог( 1БЕ-78-05, 1пя1Ип( Гпг 1п(оггпа11- опяяуя!егп(огясЬнпн, СеяеИясЬаИ Гш Ма1Ьегпа1!Ь гшг( Ва1епнегагЬе! Гапй. Вопи, 1Ггея( С~егшапу, Зппе 1978, рр. 17; Ргосггг(!пдь о7 ГГгг Р(гяг Еигареап Сот4еггасг ол Рата((г( апг( ТГ(ктггби(еб Ргосеы(пй. РеЬгпагу 1979. 170. Ьеппя К., М(сЬе! С., 1.е Венх Р., Ьон!са! Буь(егпь Вея(йп ЬГя!пя РГ Ая эпг( Рейй Не(я — РгойгапппаЫе Нагбм!гег( Буь(ешя, Гпгогтая(оп Ргосгяь!пй 77, Ргоатйпда ау Ие 1977 IРГР Сопйггяк, Ашя(егдаш: ЬГог(Ь-НоИапб, Ацяпь! 1977, р.

607 — 611 171. Ь!еп у., А Б(пг(у оГ 1Ье ТЬеогеИса! апд РгасНса1 Аьрес1я оГ Тгапя1- 1!оп Буя!ешя, РЬ. В. б!яяег(а1юп, Верят!шеп! о( Согпрп1ег Бс!епсея, ЬГпГнегя1- Гу оГ Са1Иогп!а, Вегйе(еу, Са!!Гоги!а, Бер1егпЬег 1972. 172. Ь|еп У., Тегпппа(юп апг( РюИепеяя РгорегНея оГ ТгзпюНоп Буя(ешь, ТесЬп!са! !Героя! 74-4, Г3ераг1шеп( о( Сошрн1ег Бс(енсе, ГГг1(нега(!у оГ Капяая, Ьавтепсе, Кангак, Бер1егпЬег 1974, рр. 32. 173. Ь!еп У., ТегпппаНоп Ргорег(!ея о! Сепега1!хег( Ре(П Ме!ь, БГЛЛГ Гаигпа! оГ Сотри((ггй, 5, Ь(о. 2, !976, р.

251 — 265. Под свойствами завершаемости здесь понимаготся свойства активности или образования тупика. Поскольку эта задача для обычных сетей Петри является еще не решенной, то Льен исследовал эту задачу для сетей Петри, которые являются свободнымн от конфликтов и не содержащими параллельных действий. При этом использовались как некоторые понятия нз теории графов, такие, как сильная связность, так и понятии теории сетей Петри, такие, как сохранение. 174.

1.1еп г'., Л Но(е оп ТгапьИ!оп Буя(ешя, !гйогта((ап Бсгепсгя, 1О, 1~то. 4, 1976, р. 347 — 362. 175. Ь!еп г'., Магйгане М., ТгапкРИоп Буя(ешя — Л Мобе! 1ог Сопспггеп! Ас1!нИ!ея, ТесЬп(са! Керог( 74-5, Всраг!шеп! оГ Согпрп1ег Бс!епсе, $.1п!неть!- !у о1 Капкая, 1 атнгепсе, Капяак, Ос1оЬег 1974, р.43. Справочное пособие, содержащее основные понятия сетей Петри и связанных с ними моделей систем переходов. Указываются приложения методов моделирования к транспортным. генетическим системам н вычислениям. 176.

Ь!р!оп В., ТЬе ВеасЬаЬ!1Иу РгоЫегп ГГег(а(гея ЕхропепИа1 Брасе, ВеяеагсЬ ГГерог! 62, Пераг!шеп( оГ Согпрп(ег Бс!енсе, г'а1е Ь1п!негяИу, Г(еш Нанеп, СоппесНсп1, Заппагу 1976, рр. 15. Результаты этой работы впервые были представлены на Конфеоенции по сетям Петри и связанным с ними методам в июле 1975 г. Эта работа содержит наиболее известный результат по сложности сетей Петри. Для доказательства того, что задача досгижнмосги для сетей Петри н эквивалентных моделей, таких, как систелгы сложения векторов, требует ие менее 2т ячеек памяти, используется 5 лемм.

Результат основан па конструкции, поназывающей, что нозможно построить счетчик, который может эффективно,'считать от 0 до 2, с числом переходов, пропорциональным Гг, Над счетчиком аояможяз ны операции сложения, вычитания и проверки иа нуль. (Именно проверка на нуль оказывается сложной.) Доказательство строится в рамках языка параллельных программ, который, как легко показать, эквивалентен сетям Петри.

Принеденное здесь достаточно сложное доказательство требует, чтобы его прочли несколько раз. 177. Ь(р(оп В., Бпудег Ь., РУ Б(гпп!а(1оп оГ СогпрЫа1юп ОгарЬя, ПпрпЫВЬеб, 1974, рр. 8. Аннотированная библиография Показано, что графы вычислений можно моделировать множествамн процессов, используя Р- и У-операции. 178. К. Е!р1оп., Зпудег Е.. Еа1сь(е!и с'., А Сснпрага(!те З(пду о! Моде1ь о! Рагайе! Согпри!айоп, Ргосеедсаук о1 Ме 15!5 А«ииа! Зутромит оп Зсосгойдлу алд А«сота!а Т!сеогу„Иеск с'ог)сс !ЕЕЕ, Ос!оЬег 1974, р. !45 — 155.

Липтон, Снайдер и Зальстейн сравнили основные модели параллельных вычислений, проделав работу, подобную выполненной в (5) и (240), но нх результаты существенно отличны. Отчичия проистекают из определения эквивалентности и включения Это исследование более формально и более трудно для его развития, чем (5) или (240), ио одинаково справедливо и интересно.

179. !Аьйот В,. ТЬе !!еь!дп о! 11ю Уепиь Орегайпи Зуз1есп, СоттилссаБонк о7 1(се АСМ, 15, Ио. 3, !972, р. 144 — 149. 180. Еисоп! Г., АьупсЬгопоов Сопсри(айопа1 З1гис1игеь, РЬ. О. д!ььег1айоп, Оераг1гпеп1 о! Е1ес1гка1 Епи!пеег!пи, Маьвасйиьейь 1пь(йи(е о! ТесЬ- по!ояу, СаспЬг!дуе, МаввасЬпве(Ь, Лапиагу 1968, рр. 139; ТесЬпсса! Вериг! 49, Рго!ес1 МАС, МазвасЬизейь 1пкЕйи(е о! ТесЬпо1ойу, СаспЬг!дйе. МаььасЬике1Ь, ГеЬгиагу 1968, рр. !39. 181.

Мапдгюй Ес., А Ио1е оп Ре)г! Ие1 Еапииаяез, 1п(егпа1 Вериг( 76-5, Еаьога(ог( сй Са!со(а!оп', 1пвН1исо д! Е(ес1(го(есп!са ед Е!ейгопка де! Ро1йеспссо сй Мс1апо, М!!ап, 11а1у, 1976; 1«1«гта!сои апд Соасг«1, 34, Ио. 2, 1977, р. 169 — !71. Показано, что языки сетей Петри, которые допускают Х-переходы, ие замкнуты по дополнению. )82. Мапл Л., Апдге С., Воет! Г., Сопсер11оп де Зуь(ешез Зес!иеп!!е!к То1а1егпеп1 Аи(о1ев(зЬ(еь а рагйг дев Кеьеаих де Ре(г),!севке Гга«акйе д'Аи1«- та!й7ие, 1«1огта!Руле е1 )сгс!сего(се Орега1!олпе!Ьсс Аи(о«ю!суке, !О, Ио.

11, 1976, р. 5 — 22 (1п Ггепсй). 183. Мауг Е., ТЬе Сагир(ехйу о1 !Ье Г!пйе Соп1а!пгпеп1 РгоЬ(еш !ог Ре1- п ИеЬ, Мав(ег'ь 1Ьев!в, Есераг!шеи! о! Е1ес(г1са! Епй!пеег)пи апд Соспрп(ег Зс!епсе, МавьасЬиьейв 1пя1йи1е о1 ТесЬпо!ояу, СагпЬг)дне, МаквасЬпвейв, Мау 1977, рр. 65; ТесЬпсса! Гсерог( 181, ЬаЬога!огу !ог Согори1ег Зс!енсе, Мавьасйсскейв !пь(йи1е о1 ТесЬпо1ойу, СашЬг!дйе, МаьвзсЬиве11в, Липе 1977, рр. 65. 184. Ме1дшап Л., А Иесз ТесЬп!с)ие 1ог Моде!!пи !Ье ВеЬаъюг о1 МапМасЬ!пе 1п1оппайоп Зув1ешв, Я(оаа Мааауетенх !сеосесо, 18, Ио. 3, 1977, р. 29 — 46. 185.

Ме1дшап Л., А Ре(г)-Ие( !сергекеп(зйоп о! СЮ! Ргоседоге, 1ОЕА— Тйе Хоигпа! о1 Еасо алд Теойно!оду, 19„Ио. 2, 1978, р. 123 — 148. 186. Ме!дшап Л., Ной А., Ре(п' ИеЬ апд Ееиз! Зув!ешь, Лигсте1г(ск Лоигла1, !2, Ио. 2, 1971, р. 65 — 75. Любопытное изложение сетей Петри для юристов. Юридические системы — это социальные системы, включающие адвокатов, судей, истцов, ответчиков, клерков и т. д. Взаимодействие между этими участниками процедуры описывается в такой книге, как сФедеральный гражданский процессуальный кодексэ.