पेट्री नेट

एक पेट्री नेट, जिसे एक स्थान/संक्रमण (पीटी) नेट के रूप में भी जाना जाता है, वितरित प्रणाली के विवरण के लिए कई गणितीय मॉडलिंग भाषाओं में से एक होता है। यह असतत घटना गतिशील प्रणाली का एक वर्ग है। पेट्री नेट एक निर्देशित द्विपक्षीय ग्राफ है जिसमें दो प्रकार के तत्व, स्थान और संक्रमण होते है। स्थान तत्वों को सफेद घेरे के रूप में दर्शाया गया है और संक्रमण तत्वों को आयतों के रूप में दर्शाया गया है। किसी स्थान में कितने भी टोकन हो सकते है, जिन्हें काले घेरों के रूप में दर्शाया गया है। यदि इनपुट के रूप में इससे जुड़े सभी स्थानों में कम से कम एक टोकन हो तो एक संक्रमण सक्षम हो जाता है। कुछ स्रोत कहते है कि रासायनिक प्रक्रियाओं का वर्णन करने के उद्देश्य से अगस्त 1939 में कार्ल एडम पेट्री द्वारा 13 साल की उम्र में पेट्री नेट का आविष्कार किया गया था।

यूएमएल गतिविधि आरेख, बिजनेस प्रोसेस मॉडल और नोटेशन, और घटना-संचालित प्रक्रिया श्रृंखला जैसे उद्योग मानकों की तरह, पेट्री नेट चरणवार प्रक्रियाओं के लिए ग्राफिकल नोटेशन प्रदान करते है जिसमें पसंद, पुनरावृत्ति और समवर्ती निष्पादन सम्मलित होते है। इन मानकों के विपरीत, पेट्री नेट के पास प्रक्रिया विश्लेषण के लिए एक सुविकसित गणितीय सिद्धांत के साथ उनके निष्पादन शब्दार्थ की एक त्रुटिहीन गणितीय परिभाषा है।

File:Animated Petri net commons.gif

(ए) पेट्री नेट प्रक्षेपवक्र उदाहरण

ऐतिहासिक पृष्ठभूमि

जर्मन कंप्यूटर वैज्ञानिक कार्ल एडम पेट्री, जिनके नाम पर इस तरह की संरचनाओं का नाम दिया गया है, उन्होने अपने 1962 के निबंध कॉम्यूनिकेशन मिट ऑटोमेटन में पेट्री नेट का बड़े पैमाने पर विश्लेषण किया था।

पेट्री नेट मूल बातें

एक पेट्री नेट में स्थान, संक्रमण और ग्राफ सिद्धांत सम्मलित होते है। चाप एक स्थान से संक्रमण या इसके विपरीत चलते है, स्थानों के बीच या संक्रमण के बीच कभी नहीं चलते है। जिन स्थानों से चाप एक संक्रमण तक चलता है उन्हें संक्रमण के इनपुट स्थान कहा जाता है, जिन स्थानों पर संक्रमण से चाप चलते है उन्हें संक्रमण के आउटपुट स्थान कहा जाता है।

ग्राफिक रूप से, पेट्री नेट में स्थानों में असतत संख्या में चिह्न हो सकते है जिन्हें टोकन कहा जाता है। स्थानों पर टोकन का कोई भी वितरण अंकन कहे जाने वाले नेट के विन्यास का प्रतिनिधित्व करता है। पेट्री नेट आरेख से संबंधित एक अमूर्त अर्थ में, पेट्री नेट का एक संक्रमण सक्रिय हो सकता है यदि यह सक्षम है, अर्थात इसके सभी इनपुट स्थानों में पर्याप्त टोकन है, जब संक्रमण प्रारंभ होता है, तो यह आवश्यक इनपुट टोकन का उपभोग करता है, और इसके आउटपुट स्थानों में टोकन बनाता है।

जब तक एक निष्पादन नीति (उदाहरण के लिए संक्रमणों का एक सख्त क्रम, पूर्वता का वर्णन) परिभाषित नहीं किया जाता है, पेट्री नेट का निष्पादन गैर-नियतात्मक होता है: जब एक ही समय में कई संक्रमण सक्षम होते है, तो वे किसी भी क्रम में सक्रिय हो जाते है।

चूंकि फायरिंग गैर-नियतात्मक है, और कई टोकन नेट में कहीं भी उपस्तिथ हो सकते है (यहां तक ​​कि एक ही स्थान पर), पेट्री नेट वितरित प्रणाली के समवर्ती व्यवहार के मॉडलिंग के लिए उपयुक्त होती है।

औपचारिक परिभाषा और बुनियादी शब्दावली

पेट्री नेट राज्य संक्रमण प्रणाली है जो प्राथमिक नेट नामक नेटों के एक वर्ग का विस्तार करती है।

परिभाषा 1. 'नेट' एक टपल है $N=(P,T,F)$ जहां

1. $P$ और $T$ क्रमशः स्थानों और संक्रमणों के असंयुक्त परिमित समुच्चय है।
2. $F\subseteq (P\times T)\cup (T\times P)$ (निर्देशित) चापों (या प्रवाह संबंधों) का एक सेट है।

'परिभाषा 2.' नेट एन = (पी, टी, एफ) दिया गया है, विन्यास एक सेट सी है जिससे कि सी <बड़ा>⊆</बड़ा> पी है।

सक्षम संक्रमण के साथ पेट्री नेट।

File:Petri Net B.jpg

पेट्री नेट जो संक्रमण के बाद प्रारंभ होता है (ऊपर की आकृति में प्रारंभिक पेट्री नेट)।

परिभाषा 3. एक प्रारंभिक नेट EN = (N, C) रूप का नेट है जहां

1. N = (P, T, F) एक नेट है।
2. 'सी' ऐसा है कि सी <बड़ा>⊆</बड़ा> पी एक विन्यास है।

परिभाषा 4. एक पेट्री नेट पीएन = (एन, एम, डब्ल्यू) के रूप का नेट है, जो प्राथमिक नेट का विस्तार करता है जिससे कि

1. N = (P, T, F) एक नेट है।
2. M : P → Z एक जगह मल्टीसेट है, जहां Z एक गणनीय सेट है। एम विन्यास की अवधारणा का विस्तार करता है और इसे सामान्यतः पेट्री नेट डायग्राम के संदर्भ में मार्किंग के रूप में वर्णित किया जाता है।
3. W : F → Z एक चाप मल्टीसेट है, जिससे कि प्रत्येक चाप के लिए गिनती (या वजन) चाप की बहुलता का माप किया जाता है।

