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

56 — 26 Сети Петри, графы (ЛБА и системы сложения векторов рассматриваются как модели взаимосвязи аппаратных модулей. При анализе используется Аннотированная библаограй)ия дерево достяжнмости, а затею показываются некоторые проблемы, связанные с этими модулями. 133.

НцдЬез С., ТЬе Ецц!ъа)енсе о1 Ъ'ес1ог АййЬИоп Яуя)е|цз )о а 8иЬс)аяя о1 Рок1 Сапоп|са1 8ук!е|пк. ТесЬц)са! Керог1 С5-77-22, Со|прц1ег Бс)енсе ))ераг1|цеп), ))п)ъегз!)у о) Теппеяяее, Кнехт)Ие, Тецпезкее, Анния) 1977, рр. 6; Лг4огта1|ол Ргоаяз|лй З=ейегз, 7, Ко. 4, 1978, р. 201 — 204. 134. Ни|цап Н., Сопцпеп!я оп а Ргойет )и Сопсцггеп) Ргояга|пгп)пй Соп)го), Соттиа!са!г|огья о!' !ле АСМ, 9, Ло.

1, 1966, рр. 45. )35. 1азеоИа Оо Майе)И рег Е1аЬога|йопе РагаИе1а, ТесЬп|са! КероН 73-03, 1пяИ)ц1о й| Аи)о|паИса, Ып!тегзИа сИ Ко|па, Коте, 11а1у, 1973, рр. 54'(!и 1)а))ап). 136. )зЫсй! Н., Керог1 оп Маг)|ей ОгарЬз, ТесЬп!са! Керог1 25-136, 1ВМ Неппа ЬаЬога1опея, '9)еппа, Ацк)г!а, 1973, рр. 37. Это окончательный отчет по исследованиям в Венской лаборатории фирмы 1ВМ по маркированным графам. В нем собраны вместе работы Ижбики, Хенхапля, Хаисаля и Шваба. Изложение очень формальное, наполненное таинственными обозначениями н теоремами и связано с маркированными графами. Полученные результаты минимальны. 137.

ЛаИе Л., 5егпИ)пеаг 8еп апй АррИсаИопз, Мая1ег'з И|ек)я, Рера|1- |пеп1 о1 Е)ес)пса1 Епя)пееппя апй Со|при)ег 5с1епсе, МаязасйцзеИз 1пяШц)е о) Тесйпо!ойу, Са|цЬг!йяе, МаякасЬцкеИя, 1977, рр. 79; ТесЬгйса) Керог1 )83, ЬаЬога1огу 1ог Соп|рц1ег Бе|енсе, МакзасЬцзе))я )пзИ)и)е о) ТесЬпо)ояу, СатЬг!й8е, МаззасЬцяеИз, 1975, рр. 79. 138. Л ап1хеп М., Оп 1Ье Н|егагсЬу о1 Ре1г| Ке) Ьапяцаяея, К. А. А. К. О* ТЬеогеИса) 1п)от|па))сз, 13, Л)о.

), 1979, р. 19 — 30. 139. Лап!хеп М., 5!гцс)цгей Кергезеп)аИоп о1 Кпоъч)еййе Ьу Ре1п Л)е)з аз ап А)й !ог Теасрйп9 апй КеяеагсЬ, Айъагкей Соигзе оп Оепега! Л)е! ТЬеогу о) Ргосеяяея апй Яук)е|пз, На|пЬцгя, !979; Ьес)цге Л)о)ея )ц Сотри)ег 5с)енсе. ВегИп| Ярг)пйег-Ъ|ег)ай, 1980. )40. ЛапЬееп М., )га)Ь К., Рог|па! РгорегИея о1 Р1асе Тгапкй!оп Л)е)з, Айъапсей Соцгяе оп Оепега) Ке) ТЬеогу о1 Ргосеззек апй Яуз)е|цз, На|пЬцгй, !979; Ьес!цге Л)о1ек |п Сотри)ег Яс!епсе, ВегИп| 8рппдег-Ъ|ег)ай, 1980. 14!.

