Systém sčítání vektorů - Vector addition system

A vektorový sčítací systém (VAS) je jedním z několika jazyků matematického modelování pro popis distribuované systémy. Systémy sčítání vektorů byly zavedeny Richard M. Karp a Raymond E. Miller v roce 1969,^[1] a zobecnit na vektorové systémy sčítání se stavy (VASS) podle John E. Hopcroft a Jean-Jacques Pansiot v roce 1979.^[2] VAS i VASS jsou v mnoha ohledech rovnocenné Petriho sítě představil dříve Carl Adam Petri.

Příklad přidání vektoru se stavy. V tomto VASS lze například dosáhnout q (1,2) z p (0,0), ale q (0,0) nelze dosáhnout z p (0,0).

Neformální definice

A vektorový sčítací systém se skládá z konečné sady celé číslo vektory. Počáteční vektor je považován za počáteční hodnoty více čítačů a vektory VAS jsou považovány za aktualizace. Tyto počitadla nemusí nikdy klesnout pod nulu. Přesněji řečeno, vzhledem k počátečnímu vektoru s nezápornými hodnotami lze vektory VAS přidat po částech za předpokladu, že každý mezilehlý vektor má nezáporné hodnoty. A vektorový sčítací systém se stavy je VAS vybavený kontrolními stavy. Přesněji řečeno, je to konečný řízený graf s oblouky označeno celé číslo vektory. VASS mají stejné omezení, že hodnoty čítače by nikdy neměly klesnout pod nulu.

Formální definice a základní terminologie

• A VAS je konečná množina ${ displaystyle V subseteq mathbb {Z} ^ {d}}$ pro některé ${ displaystyle d geq 1}$.
• A VASS je konečný řízený graf ${ displaystyle (Q, T)}$ takhle ${ displaystyle T subseteq Q krát mathbb {Z} ^ {d} krát Q}$ pro některé ${ displaystyle d> 0}$.

Přechody

• Nechat ${ displaystyle V subseteq mathbb {Z} ^ {d}}$ být VAS. Vzhledem k vektoru ${ displaystyle u in mathbb {N} ^ {d}}$, vektor ${ displaystyle u + v}$ může být dosáhla, v jednom přechodu, pokud ${ displaystyle v ve V}$ a ${ displaystyle u + v in mathbb {N} ^ {d}}$.
• Nechat ${ displaystyle (Q, T)}$ být VASS. Vzhledem k tomu, konfigurace ${ displaystyle (p, u) v Q krát mathbb {N} ^ {d}}$, konfigurace ${ displaystyle (q, u + v)}$ může být dosáhla, v jednom přechodu, pokud ${ displaystyle (p, v, q) v T}$ a ${ displaystyle u + v in mathbb {N} ^ {d}}$.

Viz také

• Petriho síť
• Konečný stavový stroj
• Komunikující stroj konečného stavu

Reference