यदि एक पेट्री नेट एक प्राथमिक नेट के बराबर है, तो Z काउंटेबल सेट {0,1} हो सकता है और P में वे तत्व जो M के अनुसार 1 को मैप करते है, एक विन्यास बनाते है। इसी तरह, यदि एक पेट्री नेट प्राथमिक नेट नहीं है, तो मल्टीसेट M की व्याख्या विन्यास के गैर-सिंगलटन सेट का प्रतिनिधित्व करने के रूप में की जा सकती है। इस संबंध में, 'एम' पेट्री नेट के लिए प्रारंभिक नेट के लिए विन्यास की अवधारणा का विस्तार करता है।

पेट्री नेट के आरेख में, स्थानों को पारंपरिक रूप से मंडलियों के साथ चित्रित किया गया है, लंबे संकीर्ण आयतों के साथ संक्रमण और एक तरफा तीर के रूप में चाप जो स्थानों के संक्रमण या संक्रमण के स्थानों के कनेक्शन दिखाते है। यदि आरेख एक प्राथमिक नेट का होता है, तो विन्यास में उन स्थानों को पारंपरिक रूप से मंडलियों के रूप में दर्शाया जाता है, जहां प्रत्येक वृत्त में एक बिंदु सम्मलित होता है जिसे टोकन कहा जाता है। पेट्री नेट के दिए गए आरेख में, स्थान चक्रों में एक से अधिक टोकन सम्मलित हो सकते है, यह दिखाने के लिए कि विन्यास में कोई स्थान कितनी बार दिखाई देता है। संपूर्ण पेट्री नेट आरेख पर वितरित टोकन के विन्यास को अंकन कहा जाता है।

शीर्ष आकृति में (दाएं देखें), स्थान p1 संक्रमण t का एक इनपुट स्थान है, जबकि, स्थान p2 उसी संक्रमण के लिए एक आउटपुट स्थान है। बता दें कि PN0 (ऊपरी आकृति) कॉन्फ़िगर किए गए M0 के साथ एक पेट्री नेट है, और PN1 (नीचे का आंकड़ा) कॉन्फ़िगर किए गए M1 के साथ एक पेट्री नेट है। PN0 का विन्यास संपत्ति के माध्यम से संक्रमण टी को सक्षम करता है कि सभी इनपुट स्थानों में टोकन की पर्याप्त संख्या होती है। केवल एक बार संक्रमण सक्षम हो जाने पर संक्रमण सक्रिय हो जाता है। इस उदाहरण में, संक्रमण टी की फायरिंग एक नक्शा उत्पन्न करती है जिसमें M0 की छवि में मार्किंग कॉन्फ़िगर किया गया M1 होता है और पेट्री नेट PN1 में परिणाम होता है, जो नीचे की आकृति में देखा जाता है। आरेख में, एक संक्रमण के लिए फायरिंग नियम को इसके इनपुट स्थानों से संबंधित इनपुट चाप्स की बहुलता के बराबर कई टोकन घटाकर और संबंधित की बहुलता के बराबर आउटपुट स्थानों पर टोकन की एक नई संख्या जमा करके चित्रित किया जा सकता है।

टिप्पणी 1. "बराबर या अधिक" का त्रुटिहीन अर्थ फायरिंग नियम में Z पर लागू होने वाले जोड़ के त्रुटिहीन बीजगणितीय गुणों पर निर्भर करेगा, जहां बीजगणितीय गुणों पर सूक्ष्म भिन्नताएं पेट्री नेट के अन्य वर्गों को जन्म दे सकती है, उदाहरण के लिए, बीजगणितीय पेट्री नेट।

निम्नलिखित औपचारिक परिभाषा शिथिल रूप से (पीटरसन 1981) पर आधारित है। कई वैकल्पिक परिभाषाएँ उपस्तिथ है।

वाक्य - विन्यास

एक पेट्री नेट ग्राफ (कुछ लोगों द्वारा पेट्री नेट कहा जाता है, लेकिन नीचे देखें) एक 3-टपल है $(S,T,W)$, जहाँ

• S स्थानों का परिमित समुच्चय है
• T संक्रमणों का परिमित समुच्चय है
• S और T असंयुक्त समुच्चय है, अर्थात कोई भी वस्तु स्थान और संक्रमण दोनों नहीं हो सकती
• $W:(S\times T)\cup (T\times S)\to \mathbb {N}$ निर्देशित किनारों का एक मल्टीसेट है, अर्थात यह प्रत्येक चाप को एक गैर-नकारात्मक पूर्णांक चाप बहुलता (या वजन) प्रदान करता है, ध्यान दें कि कोई चाप दो स्थानों या दो संक्रमणों को नहीं जोड़ सकता है।

प्रवाह संबंध चापों का समुच्चय है: $F=\{(x,y)\mid W(x,y)>0\}$. कई पाठ्यपुस्तकों में, चापों में केवल बहुलता हो सकती है। ये पाठ अधिकांशतः W के अतिरिक्त F का उपयोग करके पेट्री नेट को परिभाषित करते है। इस सम्मेलन का उपयोग करते समय, पेट्री नेट ग्राफ एक द्विदलीय ग्राफ मल्टीग्राफ होता है। $(S\cup T,F)$ नोड विभाजन एस और टी के साथ होता है।

संक्रमण t का प्रीसेट इसके इनपुट स्थानों का सेट है: ${}^{\bullet }t=\{s\in S\mid W(s,t)>0\}$;

इसका पोस्टसेट इसके आउटपुट स्थानों का सेट है: $t^{\bullet }=\{s\in S\mid W(t,s)>0\}$. स्थानों के पूर्व और बाद के सेट की परिभाषाएं समान है।

पेट्री नेट (ग्राफ) का एक अंकन इसके स्थानों का एक मल्टीसेट है, अर्थात मैपिंग $M:S\to \mathbb {N}$. हम कहते है कि अंकन प्रत्येक स्थान को कई टोकन प्रदान करता है।

एक 'पेट्री नेट' (कुछ लोगों द्वारा चिह्नित पेट्री नेट कहा जाता है, ऊपर देखें) एक 4-ट्यूपल है $(S,T,W,M_{0})$, जहाँ

