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

5. 113. Нас!г М. ТЬе Кесиггбте Ег!шва!енсе о!1Ье КеасйаЫ!1!у РгоЫегп ап ЬЬе 1.1тепем РгоЫеш 1ог Ре1п НеЬ апд Чес1ог АИШоп Зуь(ешв, Сотри(а(1- оп 51гис1игеь Сгоир Мегпо 107, Рго)ес1 МАС, Мамасйияе1Ь !пв111и1е о! ТесЬ- по!ояу, СагпЬпбйе„МаьмсЬимНгч Аийиз( !974, рр. 9; Ргосггг((ту~и о!' Ме ЛЮСЬ Апина! 8утросцит он 3ю!!сд!яй апг! Аи!ата!а Тйгогу, Нечг"гог(сг 1ЕЕЕ, Ос1о- Ьег 1974, р.

156 — !64, Понавано, что задача достнжимосгн н задача активности взаимно сво- димы. !14. Нас!г М., ТЬе ЕйиаН!у РгоЫегп !ог Чес1ог АИН!оп Зуь(ешв 1я Ппбе- с1баЫе, Согпри1а1!оп 5!гис1игеь Сгоир Меню !21, Рго)ес( МАС, МамасЬпьеНв !пв1!1и(е о! ТесЬпо!ойу, СашЪг!бне, МаьвасЬиве11я, Арп! 1975, рр. 32; Тйго- ге11са! Сотри1гг 3с(гиге, 2, Ко. 1, Лйпе 1976, р.

77 — 96. Показано, что задача о подмножестве для множеств достижимостн сво- дима к задаче о равенстве. Таким образом, поскольку задача о подмножестве неразрешима (см. [26, 110) илн [1!1)), то задача о равенстве также неразре- шима. Это доказательство дано здесь в гл. 5. 115. г!ас(г М., Ре!и' Не( Еапйиайея, Сотри(а!1оп 5!гас(шев Пгоир Меню 124, Рго)ес( МАС, МамасЬияеНв 1пь1!1и(е о! ТесЬпо!ону.

СатпЬгЫйе, Мама- сЬияе!Ь, Липе 1975, рр. 128: ТесЬпка! 1!ерог1 !59, ЬаЪога1огу !ог Сотри!ег Аияогироааниая библиогрш]»ия Бс)енсе, МазвасЬиве))з 1пвШи)е о1 ТесЬпо)ойу, СашЬ»Ыае, Маэ»асЬизейв, МагсЬ 1976, рр. 128. Следуя предположениям Бэйкера ]24], Хэк тщательно исследовал языки сетей Петри. Выделяются два основных класса языков: префиксные языки всех последовательностей, которые ведут к достижимой маркировке, и языки последовательностей, ведущих к определенной заключательной маркировке. Кроме того, Хэк рассматривает язьжи, которые получаются в результате принятия решения о разрешении или запрещении переходов, помеченных Х, пустой строкой. Для каждого из этих четырех классов определены простые свойства замкнутости/» даны характеристики.

Кроме того,эти языки связаны с другими классами языков, включая регулярные языки. Показано, что задачи принадлежности, пустоты й конечности раврешичы для некоторых языков, но эквивалентны задаче достижимости дли других. Прекрасное исследование в новой области. 1!6. Нас)» №. Юес)баМ!1)у С)иез))опя !ог РеЫ ИеЬ, РЬ. )). Й)взег)а)»оп, )Уераг)шеп) о) Е1ес1г»са) Епйепеег)пй, МавзасЬияейв 1пзШи$е о) ТесЬпо)оду, СашЬпдйе, МаяяасЬияейв, ОесегиЬег 1975, рр. 194; ТесЬп!са1 Керог$161, )лЬога1огу !ог Соп»ри1ег Бс»енсе, Мазвас)шяе1Ь )пя)1)й)е о) ТесЬпо)оду, СагпЬ»Ыйе, МаввасЬиве))в, Липе 1976. рр. 194.

В втой диссертации собраны вместе многие из работ Хэка. Диссертация является прекрасной работой по сетям Петри, включающей как основные определения и свойства, так и новейшие исследования. Каждая тема тщательно определена н разработана. Основные главы включают: разрешимость ограииче»»ности и покрываемости ]используя дерево достижимасти); задачи достижимости; активность и живучесть; неразрешимость задач подмножества и равенства для множеств достижимости в сетях Петри (как это впервые представлено в ]110, 114]); языки сетей Петри ]1)5].

