प्रक्रिया गणना

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

आवश्यक विशेषताएं

जबकि मौजूदा प्रक्रिया कैलकुली की विविधता बहुत बड़ी है (वैरिएंट सहित जो स्टोकेस्टिक व्यवहार, समय की जानकारी और आणविक इंटरैक्शन का अध्ययन करने के लिए विशेषज्ञता शामिल है), ऐसी कई विशेषताएं हैं जो सभी प्रक्रिया कैलकुली में समान हैं:

• साझा चर के संशोधन के बजाय संचार (संदेश-पास) के रूप में स्वतंत्र प्रक्रियाओं के बीच बातचीत का प्रतिनिधित्व करना।
• प्रिमिटिव के एक छोटे संग्रह का उपयोग करके प्रक्रियाओं और सिस्टम का वर्णन करना, और उन प्रिमिटिव के संयोजन के लिए ऑपरेटर्स।
• प्रक्रिया संचालकों के लिए बीजगणितीय कानूनों को परिभाषित करना, जो समीकरण तर्क का उपयोग करके प्रक्रिया अभिव्यक्तियों को हेरफेर करने की अनुमति देता है।

प्रक्रियाओं का गणित

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

• प्रक्रियाओं की समानांतर रचना
• डेटा भेजने और प्राप्त करने के लिए किन चैनलों का उपयोग करना है, इसकी विशिष्टता
• बातचीत का अनुक्रमिकरण
• इंटरेक्शन पॉइंट्स को छिपाना
• पुनरावर्तन या प्रक्रिया प्रतिकृति

समानांतर रचना

दो प्रक्रियाओं की समानांतर रचना ${\mathit {P}}$ और ${\mathit {Q}}$, आमतौर पर लिखा जाता है $P\vert Q$, गणना के अनुक्रमिक मॉडल से प्रक्रिया गणना को अलग करने वाला प्रमुख आदिम है। समानांतर संरचना गणना की अनुमति देती है ${\mathit {P}}$ और ${\mathit {Q}}$ एक साथ और स्वतंत्र रूप से आगे बढ़ने के लिए। लेकिन यह इंटरेक्शन की भी अनुमति देता है, जो कि सिंक्रोनाइज़ेशन और सूचनाओं का प्रवाह है ${\mathit {P}}$ को ${\mathit {Q}}$ (या इसके विपरीत) दोनों द्वारा साझा किए गए चैनल पर। महत्वपूर्ण रूप से, एक एजेंट या प्रक्रिया को एक समय में एक से अधिक चैनल से जोड़ा जा सकता है।

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

संचार

सहभागिता सूचना का एक निर्देशित प्रवाह हो सकता है (लेकिन हमेशा नहीं होता है)। अर्थात्, इनपुट और आउटपुट को दोहरी अंतःक्रियात्मक आदिम के रूप में प्रतिष्ठित किया जा सकता है। प्रक्रिया गणना जो इस तरह के भेद करती है, आमतौर पर एक इनपुट ऑपरेटर को परिभाषित करती है (उदा। $x(v)$) और एक आउटपुट ऑपरेटर (उदा. $x\langle y\rangle$), दोनों एक इंटरेक्शन पॉइंट का नाम देते हैं (यहाँ ${\mathit {x}}$) जिसका उपयोग दोहरी अंतःक्रिया आदिम के साथ सिंक्रनाइज़ करने के लिए किया जाता है।

यदि सूचनाओं का आदान-प्रदान किया जाना चाहिए, तो यह आउटपुटिंग से इनपुटिंग प्रक्रिया तक प्रवाहित होगी। आउटपुट प्रिमिटिव भेजे जाने वाले डेटा को निर्दिष्ट करेगा। में $x\langle y\rangle$, यह डेटा है $y$. इसी तरह, यदि कोई इनपुट डेटा प्राप्त करने की अपेक्षा करता है, तो एक या एक से अधिक बाध्य चर डेटा के आने पर प्लेस-होल्डर्स के रूप में कार्य करेंगे। में $x(v)$, $v$ उस भूमिका को निभाता है। एक बातचीत में जिस तरह के डेटा का आदान-प्रदान किया जा सकता है, उसका चुनाव उन प्रमुख विशेषताओं में से एक है जो विभिन्न प्रक्रिया गणनाओं को अलग करता है।

अनुक्रमिक रचना