• $(S,T,W)$ पेट्री नेट ग्राफ है,
• $M_{0}$ प्रारंभिक अंकन है, पेट्री नेट ग्राफ का अंकन है।

निष्पादन शब्दार्थ

शब्दों में

• एक संक्रमण फायरिंग t अंकन में M खपत करता है $W(s,t)$ इसके प्रत्येक इनपुट स्थान से टोकन s, और उत्पन्न करता है $W(t,s)$ इसके प्रत्येक आउटपुट स्थानों में टोकन s
• एक संक्रमण सक्षम है (यह आग लग सकता है) में M यदि इसके इनपुट स्थान में पर्याप्त टोकन है तो उपभोग संभव हो सकता है, अर्थात यदि और केवल यदि $\forall s:M(s)\geq W(s,t)$.

हम सामान्यतः इस बात में रुचि रखते है कि क्या हो सकता है जब संक्रमण मनमाने क्रम में लगातार आग लगा सकता है।

हम कहते है कि एक अंकन M' अंकन से पहुंचा जा सकता है M यदि एक चरण में $M{\underset {G}{\longrightarrow }}M'$, हम कहते है कि यह से पहुंच योग्य है M यदि $M{\overset {*}{\underset {G}{\longrightarrow }}}M'$, जहाँ ${\overset {*}{\underset {G}{\longrightarrow }}}$ का स्वतुल्य सकर्मक संवरण है ${\underset {G}{\longrightarrow }}$; अर्थात, यदि यह 0 या अधिक चरणों में पहुंचा जा सकता है।

एक (चिह्नित) पेट्री नेट के लिए $N=(S,T,W,M_{0})$, हम उन फायरिंग में रुचि रखते है जिन्हें प्रारंभिक मार्किंग से प्रारंभ किया जा सकता है $M_{0}$. इसके पहुंच योग्य चिह्नों का सेट है $R(N)\ {\stackrel {D}{=}}\ \left\{M'{\Bigg |}M_{0}{\xrightarrow[{(S,T,W)}]{*}}M'\right\}$ पहुंच योग्यता ग्राफ N संक्रमण संबंध है ${\underset {G}{\longrightarrow }}$ इसके पहुंच योग्य चिह्नों तक ही सीमित है $R(N)$. यह नेट का राज्य अंतरिक्ष है।

ग्राफ के साथ पेट्री नेट के लिए फायरिंग सीक्वेंस G और प्रारंभिक अंकन $M_{0}$ संक्रमणों का क्रम है ${\vec {\sigma }}=\langle t_{1}\cdots t_{n}\rangle$ ऐसा है कि $M_{0}{\underset {G,t_{1}}{\longrightarrow }}M_{1}\wedge \cdots \wedge M_{n-1}{\underset {G,t_{n}}{\longrightarrow }}M_{n}$. फायरिंग सीक्वेंस के सेट को इस रूप में दर्शाया गया है $L(N)$.

परिभाषा पर बदलाव

चाप बहुलता को अस्वीकार करने और चाप डब्ल्यू के बैग को एक साधारण सेट के साथ बदलने के लिए एक सामान्य भिन्नता है, जिसे प्रवाह संबंध कहा जाता है, $F\subseteq (S\times T)\cup (T\times S)$.

यह अभिव्यंजक शक्ति (कंप्यूटर विज्ञान) को सीमित नहीं करता है क्योंकि दोनों एक दूसरे का प्रतिनिधित्व कर सकते है।

देसेल और जुहास (2001) में, क्षमता को स्थानों पर परिभाषित करने की अनुमति दिया था। इस पर नीचे विस्तार के अनुसार चर्चा की गई है।

सदिशों और आव्यूहों के संदर्भ में निरूपण

पेट्री नेट के निशान $(S,T,W,M_{0})$ लंबाई के गैर-नकारात्मक पूर्णांकों के वेक्टर (गणित) के रूप में माना जा सकता है $|S|$.

Error creating thumbnail:

(बी) पेट्री शुद्ध उदाहरण

इसके संक्रमण संबंध को एक जोड़ी के रूप में वर्णित किया जा सकता है $|S|$ द्वारा $|T|$ मैट्रिक्स (गणित):

• $W^{-}$, द्वारा परिभाषित $\forall s,t:W^{-}[s,t]=W(s,t)$
• $W^{+}$, द्वारा परिभाषित $\forall s,t:W^{+}[s,t]=W(t,s).$

फिर उनका अंतर

• $W^{T}=-W^{-}+W^{+}$

मैट्रिक्स गुणा के संदर्भ में पहुंच योग्य चिह्नों का वर्णन करने के लिए निम्नानुसार उपयोग किया जा सकता है।

संक्रमण के किसी भी क्रम के लिए w, लिखना $o(w)$ वेक्टर के लिए जो प्रत्येक संक्रमण को इसकी घटनाओं की संख्या में मैप करता है w. तो हमारे पास है

• $R(N)=\{M\mid \exists w:\ w{\text{ is a firing sequence of }}N\ {\text{ and }}\ M=M_{0}+W^{T}\cdot o(w)\}$.

यह आवश्यक होना चाहिए w फायरिंग सीक्वेंस है, संक्रमणों के मनमाना अनुक्रमों की अनुमति देना सामान्यतः एक बड़ा सेट उत्पन्न करता है।

$$W^{-}={\begin{bmatrix}*&t1&t2\\p1&1&0\\p2&0&1\\p3&0&1\\p4&0&0\end{bmatrix}},\ W^{+}={\begin{bmatrix}*&t1&t2\\p1&0&1\\p2&1&0\\p3&1&0\\p4&0&1\end{bmatrix}},\ W^{T}={\begin{bmatrix}*&t1&t2\\p1&-1&1\\p2&1&-1\\p3&1&-1\\p4&0&1\end{bmatrix}}$$

$$M_{0}={\begin{bmatrix}1&0&2&1\end{bmatrix}}$$

श्रेणी-सैद्धांतिक सूत्रीकरण

मेसेगुएर और मोंटानारी को एक प्रकार की सममित मोनोइडल श्रेणियां माना जाता है जिन्हें पेट्री श्रेणियों के रूप में जाना जाता है।

पेट्री नेट के गणितीय गुण