Диссертация завершается некоторыми открытыми вопросами н предположенинми. 117. Нап У., Регбоппапсе Еча)иа))оп о1 а ))!81)а! Буя)еп» $)з!пд а РеЫ Ие1-1)йе АрргоасЬ, Ргосее»(!идв ц/з»(/»в //а((опа! Е!ес/гел»вк Со4егелсе, 23, 1978, р. 166 — 172. 118. Нап У., К»ппеу 1... Ре1п' Ие) Кебисйоп апд ангес)!)са))оп, Нопеуи»е)1, М)ппеаройя, М)ппезо1а, 1977, рр. 52. 119. НеЬаП»аг Р., Оеаб!ос)»-(гее БЬаг1пя о1 Кеяоигсев»п АвупсЬгопоив Буз)епм, РЬ. )).

б)явег$а))оп, ))ераг)шеп) о1 Е1ес)г!са1 Епй!пееппй, МаввасЬизейз 1пзШи1е о1 ТесЬпо)оду. СашЬ»Ыяе, МаввасЬияейз, Бер)ешЬег 1970, рр. 185; ТесЬп»са1 Керог)75, Рго)ес) МАС, МазяасЬивейя 1пвШи1е о1 ТесЬпо)оду, СагпЬг!бйе, МаввасЬи»е1Ь, Бер1ешЬег, 1970, рр. 185. 120. Не)щего!паег $$»., А РеЫ Ие1 АррговсЬ )о Буз$еш 1.ече1 Гаи)1 То1егапсе Апа)уз»в, Ргосегг((лдз о!' (Ае /га((ола! Ейю(гол(ск Сол/егелсе, 23, Ос1оЬег 1978, р.

161 — 165. 121. НепЬар)%., А Тгапз!оппа))оп о! Магйс!) ОгарЬв, !л/отта((ои Ргосезз(пд (.е((егв, 2, Ио. 1, МагсЬ 1973, р. 26 — 29. 122. Негхо3 О., Аи$оша1!с ))еаб)ос)» Апа1увЬ о! Рага11е1 Ргобгатз, Ргозеайпйв о/ (/»е /л(егли((опа! Сотри((ля Яутров(ит 1977, Ашз)егдагп: Иог$Ь-Но11апд, Арг)1 1977, р. 209 — 216. 123. Ной А., 1п)гобое))оп 1о Оссигепсе Буя)е»ив, Аз»ос!а((ое (л/отта((ол Тегйп(аиез, Иеж Уог!и Агпепсвп Е)тт)ег, 1971, р.

175 — 203. Хорошо изложенный обзор результатов Проекта теории ииформапиониых систем. Справочное пособие по системам событий с примерами и прекрасным обсуждением параллелизма и конфликтов в терминах систем событий и, следовательно, безопасных сетей Петри. 124. Ной А., Ко)е/Асйчйу Модей апд Ре$г! ИеЬ, Яясол»( Яет(-Аллиа( Тес/»л(са! /(ерог/, Керог1 САВО-7503-14!1, Матас)шзе1Ь Соп»ри$ег Аквос1а$ея, $Ча)»е))е)д, МавзасЬияе11в, 1975, р. 5 — 26. 125.

Но1$ А., ВейпШопя Рег)а!п»пя )о Ре1г» ИеЬ, Б)а)ез апб ЕчепЬ апб ВеЬач)ог, Бесии»( Яет(-Аллиа! Тес/»л(са! Керог(, Керог1 СА$))»-7503-!4!1, МаюасЬике$Ь Согири1ег Аввос)а1ея. ))'айе!)е! д. МаввасЬияе))з, 1975, р. 58 — 69. Аннотированная библиаарабгия 245 126. НоИ А., Сопппип1саИоп МесЬап!сз, Бесов! Бетг-Апина! Тегдтга! Керопй Керог1 САВВ-Ув)3-1411, МаззасЬпзе11з СоврШег Аззос!а(ез, )йайе- 1!е(б, МавасЬпэе165 1975, р.

