2.6. Альтернативные формы определения сетей Петри

Теория сетей Петри разрабатывалась рядом авторов. У них были различные мотивы и предпосылки. Вследствие такого разнообразия многие фундаментальные понятия были определены по-разному. Дадим некоторые из этих альтернативных определений, чтобы показать, что между ними нет существенных различий, и чтобы подготовить читателя к тем разнообразным представлениям, которые могут встретиться в литературе.

Например, оригинальные сети Петри [241] не разрешают существование кратных дуг между позициями и переходами. Это эквивалентно определению входов и выходов переходов как множеств (а не как комплектов) позиций. Далее, правило запуска было ограничено следующим требованием: фишка есть в каждой входной позиции для перехода, и нет ни одной фишки в выходных позициях. Переход запускается путем удаления фишек из его входов (которые теперь становятся пустыми) и размещением фишек в (ранее пустых) выходах (которые теперь заполняются). Переход не может быть запущен, если фишка уже принадлежит выходной позиции. Таким образом, маркировка каждой позиции присваивает либо фишек, либо 1 фишку, Теперь становится очевидным тот факт, что сеть с позициями имеет точно возможных маркировок, т. е. конечное число состояний.

Ранние разработки Хольта по проекту теории информационных систем [128] использовали эти же определения, но по мере продвижения исследований была обнаружена ограниченность такой модели. В работе Хольта и Коммонера, представленной на конференции в Вудс Холле [127], класс маркировок и правила запуска распространены на произвольные маркировки, Таким образом была создана базовая модель сетей Петри в том виде, в каком она определена сегодня (за исключением возможности кратных дуг).

Многие из первых исследователей не давали формального определения своих моделей, а описывали неформально относящиеся к их работе компоненты, такие, как позиции, переходы, фишки и правило запуска. Одно из первых формальных определений было дано Патилом [231] в его докторской диссертации, в которой сеть Петри определялась в виде четверки где множество переходов, А — множество дуг, множество позиций и В — начальная маркировка. Дуги множества А соединяли либо позицию с переходом, либо переход с позицией. Таким образом, Многие статьи по сетям Петри основываются

на этом определении и определяют сеть Петри как тройку с выделенной функцией маркировки.

Преобразование из формы к определению с выделением входной и выходной функциями сравнительно просто. Множества дуг А разбивается на множество входных дуг и выходных дуг Эта форма непосредственно приводит к обобщению, допускающему кратные входы и выходы. Необходимо только указывать кратность для каждой входной и выходной дуги.

Хэк [116] в конце концов остановился на определении сетей Петри в виде четверки где, как обычно, множество позиций, множество переходов, функции, ставящие в соответствие позициям и переходам количество фишек, необходимых для входа или образованных для выхода Следовательно, переход можно запустить только в том случае, если по крайней мере фишек находятся в каждой позиции Переход запускается путем удаления фишек из каждой входной позиции и помещения фишек в каждую выходную позицию. Функции могут быть представлены матрицами.

Питерсон в своей диссертации [236] попытался объединить переходы и их входы и выходы, определяя переход как упорядоченную пару комплектов позиций: Первая компонента пары — комплект входов перехода; вторая — комплект выходов перехода. Это сводит множество примитивных понятий теории к позициям и фишкам, так как переходы являются структурами, составленными из позиций. Такой подход особенно полезен для простого определения переходов при построении сети Петри.

Эти определения отличаются от представленных здесь только разницей в обозначениях. В большинстве работ по сетям Петри именно это имеет место: различие в определениях проявляется только в обозначениях. Однако в некоторых случаях определения могут ограничивать класс сетей Петри тем, что не допускаются кратные входные и выходные дуги или существует ограничение на форму переходов, т. е. требуется, чтобы переходы имели непустые множества входных и выходных позиций или входные и выходные позиции перехода не должны совпадать (без петель). Но, как мы покажем в гл. 5, даже эти различия не имеют большого значения.

Упражнения

(см. скан)

2.7. Замечания к литературе

Для дальнейшего знакомства с сетями Петри, вероятно, лучше всего начать с обзоров [20, 238] в Computing Surveys. Почти в любой работе несколько первых разделов посвящены основным определениям и обозначениям, поэтому, чтобы найти различия в определениях, достаточно бегло просмотреть начала некоторых из перечисленных в библиографии. Например: [128, 127, 111, 115, 116, 152, 201, 208, 290].

2.8. Темы для дальнейшего изучения

1. Разработайте теорию сетей Петри, разрешающую существование окрашенных фишек. Рассмотрите различия в определениях разрешенных переходов и запусков переходов. Существует по меньшей мере три разумных способа обобщения сетей Петри в случае окрашенных фишек. Укажите те, которые вы сможете предложить, и оцените степень их полезности.

2. Разработайте представление теории сети Петри для научных работников, не связанных с вычислительной техникой. Сравните ваше представление с представлением Хольта [123] и Мельдмана [184, 185].

3. Постройте систему моделирования на ЭВМ для выполнения сети Петри. Для удобного интерфейса пользователя с программой используйте стирающий графический дисплей (с электронно-лучевой трубкой или плазменный) для изображения запусков переходов и последовательного передвижения фишек. Это потребует решения множества вспомогательных задач.

а) Определить язык, имеющий средства вариантов задания для задания сети Петри, ее маркировок.

б) Разработать внутреннее представление сети Петри, ее маркировки и необходимые алгоритмы для моделирования.

в) Обеспечить графическую выдачу. Главная проблема здесь в достижении планарного представления сети (до разумной степени). Следует также подумать о представлении динамических свойств сети (движение фишек).