पेट्री नेट को रोचक बनाने वाली एक बात यह है कि वे मॉडलिंग शक्ति और विश्लेषण क्षमता के बीच संतुलन प्रदान करते है: पेट्री नेट के लिए समवर्ती प्रणालियों के बारे में बहुत सी चीजें स्वचालित रूप से निर्धारित की जा सकती है, चूंकि उनमें से कुछ चीजें सामान्य रूप से निर्धारित करने के लिए बहुत महंगी होती है। पेट्री नेट के कई उपवर्गों का अध्ययन किया गया है जो अभी भी समवर्ती प्रणालियों के रोचक वर्गों का मॉडल बना सकते है, जबकि ये समस्याएं आसान हो जाती है।

पेट्री नेट और कुछ उपवर्गों के लिए निर्णायकता और जटिलता परिणामों के साथ इस तरह की निर्णय समस्याओं का अवलोकन एस्पार्ज़ा और नीलसन (1995) में पाया जा सकता है।

गम्यता

पेट्री नेट के लिए रीचबिलिटी की समस्या यह तय करना है कि पेट्री नेट एन और मार्किंग एम दिया गया है या नहीं $M\in R(N)$.

यह ऊपर परिभाषित गम्यता-ग्राफ चलने की स्थिति है, जब तक या अनुरोधित-अंकन नहीं हो जाता है या अब नहीं मिल सकता है। यह पहले की तुलना में कठिन है: गम्यता ग्राफ सामान्यतः अनंत है, और यह निर्धारित करना आसान नहीं है कि कब रुकना सुरक्षित है।

वास्तव में, इस समस्या को एक्सपस्पेस-कठिन दिखाया गया था सालों पहले इसे बिल्कुल भी निर्णायक दिखाया गया था (मेयर, 1981)। इसे कुशलतापूर्वक कैसे किया जाए, इस पर शोध पत्र प्रकाशित होते रहते है। 2018 में, ज़ेरविंस्की एट अल ने निचली सीमा में सुधार किया और दिखाया कि समस्या प्राथमिक नहीं है। 2021 में, जेरोम लेरोक्स द्वारा स्वतंत्र रूप से इस समस्या को गैर-आदिम पुनरावर्ती दिखाया गया था और वोज्शिएक ज़ेरविन्स्की और लुकाज़ ऑरलिकोव्स्की द्वारा दिखाया गया था। इस प्रकार ये परिणाम लंबे समय से चली आ रही जटिलता को बंद कर देते है।

जबकि गम्यता गलत राज्यों को खोजने के लिए एक अच्छा उपकरण प्रतीत होता है, व्यावहारिक समस्याओं के लिए निर्मित ग्राफ में सामान्यतः गणना करने के लिए बहुत अधिक राज्य होते है। इस समस्या को कम करने के लिए, रैखिक लौकिक तर्क का उपयोग सामान्यतः यह सिद्ध करने के लिए विश्लेषणात्मक विधि के संयोजन में किया जाता है कि ऐसी अवस्थाओं तक नहीं पहुँचा जा सकता है। रैखिक लौकिक तर्क अर्ध-निर्णय प्रक्रिया तकनीक का उपयोग यह पता लगाने के लिए करता है कि क्या वास्तव में एक राज्य तक पहुँचा जा सकता है, राज्य तक पहुँचने के लिए आवश्यक शर्तों का एक सेट खोज कर, यह सिद्ध करते हुए कि उन शर्तों को संतुष्ट नहीं किया जा सकता है।

सजीवता

Error creating thumbnail:

एक पेट्री नेट जिसमें संक्रमण होता है $t_{0}$ मर चुका है, जबकि सभी के लिए $j>0,$ $t_{j}$ है $L_{j}$-रहना

पेट्री नेट को जीवंतता की विभिन्न डिग्री के रूप में वर्णित किया जा सकता है $L_{1}-L_{4}$. वह पेट्री नेट $(N,M_{0})$ कहा जाता है $L_{k}$-जीएं और केवल यदि इसके सभी संक्रमण है $L_{k}$-लाइव, जहां एक संक्रमण है

• मृत, यदि यह कभी भी फायर नहीं कर सकता है, अर्थात यह फायरिंग सीक्वेंस में नहीं है $L(N,M_{0})$
• $L_{1}$-लाइव (संभावित रूप से फायर करने योग्य), यदि और केवल यदि यह फायर कर सकता है, अर्थात यह कुछ फायरिंग सीक्वेंस में है $L(N,M_{0})$
• $L_{2}$-Live यदि यह मनमाने ढंग से अधिकांशतः आग लगा सकता है, अर्थात यदि हर सकारात्मक पूर्णांक के लिए k, यह कम से कम होता है k बार कुछ फायरिंग सीक्वेंस में है $L(N,M_{0})$
• $L_{3}$-लाइव यदि यह असीम रूप से अधिकांशतः आग लगा सकता है, अर्थात यदि कुछ निश्चित (आवश्यक अनंत) फायरिंग अनुक्रम है जिसमें प्रत्येक सकारात्मक पूर्णांक के लिए k, संक्रमण $L_{3}$ कम से कम होता है k,
• $L_{4}$-लाइव (लाइव) यदि यह हमेशा आग लगा सकता है, अर्थात यह है $L_{1}$में हर पहुंच योग्य अंकन में रहते है $R(N,M_{0})$

ध्यान दें कि ये तेजी से कठोर आवश्यकताएं है: $L_{j+1}$-जीवंतता का तात्पर्य है $L_{j}$-जीवंतता, के लिए है ${\textstyle \textstyle {j\in {1,2,3}}}$.

ये परिभाषाएँ मुराता के अवलोकन के अनुसार है, जो अतिरिक्त रूप से उपयोग करता है $L_{0}$-मृत के लिए एक शब्द के रूप में जीना होता है।

सीमाबद्धता

Error creating thumbnail:

एन2 का रीचेबिलिटी ग्राफ।

पेट्री नेट में एक जगह को के-बाउंड कहा जाता है यदि इसमें प्रारंभिक अंकन सहित सभी पहुंच योग्य चिह्नों में के टोकन से अधिक नहीं होते है, यदि यह 1-बाध्य है तो इसे सुरक्षित कहा जाता है, यह परिबद्ध है यदि यह कुछ k के लिए k-बाध्य है।

