Система сложения векторов - Vector addition system

А система сложения векторов (VAS) является одним из нескольких языков математического моделирования для описания распределенные системы. Системы сложения векторов были введены Ричард М. Карп и Раймонд Э. Миллер в 1969 г.,^[1] и обобщены на системы сложения векторов с состояниями (VASS) к Джон Э. Хопкрофт и Жан-Жак Пансио в 1979 году.^[2] И VAS, и VASS во многом эквивалентны Сети Петри представленный ранее Карл Адам Петри.

Пример сложения вектора с состояниями. В этом VASS, например, q (1,2) может быть достигнуто из p (0,0), но q (0,0) не может быть достигнуто из p (0,0).

Неформальное определение

А система сложения векторов состоит из конечного набора целое число векторов. Начальный вектор рассматривается как начальные значения нескольких счетчиков, а векторы VAS - как обновления. Эти счетчики никогда не могут опуститься ниже нуля. Точнее, для начального вектора с неотрицательными значениями векторы VAS могут быть добавлены покомпонентно, при условии, что каждый промежуточный вектор имеет неотрицательные значения. А система сложения векторов с состояниями VAS, оснащенный управляющими состояниями. Точнее, это конечный ориентированный граф с дуги помеченный целое число векторы. У VASS есть то же ограничение, что значения счетчика никогда не должны опускаться ниже нуля.

Формальные определения и основная терминология

• А ВАШ конечное множество ${ Displaystyle V substeq mathbb {Z} ^ {d}}$ для некоторых ${ displaystyle d geq 1}$.
• А ВАСС конечный ориентированный граф ${ displaystyle (Q, T)}$ такой, что ${ Displaystyle Т подстекла Q раз mathbb {Z} ^ {d} раз Q}$ для некоторых ${ displaystyle d> 0}$.

Переходы

• Позволять ${ Displaystyle V substeq mathbb {Z} ^ {d}}$ быть VAS. Учитывая вектор ${ Displaystyle и в mathbb {N} ^ {d}}$, вектор ${ displaystyle u + v}$ возможно достиг, за один переход, если ${ displaystyle v in V}$ и ${ Displaystyle и + v in mathbb {N} ^ {d}}$.
• Позволять ${ displaystyle (Q, T)}$ быть ВАСОМ. Учитывая конфигурация ${ Displaystyle (р, и) в Q раз mathbb {N} ^ {d}}$, конфигурация ${ Displaystyle (д, и + v)}$ возможно достиг, за один переход, если ${ displaystyle (p, v, q) in T}$ и ${ Displaystyle и + v in mathbb {N} ^ {d}}$.

Смотрите также

• Сеть Петри
• Конечный автомат
• Общающийся конечный автомат

Рекомендации