8.7. Системы замещения и сложения векторов

Если вы бегло просмотрите библиографию, то заметите, что в названиях большинства ссылок упоминаются не сети Петри, а системы сложения векторов. Системы сложения векторов были введены Карпом и Миллером [148] как математическое средство анализа систем параллельных процессов. Благодаря их простому математическому определению системы сложения векторов обычно используются для формального доказательства свойств сетей Петри или подобных систем.

Определение 8.2. Система сложения векторов V есть пара где множество из векторов, называемых базисными векторами или векторами смещения. Вектор есть начальный вектор. Все векторы состоят из целых величин. Элементы неотрицательны.

Множество достижимости системы сложения векторов V обозначается и может быть определено рекурсивно с помощью следующего определения:

Определение 8.3. Множество достижимости для системы сложения векторов есть наименьшее множество, для которого верно, что:

2. Если то либо посредством следующего определения:

Определение если существует такая последовательность базисных векторов, что

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

Аналогично система сложения векторов может быть преобразована в эквивалентную сеть Петри использованием позиций для компонент векторов и переходов для представления базисных

векторов. На рис. 8.19 иллюстрируется эквивалентность этих двух моделей.

Фактически система сложения векторов эквивалентна сетям Петри без петель. Напомним, что в присутствии петель изменение может быть нулевым, а число фишек в позиции из петли должно быть ненулевым. Это не уменьшает мощность системы сложения векторов, поскольку мы видели (в разд. 5.3), что сети Петри без петель эквивалентны обычным сетям Петри.

Рис. 8.19. Сеть Петри и эквивалентная ей система сложения векторов.

Однако для более непосредственного моделирования сетей Петри с петлями в модели, подобной системе сложения векторов, Келлер определил системы замещения векторов [150].

Определение 8.5. Система замещения векторов состоит из начального вектора пар векторов таких, что

Векторы называются векторами проверки. Множество достижимости переопределяется так, что принадлежит множеству достижимости, и если х входит в негой то также входит в множество достижимости.

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

Добавляя системы сложения векторов и системы замещения векторов в нашу иерархию, получаем иерархию, изображенную на рис. 8.20. Важность систем сложения векторов и систем замещения векторов заключается в их простом математическом определении и полезности этого определения для доказательства математических свойств систем.

(кликните для просмотра скана)