ए (चिन्हित) पेट्री नेट को के-बाउंडेड, सेफ या बाउंडेड कहा जाता है जब इसके सभी स्थान होते है। एक पेट्री नेट (ग्राफ) को (संरचनात्मक रूप से) बाउंडेड कहा जाता है यदि यह हर संभव प्रारंभिक अंकन के लिए बाउंड होता है।

एक पेट्री नेट बंधा हुआ है केवल यदि इसकी गम्यता ग्राफ परिमित होता है।

रिचर्ड कार्प-मिलर ट्री का निर्माण करके, कवरिंग समस्या को देखते हुए बाउंडेडनेस निर्णायक होता है।

किसी दिए गए नेट में स्थानों पर स्पष्ट रूप से बाध्य होना उपयोगी हो सकता है। इसका उपयोग सीमित प्रणाली संसाधनों को मॉडल करने के लिए किया जा सकता है।

पेट्री नेट की कुछ परिभाषाएँ स्पष्ट रूप से इसे एक वाक्यगत विशेषता के रूप में अनुमति देता है। औपचारिक रूप से, स्थान क्षमता वाले पेट्री नेट को टुपल्स के रूप में परिभाषित किया जा सकता है $(S,T,W,C,M_{0})$, कहाँ $(S,T,W,M_{0})$ पेट्री नेट है, $C:P\rightarrow \!\!\!\shortmid \mathbb {N}$ (कुछ या सभी) स्थानों के लिए क्षमताओं का एक असाइनमेंट, और संक्रमण संबंध सामान्य रूप से चिह्नों तक सीमित होता है जिसमें क्षमता वाले प्रत्येक स्थान पर अधिक से अधिक कई टोकन होते है।

File:Two-boundedness-ub.png

एक असीमित पेट्री नेट, एन।

उदाहरण के लिए, यदि नेट N में, दोनों स्थानों को क्षमता 2 निर्दिष्ट की गई है, तो हम स्थान क्षमताओं के साथ पेट्री नेट प्राप्त करते है, N2 कहते है, इसका गम्यता ग्राफ दाईं ओर प्रदर्शित होती है।

File:Two-boundedness-cb.png

काउंटर-प्लेस के साथ एन का विस्तार करके प्राप्त एक दो-बाउंड पेट्री नेट।

वैकल्पिक रूप से, नेट को फैलाकर स्थानों को घेरा जा सकता है। त्रुटिहीन होने के लिए, स्थान के विपरीत प्रवाह के साथ "काउंटर-प्लेस" जोड़कर और दोनों स्थानों में कुल बनाने के लिए टोकन जोड़कर एक जगह को के-बाध्य बनाया जा सकता है।

असतत, निरंतर और संकर पेट्री नेट

साथ ही असतत घटनाओं के लिए, निरंतर और संकर असतत-निरंतर प्रक्रियाओं के लिए पेट्री नेट होता हैजो असतत, सतत और संकर नियंत्रण सिद्धांत में उपयोगी होते है, और असतत, निरंतर और संकर ऑटोमेटा सिद्धांत से संबंधित होते है।

एक्सटेंशन

पेट्री नेट्स के कई विस्तार है। उनमें से कुछ मूल पेट्री नेट के साथ पूरी तरह से पीछे की ओर-संगत (जैसे रंगीन पेट्री नेट) है, कुछ ऐसे गुण जोड़ते है जिन्हें मूल पेट्री नेट औपचारिकता (जैसे समयबद्ध पेट्री नेट) में मॉडल नहीं किया जा सकता है। चूंकि पश्च-संगत मॉडल पेट्री नेट की कम्प्यूटेशनल शक्ति का विस्तार नहीं करते है, उनके पास अधिक संक्षिप्त प्रतिनिधित्व हो सकते है और मॉडलिंग के लिए अधिक सुविधाजनक हो सकते है। एक्सटेंशन जिन्हें पेट्री नेट में परिवर्तित नहीं किया जा सकता है, कभी-कभी बहुत शक्तिशाली होते है, लेकिन सामान्यतः सामान्य पेट्री नेट का विश्लेषण करने के लिए उपलब्ध गणितीय उपकरणों की पूरी श्रृंखला का अभाव होता है।

उच्च स्तरीय पेट्री नेट शब्द का प्रयोग कई पेट्री नेट औपचारिकताओं के लिए किया जाता है जो बुनियादी पी/टी नेट औपचारिकता का विस्तार करते है, इसमें रंगीन पेट्री नेट, पदानुक्रमित पेट्री नेट जैसे नेट के भीतर नेट, और इस खंड में स्केच किए गए अन्य सभी विस्तार सम्मलित होते है। इस शब्द का प्रयोग विशेष रूप से सीपीएन उपकरण द्वारा समर्थित रंगीन नेटों के प्रकार के लिए भी किया जाता है।

संभावित एक्सटेंशन की एक छोटी सूची इस प्रकार है:

• अतिरिक्त प्रकार के चाप, दो सामान्य प्रकार है
  • एक रीसेट चाप फायरिंग पर कोई पूर्व शर्त नहीं लगाता है, और संक्रमण के प्रारंभ होने पर जगह को खाली कर देता है, यह पहुंच योग्यता को अनिर्णीत बनाता है, जबकि कुछ अन्य गुण, जैसे समाप्ति, निर्णायक बने रहते है।
  • एक अवरोधक चाप पूर्व शर्त लगाता है कि स्थान खाली होने पर ही संक्रमण प्रारंभ हो सकता है, यह व्यक्त किए जाने वाले टोकन की संख्या पर मनमाने ढंग से संगणना की अनुमति देता है, जो औपचारिकता ट्यूरिंग पूर्ण पूर्ण बनाता है और एक सार्वभौमिक नेट के अस्तित्व को दर्शाता है।
