ระบบการบวกเวกเตอร์ ( VAS ) เป็นหนึ่งในภาษาการสร้างแบบจำลองทางคณิตศาสตร์หลายภาษาสำหรับการอธิบายระบบแบบกระจาย ระบบการบวกเวกเตอร์ได้รับการแนะนำโดยRichard M. Karpและ Raymond E. Miller ในปี 1969 ^{[ 1 ]}และได้รับการขยายความเป็นระบบการบวกเวกเตอร์ที่มีสถานะ ( VASS ) โดยJohn E. Hopcroftและ Jean-Jacques Pansiot ในปี 1979 ^{[ 2 ]}ทั้ง VAS และ VASS มีความเทียบเท่ากันในหลายๆ ด้านกับเครือข่าย Petriที่ได้รับการแนะนำก่อนหน้านี้โดยCarl Adam Petri

ระบบการบวกเวกเตอร์ประกอบด้วยเซตจำกัดของเวกเตอร์จำนวนเต็ม โดยเวกเตอร์ทั้งหมดมีความยาวเท่ากัน เวกเตอร์เริ่มต้นถือเป็นค่าเริ่มต้นของตัวนับหลายตัว และเวกเตอร์ของระบบการบวกเวกเตอร์ถือเป็นการอัปเดต ค่าของตัวนับเหล่านี้ต้องไม่ลดลงต่ำกว่าศูนย์ กล่าวโดยละเอียดคือ เมื่อกำหนดเวกเตอร์เริ่มต้นที่มีค่าไม่เป็นลบ เวกเตอร์ของระบบการบวกเวกเตอร์สามารถบวกกันได้แบบทีละส่วน โดยที่เวกเตอร์ระหว่างกลางทุกตัวต้องมีค่าไม่เป็นลบ ระบบการบวกเวกเตอร์ที่มีสถานะคือระบบการบวกเวกเตอร์ที่มีสถานะควบคุม กล่าวโดยละเอียดคือ เป็นกราฟทิศทาง จำกัด ที่มีส่วนโค้งกำกับด้วย เวกเตอร์ จำนวนเต็มระบบการบวกเวกเตอร์มีข้อจำกัดเดียวกันคือ ค่าของตัวนับต้องไม่ลดลงต่ำกว่าศูนย์

ระบบการบวกเวกเตอร์สามารถมองได้ว่าเป็นเครื่องนับ แบบอ่อน ซึ่งไม่สามารถทดสอบได้ว่าตัวนับเป็นศูนย์ (แต่สามารถตรวจสอบได้ว่าตัวนับเป็นบวก โดยการพยายามลดค่าตัวนับลง หากการทดสอบล้มเหลว การทำงานจะสิ้นสุดลง)

• VAS คือเซตจำกัดสำหรับบางค่า${\displaystyle V\subseteq \mathbb {Z} ^{d}}$${\displaystyle d\geq 1}$
• VASS คือกราฟทิศทาง จำกัดซึ่งเป็นไปตาม เงื่อนไขที่ว่าสำหรับบางค่า${\displaystyle (Q,T)}$${\displaystyle T\subseteq Q\times \mathbb {Z} ^{d}\times Q}$${\displaystyle d>0}$

• ให้VAS เป็นระบบ VAS เมื่อกำหนดเวกเตอร์เวกเตอร์สามารถเข้าถึงได้ในการเปลี่ยนสถานะเดียวถ้าและ${\displaystyle V\subseteq \mathbb {Z} ^{d}}$${\displaystyle u\in \mathbb {N} ^{d}}$${\displaystyle u+v}$${\displaystyle v\in V}$${\displaystyle u+v\in \mathbb {N} ^{d}}$
• ให้VASS เป็นตัวจัดการสถานะ (VASS) เมื่อกำหนดสถานะ หนึ่ง แล้ว สถานะถัดไปสามารถเข้าถึงได้ในการเปลี่ยนสถานะเพียงครั้งเดียวหากและ${\displaystyle (Q,T)}$${\displaystyle (p,u)\in Q\times \mathbb {N} ^{d}}$${\displaystyle (q,u+v)}$${\displaystyle (p,v,q)\in T}$${\displaystyle u+v\in \mathbb {N} ^{d}}$

VAS เห็นได้ชัดว่าเป็นกรณีพิเศษของ VASS ในทางกลับกัน VASS ที่มีมิติnสามารถจำลองได้ด้วย VAS ที่มีมิติn + 3 ดัง ที่HopcroftและPansiotแสดงไว้^{[ 3 ]} ในระบบนี้ พิกัดเพิ่มเติมสามพิกัดจะเข้ารหัสสถานะ การเปลี่ยนสถานะแต่ละครั้งของ VASS จะถูกจำลองด้วยลำดับของการเปลี่ยนสถานะ VAS สามครั้ง โดยสองครั้งแรกจะจัดการเฉพาะพิกัดที่เข้ารหัสสถานะเท่านั้น

