Система векторного сложения

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

Достижимость в системах сложения векторов аккермановская -полная (и, следовательно, неэлементарная ). ^[3]^[4]

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

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

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

VAS — это конечное множество $V\subseteq \mathbb {Z} ^{d}$ для некоторых $d\geq 1$ .
VASS . — это конечный ориентированный граф $(Q,T)$ такой, что $T\subseteq Q\times \mathbb {Z} ^{d}\times Q$ для некоторых $d>0$ .

Переходы

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

См. также

Ссылки

^ Карп, Ричард М.; Миллер, Раймонд Э. (май 1969 г.). «Схемы параллельных программ» . Журнал компьютерных и системных наук . 3 (2): 147–195. дои : 10.1016/S0022-0000(69)80011-5 .
^ Хопкрофт, Джон Э.; Пансио, Жан-Жак (1979). «О проблеме достижимости пятимерных систем сложения векторов». Теоретическая информатика . 8 (2): 135–159. дои : 10.1016/0304-3975(79)90041-0 . hdl : 1813/6102 .
^ Червинский, Войцех; Орликовский, Лукаш (2021). Достижимость в системах сложения векторов является полной по Аккерману . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS), 2021 г. arXiv : 2104.13866 .
^ Леру, Жером (2021). Проблема достижимости сетей Петри не является примитивно-рекурсивной . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS), 2021 г. arXiv : 2104.12695 .

[1] Карп, Ричард М.; Миллер, Раймонд Э. (май 1969 г.). «Схемы параллельных программ» . Журнал компьютерных и системных наук . 3 (2): 147–195. дои : 10.1016/S0022-0000(69)80011-5 .

[2] Хопкрофт, Джон Э.; Пансио, Жан-Жак (1979). «О проблеме достижимости пятимерных систем сложения векторов». Теоретическая информатика . 8 (2): 135–159. дои : 10.1016/0304-3975(79)90041-0 . hdl : 1813/6102 .

[3] Червинский, Войцех; Орликовский, Лукаш (2021). Достижимость в системах сложения векторов является полной по Аккерману . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS), 2021 г. arXiv : 2104.13866 .

[4] Леру, Жером (2021). Проблема достижимости сетей Петри не является примитивно-рекурсивной . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS), 2021 г. arXiv : 2104.12695 .

[1]

[2]

[3]

[4]