• एक मानक पेट्री नेट में, टोकन अप्रभेद्य है। रंगीन पेट्री नेट में, प्रत्येक टोकन का मूल्य होता है। सीपीएन उपकरण्स जैसे रंगीन पेट्री नेट के लिए लोकप्रिय उपकरण में, टोकन के मूल्यों को टाइप किया जाता है, और इसका परीक्षण किया जा सकता है (गार्ड एक्सप्रेशंस का उपयोग करके) और एक कार्यात्मक प्रोग्रामिंग भाषा के साथ हेरफेर किया जा सकता है। रंगीन पेट्री नेटों की एक सहायक पेट्री नेट अच्छी तरह से बनाई गई है, जहां नेट का विश्लेषण करना आसान बनाने के लिए चाप और गार्ड अभिव्यक्ति प्रतिबंधित है।
• पेट्री नेट का एक अन्य लोकप्रिय विस्तार पदानुक्रम है, फेहलिंग द्वारा शोधन और अमूर्तता के समर्थन स्तरों के विभिन्न विचारों के रूप में इसका अध्ययन किया गया था। पदानुक्रम का एक अन्य रूप तथाकथित ऑब्जेक्ट पेट्री नेट या ऑब्जेक्ट प्रणाली में पाया जाता है जहां पेट्री नेट में पेट्री नेट हो सकते है क्योंकि इसके टोकन नेस्टेड पेट्री नेट के पदानुक्रम को प्रेरित करते है जो विभिन्न स्तरों पर संक्रमणों के सिंक्रनाइज़ेशन द्वारा संचार करते है।
• राज्यों (वीएएसएस) के साथ एक वेक्टर जोड़ प्रणाली पेट्री नेट के समान औपचारिकता है। चूँकि, इसे सतही तौर पर पेट्री नेट के सामान्यीकरण के रूप में देखा जा सकता है। एक परिमित राज्य ऑटोमेटन पर विचार करें जहां प्रत्येक संक्रमण को पेट्री नेट से संक्रमण द्वारा लेबल किया जाता है। पेट्री नेट को तब परिमित राज्य ऑटोमेटन के साथ सिंक्रनाइज़ किया जाता है, अर्थात, ऑटोमेटन में एक संक्रमण उसी समय लिया जाता है जब पेट्री नेट में संबंधित संक्रमण होता है। पेट्री नेट में संबंधित संक्रमण सक्षम होने पर ही ऑटोमेटन में एक संक्रमण लेना संभव होता है, और पेट्री नेट में एक संक्रमण को आग लगाना केवल तभी संभव है जब इसके द्वारा लेबल किए गए ऑटोमेटन में वर्तमान स्थिति से कोई संक्रमण होता है। (वीएएसएस की परिभाषा सामान्यतः थोड़ी अलग तरीके से तैयार की जाती है।)
• प्राथमिकता वाले पेट्री नेट संक्रमणों में प्राथमिकताएं जोड़ते है, जिससे एक उच्च-प्राथमिकता संक्रमण सक्षम होने पर एक संक्रमण प्रारंभ नहीं हो सकता है (अर्थात आग लगा सकता है)। इस प्रकार, संक्रमण प्राथमिकता समूहों में है, और प्राथमिकता समूह 3 केवल तब सक्रिय हो सकता है जब समूह 1 और 2 में सभी संक्रमण अक्षम होते है। प्राथमिकता समूह के भीतर, फायरिंग अभी भी गैर-निर्धारिती है।
• गैर-नियतात्मक संपत्ति एक बहुत ही मूल्यवान संपत्ति रही है, क्योंकि यह उपयोगकर्ता को बड़ी संख्या में गुणों को सार करने देती है। चूंकि, कुछ स्थितियों में, केवल एक मॉडल की संरचना ही नहीं, जबकि समय को भी मॉडल करने की आवश्यकता होती है। इन स्थितियों के लिए, समयबद्ध पेट्री नेट विकसित हुए है, जहां ऐसे संक्रमण है जो समयबद्ध है, और संभवतः संक्रमण जो समयबद्ध नहीं है (यदि है, तो समयबद्ध संक्रमणों की समयबद्धता की तुलना में उच्च प्राथमिकता है)। समयबद्ध पेट्री नेट की एक सहायक स्टोकेस्टिक पेट्री नेट है जो संक्रमणों की समायोज्य यादृच्छिकता के माध्यम से गैर-नियतात्मक समय जोड़ता है। घातीय यादृच्छिक वितरण का उपयोग सामान्यतः इन नेटों को 'समय' करने के लिए किया जाता है। इस स्थिति में, नेट गम्यता ग्राफ का उपयोग निरंतर समय मार्कोव श्रृंखला (सीटीएमसी) के रूप में किया जा सकता है।
• द्वैतवादी पेट्री नेट (डीपी-नेट) ई. डाविस, एट अल द्वारा विकसित एक पेट्री नेट एक्सटेंशन है। वास्तविक दुनिया की प्रक्रिया का बेहतर प्रतिनिधित्व करने के लिए होती है। डीपी-नेट परिवर्तन/अपरिवर्तन, क्रिया/निष्क्रियता, (परिवर्तन) समय/स्थान आदि के द्वंद्व को संतुलित करते है, परिवर्तन और स्थान के द्विदलीय पेट्री नेट निर्माणों के बीच, जिसके परिणामस्वरूप परिवर्तन अंकन की अनूठी विशेषता होती है, अर्थात, जब परिवर्तन काम कर रहा है यह चिह्नित होता है। यह प्रक्रिया थ्रूपुट के वास्तविक दुनिया के व्यवहार का प्रतिनिधित्व करते हुए कई बार आग (या चिह्नित) के परिवर्तन की अनुमति देता है। परिवर्तन का अंकन मानता है कि परिवर्तन का समय शून्य से अधिक होना चाहिए। कई विशिष्ट पेट्री नेट में उपयोग किया जाने वाला शून्य परिवर्तन समय गणितीय रूप से आकर्षक हो सकता है लेकिन वास्तविक दुनिया की प्रक्रियाओं का प्रतिनिधित्व करने में अव्यावहारिक होता है । डीपी-नेट प्रक्रिया संरचना को चित्रित करने के लिए पेट्री नेट्स के पदानुक्रमित अमूर्तता की शक्ति का भी उपयोग करता है। जटिल प्रक्रिया प्रणालियों को पदानुक्रमित अमूर्तता के विभिन्न स्तरों के माध्यम से परस्पर जुड़े सरल नेटों की एक श्रृंखला के रूप में तैयार किया जाता है। एक पैकेट स्विच के प्रक्रिया वास्तुकला को प्रदर्शित किया जाता है, जहां डिजाइन प्रणाली की संरचना के आसपास विकास आवश्यकताओं का आयोजन किया जाता है।