Лепзеп К., Ех)епйей апй Нурег Ре)г! Лебп ТесЬп)са1 Керог) ПА)М1 ТК-5, Согцрц1ег Зс!енсе 7)ераг!|цен), АагЬця Ып!ъегк))у, АагЬцз, ))епгпаг)г, 1978. 142. Лепяеп К., Со!оигей РеЬИ Ке)я апй И|е 1пъапап) Ме1Ьой, ТесЬп1са1 Керог1 ПА!М1 РВ-104, Сотри!ег 8с)енсе Рераг)теп), Ааг)Ьцз Бп!тетя!1у. АагЬцз, ))еп|цагй, 1979, рр. 27. )43. Лойпяоп К., Л)еейейг А №азиге 1ог Меазцге, Ра!ата!!ол, 16, Л)о. 12, 1970, р. 22 — 70. 144. Лопез Ко ЬацйъчеЬег Ь., Ь!еп "г"., Со|пр)ехИу о) 8о|це РгоЬ)е|пя )п Ре1г1 Л)е!з, ТесЬп)са! Керог1 276, Сотри!ег 5с)енсе Пераг)п|еп1, Ып)тегз!)у о1 %!ясона!п, Ма йтоп, ъъ'!ясона) и, 1976, рр. 43; Тйеоге)!са) Сотри(ег Бс!енсе, 4, )к)о. 3, 1977, р. 277 †2. В этой работе теория сложности применяется к сетям Петри. Для нескольких задач в сетях Петри, включая достижимость, активность и безопасность, даны границы времени и объема памяти.

Показано,чго живучесть сводима к достижямости. Результаты по сложности даны как для сетей Пегри, так и для автоматов, маркированных графов и сетей Петри со свободныи выбором. 145. Лц|цр Л., Трйайагз)ап Р., Оп )Ье Еци1та1епсе о1 АкупсЬгопоцз Соп)- го1 5)гцс)цгез, Ргосзей!лдк о7 Ме !3)Ь Аалиа! артроз)ит оп Зиз|сдйлй анй Аи!ото)а Тйеогу. Л)еьч Уогйл 1ЕЕЕ, 1972, р. 2!2 — 223.

146. Катр К., Кейцс1Ь|)Иу Агпопя Со|пЬ!па1ог1а! РгоЫеп|к, )п К. МРИег апй Л. ТЬа1сйег (ЕйИогк), Сотр)зхг!у оЛ Сотри1ег Сотри~ааааа, Л)еьч Уогйг Р1епцга Ргет, 1972„р. 85 — 103. 147. Катр К., МЬИег К., РгорегИез о) а Мойе1 1ог РагаИе! Со|при)а)юп| Пе)ег|ц!пасу, ТегпйпаИоп апй Яцеце!п9, Я/АМ Лоигпа! о7 Арр)!ей Л!а|Ь, !4, Ио. 6, 1966, р. 1390 — 1411. Аннотированная библиограйгил 247 Определяются н исследуются свойства модели вычислений в виде графа вычислений. Эта модель оказала влияние на многие более поздние модели, такие, как схемы параллельных программ [148).

148. Катр К., МЬИег К., РагаИе1 Ргодтагп Зсйеша1а, КС-2053, 1ВМ Т. 3. Ъ'а1яоп КеяеагсЬ Сеп1ег, Ъ'ог)г1о»тп Не!аЬ1я, Ые»ч Уогй, 1968, рр. 54; Хоигла1 оУ Сотри1ег апй Буягет Ясгепсе, 3, Ыо. 4, 1969, р. 167 — 195; ргеИпппагу йгаИ, 1ЕЕЕ Соп7«»елее Кесогй о7 1Ье 1967 Е1ай1Ь Аллиа1 Яутроярит ол Яго11- с1г1ли апй Аигота!а Тбеогу, Хетт Ъ'огй: 1ЕЕЕ, 1967, р. 55 — 61 ° Многие ранние работы по моделированию параллелизма в вычислительных системах основаны на модели вычислительной системы с памятью и несколькими процессорами.