कभी-कभी बातचीत अस्थायी रूप से आदेशित होनी चाहिए। उदाहरण के लिए, एल्गोरिदम निर्दिष्ट करना वांछनीय हो सकता है जैसे: पहले कुछ डेटा प्राप्त करें ${\mathit {x}}$ और उसके बाद उस डेटा को भेजें ${\mathit {y}}$. ऐसे उद्देश्यों के लिए अनुक्रमिक संरचना का उपयोग किया जा सकता है। यह गणना के अन्य मॉडलों से अच्छी तरह से जाना जाता है। प्रक्रिया गणना में, क्रमिककरण ऑपरेटर आमतौर पर इनपुट या आउटपुट, या दोनों के साथ एकीकृत होता है। उदाहरण के लिए, प्रक्रिया $x(v)\cdot P$ एक इनपुट के लिए प्रतीक्षा करेंगे ${\mathit {x}}$. यह इनपुट होने पर ही प्रक्रिया होगी ${\mathit {P}}$ के माध्यम से प्राप्त डेटा के साथ सक्रिय हो ${\mathit {x}}$ पहचानकर्ता के लिए प्रतिस्थापित ${\mathit {v}}$.

कमी शब्दार्थ

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

$x\langle y\rangle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]$

इस कमी नियम की व्याख्या है:

1. प्रक्रिया $x\langle y\rangle \cdot P$ एक संदेश भेजता है, यहाँ ${\mathit {y}}$, चैनल के साथ ${\mathit {x}}$. दो तरह से, प्रक्रिया $x(v)\cdot Q$ चैनल पर वह संदेश प्राप्त करता है ${\mathit {x}}$.
2. संदेश भेजे जाने के बाद, $x\langle y\rangle \cdot P$ प्रक्रिया बन जाती है ${\mathit {P}}$, जबकि $x(v)\cdot Q$ प्रक्रिया बन जाती है $Q[^{y}\!/\!_{v}]$, जो है ${\mathit {Q}}$ स्थान धारक के साथ ${\mathit {v}}$ द्वारा प्रतिस्थापित ${\mathit {y}}$, पर डेटा प्राप्त हुआ ${\mathit {x}}$.

प्रक्रियाओं का वर्ग जो ${\mathit {P}}$ सीमा से अधिक की अनुमति है क्योंकि आउटपुट ऑपरेशन की निरंतरता कैलकुलस के गुणों को काफी हद तक प्रभावित करती है।

छिपाना

प्रक्रियाएं उन कनेक्शनों की संख्या को सीमित नहीं करती हैं जो किसी दिए गए अंतःक्रियात्मक बिंदु पर किए जा सकते हैं। लेकिन इंटरेक्शन पॉइंट हस्तक्षेप (यानी इंटरैक्शन) की अनुमति देते हैं। के लिए कॉम्पैक्ट, न्यूनतम और रचनात्मक प्रणालियों का संश्लेषण, हस्तक्षेप को प्रतिबंधित करने की क्षमता महत्वपूर्ण है। छिपाने के संचालन से रचना करते समय बातचीत बिंदुओं के बीच बने कनेक्शनों को नियंत्रित करने की अनुमति मिलती है समानांतर में एजेंट। छिपाने को विभिन्न तरीकों से निरूपित किया जा सकता है। उदाहरण के लिए, π-कैलकुलस में एक नाम को छुपाना ${\mathit {x}}$ में ${\mathit {P}}$ के रूप में व्यक्त किया जा सकता है $(\nu \;x)P$, जबकि संचार अनुक्रमिक प्रक्रियाओं में इसे इस रूप में लिखा जा सकता है $P\setminus \{x\}$.

पुनरावर्तन और प्रतिकृति

अब तक प्रस्तुत किए गए ऑपरेशन केवल परिमित अंतःक्रिया का वर्णन करते हैं और परिणामस्वरूप पूर्ण संगणनीयता के लिए अपर्याप्त हैं, जिसमें गैर-समाप्ति व्यवहार शामिल है। पुनरावर्तन और प्रतिकृति (कंप्यूटिंग) ऐसे ऑपरेशन हैं जो अनंत व्यवहार के परिमित विवरण की अनुमति देते हैं। प्रत्यावर्तन अनुक्रमिक दुनिया से अच्छी तरह से जाना जाता है। प्रतिकृति $!P$ की एक अनगिनत अनंत संख्या की समानांतर रचना को संक्षिप्त करने के रूप में समझा जा सकता है ${\mathit {P}}$ प्रक्रियाएं:

$!P=P\mid !P$

अशक्त प्रक्रिया

प्रक्रिया गणना में आम तौर पर एक अशक्त प्रक्रिया भी शामिल होती है (जिसे विभिन्न रूप में दर्शाया जाता है ${\mathit {nil}}$, $0$, ${\mathit {STOP}}$, $\delta$, या कोई अन्य उपयुक्त प्रतीक) जिसमें कोई अंतःक्रिया बिंदु नहीं है। यह पूरी तरह से निष्क्रिय है और इसका एकमात्र उद्देश्य आगमनात्मक एंकर के रूप में कार्य करना है जिसके शीर्ष पर और अधिक रोचक प्रक्रियाएं उत्पन्न की जा सकती हैं।