पेट्री नेट के कई और विस्तार है, चूंकि, यह ध्यान रखना महत्वपूर्ण है कि जैसे-जैसे विस्तारित गुणों के संदर्भ में नेट की जटिलता बढ़ती है, नेट के कुछ गुणों का मूल्यांकन करने के लिए मानक उपकरणों का उपयोग करना उतना ही कठिन होता है। इस कारण से, किसी दिए गए मॉडलिंग कार्य के लिए सबसे सरल नेट प्रकार का उपयोग करना एक अच्छा विचार होता है।

प्रतिबंध

पेट्री नेट प्रकार रेखांकन

पेट्री नेट औपचारिकता को विस्तारित करने के अतिरिक्त, हम इसे प्रतिबंधित करने पर भी देख सकते है, और विशेष प्रकार के पेट्री नेट को देख सकते है, जो एक विशेष तरीके से सिंटैक्स को प्रतिबंधित करके प्राप्त किया जाता है। साधारण पेट्री नेट वे नेट होते है जहां सभी चाप भार 1 होते है। आगे प्रतिबंधित करते हुए, निम्नलिखित प्रकार के साधारण पेट्री नेटों का सामान्यतः उपयोग और अध्ययन किया जाता है:

1. एक राज्य मशीन (एसएम) में, प्रत्येक संक्रमण में एक आने वाली चाप और एक बाहर जाने वाली चाप होती है, और सभी चिह्नों में बिल्कुल एक टोकन होता है। परिणाम स्वरुप, समवर्ती नहीं हो सकता है, लेकिन संघर्ष हो सकता है (अर्थात समवर्ती गणना में अनिश्चितता): गणितीय रूप से, $\forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1$
2. एक चिह्नित ग्राफ (एमजी) में, प्रत्येक स्थान में एक आने वाली चाप और एक बाहर जाने वाली चाप होती है। इसका अर्थ यह है कि विरोध नहीं हो सकता, लेकिन समवर्ती हो सकता है: गणितीय रूप से, $\forall s\in S:|s^{\bullet }|=|{}^{\bullet }s|=1$
3. फ्री चॉइस नेट (एफसी) में, एक स्थान से एक संक्रमण के लिए प्रत्येक चाप या तो उस स्थान से एकमात्र चाप है या उस संक्रमण के लिए एकमात्र चाप होती है, अर्थात संगामिति और संघर्ष दोनों हो सकते है, लेकिन एक ही समय में नहीं हो सकते है: गणितीय रूप से, $\forall s\in S:(|s^{\bullet }|\leq 1)\vee ({}^{\bullet }(s^{\bullet })=\{s\})$
4. एक्सटेंडेड फ्री चॉइस (ईएफसी) - एक पेट्री नेट जिसे एफसी में बदला जा सकता है।
5. एक असममित विकल्प नेट (एसी) में, संगामिति और संघर्ष हो सकता है, लेकिन सममित रूप से नहीं हो सकता है: गणितीय रूप से, $\forall s_{1},s_{2}\in S:(s_{1}{}^{\bullet }\cap s_{2}{}^{\bullet }\neq \emptyset )\to [(s_{1}{}^{\bullet }\subseteq s_{2}{}^{\bullet })\vee (s_{2}{}^{\bullet }\subseteq s_{1}{}^{\bullet })]$

कार्यप्रवाह नेट

वर्कफ़्लो नेट (डब्ल्यूएफ-नेट) पेट्री नेट का एक उपवर्ग है जो प्रक्रिया गतिविधियों के वर्कफ़्लो को मॉडल करने का इरादा रखता है। डब्ल्यूएफ-नेट संक्रमण कार्यों या गतिविधियों को सौंपा गया है, और स्थान पूर्व/पोस्ट स्थितियों को असाइन किए गए है। डब्ल्यूएफ-नेट की अतिरिक्त संरचनात्मक और परिचालन आवश्यकताएं होती है, मुख्य रूप से एक एकल इनपुट (स्रोत) स्थान के अतिरिक्त कोई पिछला संक्रमण नहीं है, और आउटपुट स्थान (सिंक) बिना किसी संक्रमण के होता है। तदनुसार, प्रारंभ और समाप्ति चिह्नों को परिभाषित किया जा सकता है जो प्रक्रिया की स्थिति का प्रतिनिधित्व करते है।

डब्ल्यूएफ-नेट में ध्वनि प्रॉपर्टी है, यह दर्शाता है कि अपने स्रोत स्थान पर k टोकन के स्टार्ट मार्किंग के साथ एक प्रक्रिया, अपने सिंक स्थान में k टोकन के साथ समापन स्टेट मार्किंग तक पहुँच सकती है (k- ध्वनि डब्ल्यूएफ-नेट के रूप में परिभाषित) इसके अतिरिक्त, प्रक्रिया में सभी संक्रमण लग सकते है (अर्थात, प्रत्येक संक्रमण के लिए एक पहुंच योग्य स्थिति होती है जिसमें संक्रमण सक्षम होता है)। एक सामान्य ध्वनि (जी-ध्वनि) डब्ल्यूएफ-नेट को प्रत्येक के> 0 के लिए के-ध्वनि के रूप में परिभाषित किया गया है।

पेट्री नेट में एक निर्देशित पथ (ग्राफ सिद्धांत) को निर्देशित चापों से जुड़े नोड्स (स्थानों और संक्रमण) के अनुक्रम के रूप में परिभाषित किया गया है। प्राथमिक पथ में अनुक्रम में प्रत्येक नोड केवल एक बार सम्मलित होता है।

एक अच्छी तरह से नियंत्रित पेट्री नेट एक ऐसा नेट है जिसमें एक स्थान और एक संक्रमण (या संक्रमण और एक स्थान) के बीच पूरी तरह से अलग प्राथमिक पथ नहीं होते है, अर्थात, यदि नोड्स की जोड़ी के बीच दो पथ है तो ये पथ एक नोड साझा करते है। एक विश्वकोश अच्छी तरह से नियंत्रित डब्ल्यूएफ-नेट ध्वनि (जी-ध्वनि) होती है।

विस्तारित डब्ल्यूएफ-नेट एक पेट्री नेट है जो अतिरिक्त संक्रमण टी (फीडबैक संक्रमण) के साथ डब्ल्यूएफ-नेट से बना होता है। सिंक स्थान संक्रमण टी के इनपुट स्थान और स्रोत स्थान के रूप में इसके आउटपुट स्थान के रूप में जुड़ा हुआ होता है। संक्रमण की फायरिंग प्रक्रिया की पुनरावृत्ति का कारण बनती है।