143 — 168. 127. Но11 А., Согппюпег Г., Еуепв апб СопбИ!опз (!п 1Ьгее раг(Ьз), АррИед Ва1а Резеагсп, Нем Уогй, 1970; Кесогб о) Гйе Рго!есГ л(АС СопЛсгелге оп Сопсшгеп! Ярз)евз апб РагаИе! Сагпри[а!шп, Ыетг Ъ'огра АСМ, 1970, р. ! — 52. Рабата Хольта по развитию науки об информации и системах называется систематикой. В данной статье имеется превосходное изложение основ этой работы и начал теория сетей Петри.

Сети Петри определяются и иллюстрируются. На протяжении всей работы рассматриваются маркированные графы и автоматы. В одном нз примеров статьи отражено ограничение безопасности и, таким образом„посажено зерно современных определений. Статья очень интересна и хорошо читается. 128. Но!1 А., Ба!п1 Н., Яир!го К., 97агзЬаИ $., Г!па1 Керог1 о( 1Ье 1и(огваИоп Яуз(еш ТЬеогу Рго)ес1„ТесЬй!са1 Керог( КАВС-ТК-68-305, Копи Агг Веуе1оргпеп1 Сеп(ег, ОИИВз Агг Гогов Ваш, Ыечг Уогй, 1968, рр. 352. Зтот объемный отчет представляет результаты Проекта теории информационных систем, которые касаются определения необходимых описательных средств для моделирования, сценки и реализации систем. Сети Петри занимают основную часть этой работы н представлены здесь детально.

Понятие сети Петри само по себе является еще безопасной сетью. Зто привело к большому объему работ по графам событий и системам событий, подходу к представлению и анализу последовательностей запусков, которые применимы к безопасным сетям. После работы (127) интерес к системам событий уменьшился. Большинство работ по сетям Петри ссыпается на этот отчет, хотя он представляет сейчас главным образом исторический интерес. Раздел Ч пересмотрен (274). 129. Норсгой Л., Рапз)о! Л., Оп Ийе КеасЬаЬ!1Иу РгоЫегп 1ог 5-Вппепз!опа! Чес(ог АбдРИоп Зузгепгэ, ТесЬшса! Керог1 76-280, Вераг1веп1 о1 Сопи рп(ег 5с(енсе, СогпеИ 1)п!уегз!1у, 11Ьаса, Ыеуг Уогй, 1976, рр.

42. Изучается задача достижимостн для систем сложении векторов с размерностью не большей пяти (сети Петри с числом позиций ие больше пити). Показано, что множества достнжимости являются эффективно полулинейными, это дает алгоритм для их решения. Задачи эквивалентности н включения в общем случае неразрешимые разрешимы для этих систем. К сожалению, этот подход не пригоден для сетей с числом позиций большим пяти и имеет поэтому ограниченную практическую пользу.

! 30. Норсгой Л., 1)Иван Л., ГаллаМ Саплиалег ав! Тйе!г Ке!айоп го Антошаа)а. Кеаб!пй, МавасЬизе11зг Абб!эоп-Ъ'ез1еу, 1969, рр. 242. Зта книга янляется классической в данной области. Оиа является кратким, ио понятным изложением теории формальных языков (регулярных, контекстно-свободных, контекстно-зависимых и языков типа О) и теории автоматов (автоматы с магазинной памятью, линейные ограниченные автоматы и машины Тьюринга). Хорошо предсввлены вопросы разрешимости и вопросы временной н емкостяой сложности.

Наиболее читаемый н постоянно упоминаемый источник для работ з любой нз этих областей. 13!. Норпег М., Орр М., Кепав!пй апб Егалпй 1п ЯаИагд Ьапяиайез, ТесЬп!са! Керог( 35, !пзИ(п1 1иг 1п!огваИЬ, ()и!уегз!1у о( НагпЬпгд, Мау 1977, рр. 371 Аи!ота)а, Сапйиайез апб Ргойгаттгп~, ) ес1пге )4о1ез !и Соврп1ег 5с!енсе, 52, ВегИп: Брг!пйег-Чег!ац, 1977, р. 244 — 257. 132. Ниеп )Ч., 8!ечбогей В., 1и!егвобп!е Рго1осо) !ог Кей!з(ег Тгапз1ег Сече! Моби!ез: Кергелен(аИоп апд Апа1уИс ТооИь Ргосеа)гпйг оу Где Зесопб Аллиа! Бутраг!ит оп Сотри!ег Аггвикгиге, Ыем Уогрл АСМ, 1975, р.