สามารถมองโครง ข่ายเพทรีว่าเป็น VASS ได้: ลองพิจารณาโครงข่ายเพทรีโดยที่ ${\displaystyle (S,T,W)}$

• ${\displaystyle S=\{1,\dots ,n\}}$เป็นเซตจำกัดของสถานที่
• Tคือเซตของการเปลี่ยนสถานะ ที่มีจำนวนจำกัด
• ${\displaystyle W:(S\times T)\cup (T\times S)\to \mathbb {N} }$ระบุจำนวนโทเค็นที่การเปลี่ยนสถานะใช้และสร้างขึ้น

จากนั้น การทำเครื่องหมายบนเน็ตสามารถมองได้ว่าเป็นเวกเตอร์ในโดยที่และการเปลี่ยนสถานะtเป็นคู่ของการเปลี่ยนสถานะ VASS โดยที่qเป็นสถานะควบคุมเสริมและ ในทำนองเดียวกัน VAS สามารถกำหนดเป็นเน็ต Petri ได้ ${\displaystyle \mathbb {N} ^{d}}$${\displaystyle d=|S|}$${\displaystyle (p,v,q),(q,v',p)}$${\displaystyle v_{i}=-W(i,t)}$${\displaystyle v'_{j}=W(t,j)}$

ปัญหาการเข้าถึงได้สำหรับโครงข่ายเพทรีคือการตัดสินใจว่า เมื่อกำหนด VAS(S) และสถานะหนึ่ง (เวกเตอร์ในกรณีของ VAS เวกเตอร์และสถานะควบคุมในกรณีของ VASS) สถานะอื่นที่กำหนดนั้นสามารถเข้าถึงได้จากสถานะดังกล่าวโดยลำดับการเปลี่ยนสถานะแบบจำกัดหรือไม่

ปัญหานี้ได้รับการพิสูจน์แล้วว่าเป็นปัญหาEXPSPACE -hard ^{[ 4 ]}หลายปีก่อนที่จะได้รับการพิสูจน์ว่าสามารถตัดสินได้เลย^{[ 5 ]} ในปี 2021 ปัญหานี้ได้รับการพิสูจน์แล้วว่าเป็นปัญหาAckermann-complete (ดังนั้นจึงไม่ใช่primitive recursive ) โดยอิสระจาก Jerome Leroux ^{[ 6 ]} และโดย Wojciech Czerwiński และ Łukasz Orlikowski ^{[ 7 ]}ขอบเขตบนแบบ Ackermannian มาจาก Leroux และ Schmitz ^{[ 8 ]}ซึ่งอัลกอริทึมของพวกเขายอมรับ ขอบเขตบน แบบ primitive-recursiveเมื่อมิติเป็นค่าคงที่

ปัญหาการเข้าถึงร่วมกัน (หรือที่เรียกว่าการเข้าถึงแบบย้อนกลับได้) ถามถึงสถานะสองสถานะxและyว่าxสามารถเข้าถึงได้จากyหรือไม่ และในทางกลับกัน ปัญหานี้ง่ายกว่าการเข้าถึงแบบทิศทางเดียวมาก และได้รับการพิสูจน์แล้วว่าสมบูรณ์แบบ EXPSPACE ^{[ 9 ]}

เมื่อกำหนดสถานะสองสถานะของ VAS คือxและyคำถามเรื่องความสามารถในการครอบคลุมจะถามว่ามีลำดับการเปลี่ยนผ่านที่นำสถานะเริ่มต้นxไปสู่สถานะที่(การเปรียบเทียบเป็นแบบองค์ประกอบต่อองค์ประกอบ) หรือไม่ ใน VASS เรายังระบุสถานะควบคุมด้วย และปัญหานี้เทียบเท่ากับปัญหาที่ (ดูเหมือน) ง่ายกว่าของการถามว่าสถานะควบคุมที่กำหนดqสามารถเข้าถึงได้จากสถานะเริ่มต้น หรือ ไม่ ปัญหาความสามารถในการครอบคลุมนั้นสมบูรณ์แบบ EXPSPACE ^{[ 4 ]}${\displaystyle x'}$${\displaystyle x'\geq y}$${\displaystyle (p,x)}$

ปัญหาขอบเขตสำหรับ VASS คือ: เมื่อกำหนดสถานะเริ่มต้นแล้วเซตของสถานะสามารถเข้าถึงได้จากจำกัดหรือไม่? ปัญหาการตัดสินใจนี้ยังเป็นปัญหา EXPSPACE-complete อีกด้วย^{[ 10 ]}${\displaystyle (p,x)}$${\displaystyle (p,x)}$

• โครงข่ายเพทรี
• เครื่องจักรสถานะจำกัด
• เครื่องจักรสถานะจำกัดที่สื่อสารกันได้
• เครือข่ายกระบวนการของคาน
• แคลคูลัสกระบวนการ
• นักแสดง นายแบบ
• ทฤษฎีร่องรอย