Vektortilläggssystem

Ett vektoradditionssystem (VAS) är ett av flera matematiska modelleringsspråk för beskrivning av distribuerade system . Vektoradditionssystem introducerades av Richard M. Karp och Raymond E. Miller 1969 och generaliserades till vektoradditionssystem med tillstånd (VASS) av John E. Hopcroft och Jean-Jacques Pansiot 1979. Både VAS och VASS är likvärdiga i många sätt att Petri-nät introducerade tidigare av Carl Adam Petri .

Exempel på vektoraddition med tillstånd. I denna VASS kan t.ex. q(1,2) inte nås från p(0,0), men q(0,0) kan nås från p(0,0).

Nåbarheten i vektoradditionssystem är Ackermann -komplett (och därmed icke-elementär ).

Informell definition

Ett vektoradditionssystem består av en ändlig uppsättning heltalsvektorer . En initial vektor ses som de initiala värdena för flera räknare, och vektorerna för VAS ses som uppdateringar. Dessa räknare får aldrig falla under noll. Mer exakt, givet en initial vektor med icke-negativa värden, kan vektorerna för VAS adderas komponentvis, givet att varje mellanvektor har icke-negativa värden. Ett vektoradditionssystem med tillstånd är en VAS utrustad med kontrolltillstånd. Mer exakt är det en ändlig riktad graf med bågar märkta av heltalsvektorer . VASS har samma begränsning att räknarvärdena aldrig ska falla under noll.

Formella definitioner och grundläggande terminologi

Ett VAS är en finit mängd $V\subseteq \mathbb {Z} ^{d}$ för vissa $d\geq 1$ .
En VASS är en finit riktad graf $(Q,T)$ så att $T\subseteq Q\times \mathbb {Z} ^{d}\ gånger Q$ för vissa $d>0$ .

Övergångar

Låt $V\subseteq \mathbb {Z} ^{d}$ vara ett VAS. Givet en vektor ${\displaystyle u\in \mathbb {N} ^{d}} ,$ kan vektorn $u+v$ nås , i en övergång, om ${\ displaystyle v\in V}$ och $u+v\in \mathbb {N} ^{d}$ .
Låt $(Q,T)$ vara en VASS. Givet en konfiguration $(p,u)\in Q\times \mathbb {N} ^{d}$ , konfigurationen $( q,u+v)$ kan nås , i en övergång, om $(p,v,q)\in T$ och $u +v\in \mathbb {N} ^{d}$ .

Se även