Система сложения векторов
-
История и определение
- Система векторного сложения (VAS) была представлена Ричардом М. Карпом и Рэймондом Э. Миллером в 1969 году.
- Джон Э. Хопкрофт и Жан-Жак Пансио обобщили VAS на системы сложения векторов с состояниями (VASS) в 1979 году.
- VAS и VASS эквивалентны сетям Петри, представленным Карлом Адамом Петри.
-
Достижимость и формальные определения
- Достижимость в VAS является полной по Аккерману и неэлементарной.
- VAS состоит из конечного набора целочисленных векторов одинаковой длины.
- VASS — это VAS с управляющими состояниями, представляющий собой конечный ориентированный граф.
-
Переходы и базовая терминология
- VAS: задан вектор u, вектор u + v может быть достигнут за один переход, если v ∈ V и u + v ∈ Nd.
- VASS: задан конфигурация (p, u), конфигурация (q, u + v) может быть достигнута за один переход, если (p, v, q) ∈ T и u + v ∈ Nd.
-
Связанные концепции
- Сеть Петри
- Конечный автомат
- Взаимодействующий конечный автомат
- Технологические сети Кана
- Вычисление процессов
- Модель актера
- Теория следов