Процессоры выполняли программы, которые моделируются в большей или меньшей степени блок-схемами. Данная работа Карпа н Миллера является высшей точкой этого подхода. В ней представляются модели схем параллельных программ, а затем определяются различные вопросы, связанные с этой моделью, такие, как эквивалентность, детермняированносгь и ограниченность. Особый интерес представляет равд. Ч, в котором вводятся системы сложения векторов и деревья достижимосгн для решения задач ограниченности и покрываемостн. !49.

Каяапп' Т., Чес)ог Айй1Иоп Зуя1ешя апй ЗупсЬгоп!ха1!оп РгоЬ!ешя о! Сопспггеп1 Ргосеяьея, ТесЬп!са! Керог! АКО-23, Ип)четь!1у о! НаттаИ, Нопо1и1п, НатгаИ, !974. 150. КеИег К., Чес1ог Кер1асешеп1 5уя!ешса А ГогшаИяш !ог МойеИпд АяупсЬгопооь 5уь1ешь, ТесЬп!са! Керог1 117, Сошрп1ег 5с!епсе ЬаЬога!огу, РНпсе1оп !!п1тегьйу, Р~псе1оп, г!е»г,)егяеу, ЬесегпЬег 1972, рр.

38; гетйяей ааппагу 1974, рр. 57. Важная работа, на которую часто ссылаются. Келлер определяет «Системы переходов» как общую модель параллельных вычислений, а затем сужает ее до систем замещения векторов. Системы замещения векторов являются естественным обобщением систем сложения векторов и формализмом, эквивалентным сетям Петри. Исследуется главным образом задача активности. 151.

КеИег К., А Рипйагпеп1а1 ТЬеогеш о! АяупсЬгопоия РагаИе1 Сотри!аНоп, Ргосеей!щя о! 1ле Баяатоге Сотри1гг Соп7егепсе, Ьес1нге Ь)о1ея 1п Сошрп1ег Зс!епсе, 24, ВегИп: 5рНпдег-Чег1ай, Апдпь! 1974, р. 102 — 112. 152. КеИег К., ОепегаИгей Ре1г! Ые1» аь Майе!ь 1ог 5уя1еш ЧегИ)саИоп, ТесЬп)са1 Керог1 202, !»ераг!шеп! о! Е1ес1Пса1 Епя!пеег!пя„Рг!псе!оп Пп)- тегь11у, Рг!псе!оп, Хеъ Легяеу, Апяпь1 1975, рр. 50. В данном случае Келлер заинтересован в определении мощности моделирования (системы, которые могут быть промоделнроваиы) и мощности разрешения (вопросы, которые разрешимы) сетей Петри . Мощность моделирования характеризуется аддитивними монотонными системами. Обсуждаемые здесь вопросы разрешимости концентрируются на использовании дерева достижимостн для доказательства корректности. 153.

КеИег К., Ьоой-АЬеай Ргосеяяогя, Сотриг!ги! Кигоеуя, 7, !4о. 4, 1975, р. !77 — 196. 154. КеИег К., Гогша1 ЧегИ!са1!оп о1 РагаИе! Ргоягашя, СоттитсаИ- опя о7 1йе АСМ, 19, Ыо. 7, 1976, р. 37! — 384. Модель, используемая здесь, явлиетси более мощной, чем сети Петри, но разработана на основе работы Келлера по системам замещения векторов н сетям Петри. 155. К!ппеу Ь., Нап У., КейпсИоп о1 Ре1«1 г!е1ь, Ргосеейгпйь о1 йе 1413 А!1ег1оп Соп7егепсе оп С1гсш1я апй 8уя1еаяя ТЬеогу, 5ер1егпЬег 1976.