असतत और सतत प्रक्रिया बीजगणित

प्रक्रिया बीजगणित का अध्ययन असतत समय और निरंतर समय # असतत समय और असतत समय और निरंतर समय # सतत समय (वास्तविक समय या सघन समय) के लिए किया गया है।

इतिहास

20वीं शताब्दी के पूर्वार्द्ध में, Μ-रिकर्सिव फ़ंक्शन|μ-रिकर्सिव फ़ंक्शंस, ट्यूरिंग मशीन और लैम्ब्डा कैलकुलस संभवतः आज सबसे प्रसिद्ध उदाहरण हैं, एक संगणनीय फ़ंक्शन की अनौपचारिक अवधारणा को पकड़ने के लिए विभिन्न औपचारिकताओं का प्रस्ताव किया गया था। आश्चर्यजनक तथ्य यह है कि वे अनिवार्य रूप से समतुल्य हैं, इस अर्थ में कि वे सभी एक-दूसरे में एन्कोड करने योग्य हैं, चर्च-ट्यूरिंग थीसिस का समर्थन करते हैं। एक और साझा सुविधा पर शायद ही कभी टिप्पणी की जाती है: वे सभी अनुक्रमिक संगणना के मॉडल के रूप में सबसे आसानी से समझी जाती हैं। कंप्यूटर विज्ञान के बाद के समेकन के लिए संगणना की धारणा के अधिक सूक्ष्म सूत्रीकरण की आवश्यकता थी, विशेष रूप से संगामिति और संचार के स्पष्ट प्रतिनिधित्व में। 1962 में प्रोसेस कैलकुली, पेट्री नेट्स और 1973 में अभिनेता मॉडल जैसे संगामिति के मॉडल पूछताछ की इस पंक्ति से उभरे।

1973 से 1980 की अवधि के दौरान संचार प्रणालियों की गणना (CCS) पर रॉबिन मिलनर के मौलिक कार्य के साथ प्रोसेस कैलकुली पर शोध शुरू हुआ। C.A.R. होरे की संचार अनुक्रमिक प्रक्रियाएं (सीएसपी) पहली बार 1978 में सामने आईं, और बाद में 1980 के दशक की शुरुआत में इसे एक पूर्ण विकसित प्रक्रिया कलन के रूप में विकसित किया गया। विकसित होते ही सीसीएस और सीएसपी के बीच विचारों का बहुत अधिक क्रॉस-फर्टिलाइजेशन हो गया। 1982 में Jan Bergstra और Jan Willem Klop ने संचार प्रक्रियाओं (ACP) के बीजगणित के रूप में जाने जाने वाले काम पर काम करना शुरू किया, और अपने काम का वर्णन करने के लिए प्रक्रिया बीजगणित की शुरुआत की।सीसीएस, सीएसपी, और एसीपी प्रक्रिया गणना परिवार की तीन प्रमुख शाखाओं का गठन करते हैं: अन्य प्रक्रिया गणनाओं में से अधिकांश इन तीन गणनाओं में से किसी एक में अपनी जड़ों का पता लगा सकते हैं।

वर्तमान शोध

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