डब्ल्यूआरआई डब्ल्यूएफ-नेट, एक विस्तारित एसाइक्लिक अच्छी तरह से हैंडल किया जाने वाला डब्ल्यूएफ-नेट है। डब्ल्यूआरआई-डब्ल्यूएफ-नेट को नेट की संरचना के रूप में बनाया जा सकता है, अर्थात, डब्ल्यूआरआई-डब्ल्यूएफ-नेट के भीतर एक सबनेट के साथ एक संक्रमण को बदलना होता है जो डब्ल्यूआरआई-डब्ल्यूएफ-नेट होता है। नतीजा डब्ल्यूआरआई-डब्ल्यूएफ-net भी होता है। डब्ल्यूआरआई-डब्ल्यूएफ-नेट जी-ध्वनि होती है, इसलिए केवल डब्ल्यूआरआई-डब्ल्यूएफ-नेट बिल्डिंग ब्लॉक्स का उपयोग करके, डब्ल्यूएफ-नेट प्राप्त कर सकते है जो निर्माण द्वारा जी-ध्वनि होती है।

डिजाइन संरचना मैट्रिक्स (डीएसएम) प्रक्रिया संबंधों को मॉडल कर सकता है, और प्रक्रिया नियोजन के लिए उपयोग किया जा सकता है। डीएसएम-नेट, पेट्री नेट द्वारा कार्यप्रवाह प्रक्रियाओं में डीएसएम-आधारित योजनाओं की प्राप्ति करता है, और डब्ल्यूआरआई-डब्ल्यूएफ-नेट के समकक्ष होता है। डीएसएम-नेट निर्माण प्रक्रिया परिणामी नेट की सुदृढ़ता संपत्ति सुनिश्चित करता है।

समवर्ती के अन्य मॉडल

मॉडलिंग समवर्ती संगणना के अन्य विधियों का प्रस्ताव किया गया है, जिसमें वेक्टर जोड़ प्रणाली, परिमित-राज्य मशीनों का संचार, क्हान प्रक्रिया नेटवर्क, प्रक्रिया बीजगणित, अभिनेता मॉडल और ट्रेस सिद्धांत सम्मलित है। विभिन्न मॉडल संरचना, प्रतिरूपकता (प्रोग्रामिंग) और स्थानीयता जैसी अवधारणाओं का व्यापार प्रदान करते है।

विन्सेल और नीलसन द्वारा अध्याय में समवर्ती के इन मॉडलों में से कुछ को संबंधित करने का एक दृष्टिकोण प्रस्तावित है।

उपयेाग क्षेत्र

• बूलियन डिफरेंशियल कैलकुलस
• बिजनेस प्रोसेस मॉडलिंग

• कम्प्यूटेशनल बायोलॉजी
• समवर्ती प्रोग्रामिंग
• नियंत्रण इंजीनियरिंग
• डेटा विश्लेषण
• निदान (कृत्रिम बुद्धि)
• डायग्नोसिस (आर्टिफिशियल इंटेलिजेंस)
• अनुक्रमिक फ़ंक्शन चार्ट
• खेल सिद्धांत
• सिग्नल संक्रमण रेखांकन
• क्हान प्रक्रिया नेटवर्क
• प्रक्रिया मॉडलिंग
• स्थिरता अभियांत्रिकी
• सिमुलेशन* सॉफ्टवेर डिज़ाइन
• वर्कफ़्लो प्रबंधन प्रणाली

यह भी देखें

• परिमित अवस्था मशीन
• पेट्री नेट मार्कअप लैंग्वेज
• पेट्रीस्क्रिप्ट
• प्रक्रिया संरचना
• वेक्टर जोड़ प्रणाली
• यंत्र अधिगम

अग्रिम पठन

• Cardoso, Janette; Camargo, Heloisa (1999). Fuzziness in Petri Nets. Physica-Verlag. ISBN 978-3-7908-1158-2.
• Chiachio, Manuel; Chiachio, Juan; Presscott, Darren; Andrews, John (2018). "A new paradigm for uncertain knowledge representation by 'Plausible Petri nets'". Information Sciences. 453 (July 2018): 323–345. doi:10.1016/j.ins.2018.04.029.
• Grobelna, Iwona (2011). "Formal verification of embedded logic controller specification with computer deduction in temporal logic". Przegląd Elektrotechniczny. 87 (12a): 47–50.
• Jensen, Kurt (1997). Coloured Petri Nets. Springer Verlag. ISBN 978-3-540-62867-5.
• Pataricza, András (2004). Formális módszerek az informatikában (Formal methods in informatics). TYPOTEX Kiadó. ISBN 978-963-9548-08-4.
• Peterson, James Lyle (1977). "Petri Nets". ACM Computing Surveys. 9 (3): 223–252. doi:10.1145/356698.356702. hdl:10338.dmlcz/135597. S2CID 3605804.
• Peterson, James Lyle (1981). Petri Net Theory and the Modeling of Systems. Prentice Hall. ISBN 978-0-13-661983-3.
• Petri, Carl Adam (1962). Kommunikation mit Automaten (Ph. D. thesis). University of Bonn.
• Petri, Carl Adam; Reisig, Wolfgang (2008). "Petri net". Scholarpedia. 3 (4): 6477. Bibcode:2008SchpJ...3.6477P. doi:10.4249/scholarpedia.6477.
• Reisig, Wolfgang (1992). A Primer in Petri Net Design. Springer-Verlag. ISBN 978-3-540-52044-3.
• Riemann, Robert-Christoph (1999). Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus. Herbert Utz Verlag. ISBN 978-3-89675-629-9.
• Störrle, Harald (2000). Models of Software Architecture – Design and Analysis with UML and Petri-Nets. Books on Demand. ISBN 978-3-8311-1330-9.
• Zaitsev, Dmitry (2013). Clans of Petri Nets: Verification of protocols and performance evaluation of networks. LAP LAMBERT Academic Publishing. ISBN 978-3-659-42228-7.
• Zhou, Mengchu; Dicesare, Frank (1993). Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. Kluwer Academic Publishers. ISBN 978-0-7923-9289-7.
• Zhou, Mengchu; Venkatesh, Kurapati (1998). Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach. World Scientific Publishing. ISBN 978-981-02-3029-6.