156. Кпп!Ь П., ТЬе Аг1 о! Сотри!ег Ргоигапнп!пя, 3, ЗогИпд апй 5еагсЬ!пя, Кеай!пд, Маьяас1шяе!Ьм Аййгьоп-%еь!еу, 1973, рр. 772. 157. Кпп!Ь Е., Ре1п' Ь!е!я апй Кейп!аг Тгасе Ьапдпаяея, Керог1 АБМ(47, Сотри!!пд 1.аЬога1огу, 1)п1тегяИу о1 ЫечгсаьИе прап Туле, ЫеьчсаяИе ороп Тупе, Епд1апй, АргИ 1978.

158. Кпп1Ь Е.,Сус!еь о! РагИа! Огйегь., Ргосеей)пбя о) 1Ье Леоел1л Бутр~~- ягит оп Магйета11са! Роипйа11опя оу Соглригег Ясгепся 1978, ! ес1пге Ь!о1еь )п Со»при!ег Яс)епсе, 64, Вег11п: БрНпйег-Чег1ад, 5ер1егпЬег 197 8, р. 315 — 325 Аннотированная библиоарафия 159.

Козага!и Б., 1.1тпйаИопз о! П!!Ьь1га'з БетпарЬоге Рг!гпИ!чез апй Ре1г! ХеИ, Тесйп!са! Керог! 25, Сотпри1ег Бс!енсе Ргойташ, йоЬпь Норйбпз Ип!чегзИу, Ве11ппоге, Мату!апй, Мау 1973, рр. 20; Орегат!па Ядз!етя Кеотеат, 7, Лто. 4, 1973, р. 122 — !26. Это первая работа по определению задачи синхронизации, которую нельзя промоделировать с помощью сетей Петри. Поскольку в сетях Петри можно моделировать Р- н Ч-операции над семафорами, то они также являются неполными. Проблема заключается в кодировании состояний с одной.

двумя или тремя фишками в позиции. Поскольку сети Петри являются разрешающими, то невозможно препятствовать запуску перехода, предназначенного для запуска с одной нлн двумя фиптками в позиции, когда в ней имеется три фишки 160. Ко!оч Ч., Ап А!деЬга 1ог Рагайе1!ып Вязей оп Ре1г1 Л!е1в, Ргосгей!пйз о/ Же Яеоеи!Ь Юитрозтттт оп Ма!йети!тйа! Рантик!!опз о7 Сотри!ег Затеи енсе 1978, 1.ее!иге Л!о1ея 1п Сотпри1ег Бстепсе, 64, Вег!тп: Брт!пает-Чег!ая, Бер1етпЬег 1978, р. 39 — 55. 161. ЬапйчеЬег 1., КоЬег!ьоп Е„РторегИез о! СопП1с1-1гее апй Реть!я1еп1 Ре1п' Ь!е1з, ТесЬшса! КероН 264, Сотприйег Бс!епсез Перес!шеи!, Нп!чегзйу о1%!ьсопз!п, Май!зоп, %1ясопз!и, ВесешЬег 1975, рр.

30; Хоигла! о! Фе АСМ, 25, Но. 3, 1978, р. 352 — 364. Сети Петри, свободные от конфликтов, допускают разделяемые входные позиции, только если они пе входят в петли. 7Кввучне сети Петри не могут сделать переход неразрешенным иным способом, отличным от его запуска. Множество достижимости обоих типов сетей Петри характеризуется как полулннейнос. Основными темами этой работы являютсясложность н разрешимость. 162. Ьаиег Р., Райй Ехртеьвопз аз Ре1гт Л!е1з, ог Ре1п' Ые1з тчИЬ Ретвег Теагз, МКМ 70, Сота риИпй Ьайога1огу, оп!четь!1у о1 ЛетчсаьИе прап Тупе, йетчсазИе ироп Туле, Епй1апй, Запиагу 1974, рр.