• कम्प्यूटेशनल घटना के बेहतर मॉडलिंग के लिए नई प्रक्रिया कैलकुली का विकास करना।
• किसी दिए गए प्रोसेस कैलकुस के अच्छे व्यवहार वाले उप-कैलकुली ढूँढना। यह मूल्यवान है क्योंकि (1) अधिकांश गणना इस अर्थ में काफी जंगली हैं कि वे सामान्य हैं और मनमानी प्रक्रियाओं के बारे में बहुत कुछ नहीं कहा जा सकता है; और (2) कम्प्यूटेशनल अनुप्रयोग शायद ही कभी पूरे कैलकुलस को समाप्त करते हैं। बल्कि वे केवल उन प्रक्रियाओं का उपयोग करते हैं जो बहुत सीमित रूप में होती हैं। प्रक्रियाओं के आकार को सीमित करना ज्यादातर प्रकार प्रणाली के माध्यम से अध्ययन किया जाता है।
• प्रक्रियाओं के लिए तर्क जो होरे तर्क के विचारों का पालन करते हुए प्रक्रियाओं के (अनिवार्य रूप से) मनमाने गुणों के बारे में तर्क करने की अनुमति देते हैं।
• व्यवहार सिद्धांत: दो प्रक्रियाओं के समान होने का क्या अर्थ है? हम कैसे तय कर सकते हैं कि दो प्रक्रियाएं अलग हैं या नहीं? क्या हम प्रक्रियाओं के समतुल्य वर्गों के प्रतिनिधि ढूंढ सकते हैं? आम तौर पर, प्रक्रियाओं को समान माना जाता है यदि कोई संदर्भ नहीं है, यानी समानांतर में चल रही अन्य प्रक्रियाएं, अंतर का पता लगा सकती हैं। दुर्भाग्य से, इस अंतर्ज्ञान को सटीक बनाना सूक्ष्म है और अधिकतर समानता के अनावश्यक लक्षणों को जन्म देता है (जो कि ज्यादातर मामलों में भी अनिर्णीत होना चाहिए, हॉल्टिंग समस्या के परिणामस्वरूप)। बिसिमुलेशन एक तकनीकी उपकरण है जो प्रक्रिया समकक्षों के बारे में तर्क करने में मदद करता है।
• पथरी की अभिव्यक्ति। प्रोग्रामिंग अनुभव से पता चलता है कि कुछ भाषाओं में कुछ समस्याओं को हल करना दूसरों की तुलना में आसान होता है। यह घटना चर्च-ट्यूरिंग थीसिस द्वारा वहन की तुलना में कैलकुली मॉडलिंग संगणना की अभिव्यंजना के अधिक सटीक लक्षण वर्णन की मांग करती है। ऐसा करने का एक तरीका यह है कि दो औपचारिकताओं के बीच एन्कोडिंग पर विचार किया जाए और देखें कि कौन से गुण एन्कोडिंग संभावित रूप से संरक्षित कर सकते हैं। जितने अधिक गुणों को संरक्षित किया जा सकता है, एन्कोडिंग का लक्ष्य उतना ही अधिक अभिव्यंजक कहा जाता है। प्रक्रिया गणना के लिए, मनाए गए परिणाम यह हैं कि सिंक्रोनस π-कैलकुलस अपने एसिंक्रोनस वेरिएंट की तुलना में अधिक अभिव्यंजक है, उच्च-क्रम π-कैलकुलस के समान अभिव्यंजक शक्ति है, लेकिन परिवेश कलन से कम है।
• मॉडल जैविक प्रणालियों (स्टोचैस्टिक π-कैलकुलस, बायोएम्बिएंट्स, बीटा बाइंडर्स, बायोपीईपीए, ब्रैन कैलकुलस) को मॉडल करने के लिए प्रोसेस कैलकुलस का उपयोग करना। कुछ लोगों का मानना ​​है कि प्रक्रिया-सैद्धांतिक उपकरणों द्वारा प्रदान की जाने वाली संरचना जीवविज्ञानियों को अपने ज्ञान को अधिक औपचारिक रूप से व्यवस्थित करने में मदद कर सकती है।

सॉफ्टवेयर कार्यान्वयन

प्रक्रिया बीजगणित के पीछे के विचारों ने कई उपकरणों को जन्म दिया है जिनमें शामिल हैं:

• सीएडीपी
• समवर्ती कार्यक्षेत्र
• mCRL2 टूलसेट

संगामिति के अन्य मॉडलों से संबंध

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

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

यह भी देखें

• अनुक्रमिक प्रक्रियाओं का संचार करना
• ProVerif
• स्टोकेस्टिक जांच
• तामारिन प्रोवर
• लौकिक प्रक्रिया भाषा
• π-पथरी

अग्रिम पठन

• Matthew Hennessy: Algebraic Theory of Processes, The MIT Press, ISBN 0-262-08171-7.
• C. A. R. Hoare: Communicating Sequential Processes, Prentice Hall, ISBN 0-13-153289-8.
  • This book has been updated by Jim Davies at the Oxford University Computing Laboratory and the new edition is available for download as a PDF file at the Using CSP website.
• Robin Milner: A Calculus of Communicating Systems, Springer Verlag, ISBN 0-387-10235-3.
• Robin Milner: Communicating and Mobile Systems: the Pi-Calculus, Springer Verlag, ISBN 0-521-65869-1.
• Valk, Rüdiger; Moldt, Daniel; Köhler-Bußmeier, Michael, eds. (2011). "Chapter 5: Prozessalgebra - Parallele und kommunizierende Prozesse" (PDF). Formale Grundlagen der Informatik II: Modellierung und Analyse von Informatiksystemen. FGI2. Archived (PDF) from the original on 2019-07-09. Retrieved 2019-07-13. {{cite book}}: |work= ignored (help)