نظام جمع المتجهات

يُعد نظام جمع المتجهات ( VAS ) أحد لغات النمذجة الرياضية العديدة لوصف الأنظمة الموزعة . وقد طُوِّرت أنظمة جمع المتجهات بواسطة ريتشارد إم. كارب وريموند إي. ميلر في عام 1969، ^{[ 1 ]} ثم عُمِّمت إلى أنظمة جمع المتجهات ذات الحالات ( VASS ) بواسطة جون إي. هوبكروفت وجان جاك بانسيو في عام 1979. ^{[ 2 ]} ويُعد كل من VAS وVASS مكافئين من نواحٍ عديدة لشبكات بيتري التي قدمها كارل آدم بيتري سابقًا .

يتكون نظام جمع المتجهات من مجموعة محدودة من المتجهات الصحيحة، جميعها متساوية الطول. يُنظر إلى المتجه الابتدائي على أنه القيم الأولية لعدة عدادات، وتُعتبر متجهات نظام جمع المتجهات بمثابة تحديثات. لا يجوز أن تقل قيم هذه العدادات عن الصفر. بتعبير أدق، عند وجود متجه ابتدائي ذي قيم غير سالبة، يمكن جمع متجهات نظام جمع المتجهات عنصرًا بعنصر، بشرط أن تكون جميع المتجهات الوسيطة ذات قيم غير سالبة. نظام جمع المتجهات ذو الحالات هو نظام جمع متجهات مزود بحالات تحكم. بتعبير أدق، هو رسم بياني موجه محدود، حيث تُسمى الأقواس بمتجهات صحيحة . تخضع أنظمة جمع المتجهات ذات الحالات لنفس القيد، وهو ألا تقل قيم العدادات عن الصفر.

يمكن اعتبار أنظمة جمع المتجهات بمثابة آلة عداد ضعيفة ، غير قادرة على اختبار أن العداد يساوي صفرًا (لكنها تستطيع التحقق من أن العداد موجب، عن طريق محاولة إنقاصه. إذا فشل الاختبار، ينتهي التنفيذ).

• مجموعة القيم الذاتية هي مجموعة منتهية${\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 هو حالة خاصة من نظام VASS. من جهة أخرى، يمكن محاكاة نظام VASS ذي البعد n بنظام VAS ذي البعد n +3، كما أوضح هوبكروفت وبانسيوت . ^{[ 3 ]} في هذا النظام، تُشفّر الإحداثيات الثلاث الإضافية الحالة. تتم محاكاة كل انتقال في نظام VASS بتسلسل من ثلاثة انتقالات، حيث يُعالج الانتقالان الأولان فقط إحداثيات تشفير الحالة.

يمكن اعتبار شبكة بتري بمثابة نظام VASS: لنفترض شبكة بتري${\displaystyle (S,T,W)}$، أين

• ${\displaystyle S=\{1,\dots ,n\}}$هي مجموعة محدودة من الأماكن
• T هي مجموعة منتهية من الانتقالات
• ${\displaystyle W:(S\times T)\cup (T\times S)\to \mathbb {N} }$يحدد عدد الرموز المميزة التي يستهلكها وينتجها الانتقال.

عندئذٍ يمكن اعتبار علامة الشبكة بمثابة متجه في${\displaystyle \mathbb {N} ^{d}}$، أين${\displaystyle d=|S|}$، وانتقال t كزوج من انتقالات VASS${\displaystyle (p,v,q),(q,v',p)}$حيث q هي حالة تحكم مساعدة،${\displaystyle v_{i}=-W(i,t)}$و ${\displaystyle v'_{j}=W(t,j)}$وبالمثل، يمكن صياغة مقياس القيمة المضافة كشبكة بتري.

• شبكة بتري
• آلة الحالة المحدودة
• آلة الحالة المحدودة المتصلة
• شبكات عملية كان
• حساب العمليات
• عارض أزياء ممثل
• نظرية الأثر