द्विअनुकरण

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

सहज रूप से दो प्रणालियाँ समान होती हैं यदि वे, यह मानते हुए कि हम उन्हें कुछ नियमों के अनुसार गेम खेलते हुए देखते हैं, एक-दूसरे की चाल से मेल खाते हैं। इस अर्थ में, पर्यवेक्षक द्वारा प्रत्येक प्रणाली को दूसरे से अलग नहीं किया जा सकता है।

औपचारिक परिभाषा

एक राज्य संक्रमण प्रणाली को देखते हुए ($S$, $\Lambda$, →), कहाँ $S$ राज्यों का एक समूह है, $\Lambda$ लेबलों का एक सेट है और → लेबल किए गए ट्रांज़िशन का एक सेट है (यानी, का एक सबसेट) $S\times \Lambda \times S$), द्विसिमुलेशन एक द्विआधारी संबंध है $R\subseteq S\times S$, ऐसे कि दोनों $R$ और इसका विपरीत संबंध $R^{T}$ अनुकरण पूर्वआदेश हैं। इससे यह पता चलता है कि द्विसिमुलेशन का सममित समापन एक द्विसिमुलेशन है, और प्रत्येक सममित सिमुलेशन एक द्विसिमुलेशन है। इस प्रकार कुछ लेखक द्विसिमुलेशन को सममित अनुकरण के रूप में परिभाषित करते हैं। समान रूप से, $R$ राज्यों की प्रत्येक जोड़ी के लिए यदि और केवल यदि एक द्विसिमुलेशन है $(p,q)$ में $R$ और सभी लेबल α में $\Lambda$:

• अगर $p\mathrel {\overset {\alpha }{\rightarrow }} p'$, फिर वहाँ है $q\mathrel {\overset {\alpha }{\rightarrow }} q'$ ऐसा है कि $(p',q')\in R$;
• अगर $q\mathrel {\overset {\alpha }{\rightarrow }} q'$, फिर वहाँ है $p\mathrel {\overset {\alpha }{\rightarrow }} p'$ ऐसा है कि $(p',q')\in R$.

दो राज्य दिए गए $p$ और $q$ में $S$, $p$ के समान है $q$, लिखा हुआ $p\,\sim \,q$, यदि और केवल यदि कोई द्विसिमुलेशन है $R$ ऐसा है कि $(p,q)\in R$. इसका मतलब है कि द्विसमानता संबंध $\,\sim \,$ सभी द्विअनुकरणों का मिलन है: $(p,q)\in \,\sim \,$ बिल्कुल कब $(p,q)\in R$ कुछ द्विसिमुलेशन के लिए $R$.

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

वैकल्पिक परिभाषाएँ

संबंधपरक परिभाषा

बिसिमुलेशन को संबंधों की संरचना के संदर्भ में निम्नानुसार परिभाषित किया जा सकता है।

एक राज्य संक्रमण प्रणाली दी गई $(S,\Lambda ,\rightarrow )$, एक द्विसिमुलेशन संबंध (गणित) एक द्विआधारी संबंध है $R$ ऊपर $S$ (अर्थात।, $R$ ⊆ $S$ × $S$) ऐसा है कि $\forall \alpha \in \Lambda$

$$R\ ;\ {\overset {\alpha }{\rightarrow }}\quad {\subseteq }\quad {\overset {\alpha }{\rightarrow }}\ ;\ R$$

और

$$R^{-1}\ ;\ {\overset {\alpha }{\rightarrow }}\quad {\subseteq }\quad {\overset {\alpha }{\rightarrow }}\ ;\ R^{-1}$$

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

फिक्सप्वाइंट परिभाषा

बिसिमिलरिटी को आदेश सिद्धांत | ऑर्डर-सैद्धांतिक फैशन में भी परिभाषित किया जा सकता है, नास्टर-टार्स्की प्रमेय के संदर्भ में, अधिक सटीक रूप से नीचे परिभाषित एक निश्चित फ़ंक्शन के सबसे बड़े निश्चित बिंदु के रूप में।

एक राज्य संक्रमण प्रणाली को देखते हुए ($S$, Λ, →), परिभाषित करें $F:{\mathcal {P}}(S\times S)\to {\mathcal {P}}(S\times S)$ बाइनरी संबंधों से एक फ़ंक्शन बनना $S$ द्विआधारी संबंधों को खत्म करने के लिए $S$, निम्नलिखित नुसार:

होने देना $R$ कोई भी द्विआधारी संबंध खत्म हो $S$. $F(R)$ सभी जोड़ियों के समुच्चय के रूप में परिभाषित किया गया है $(p,q)$ में $S$ × $S$ ऐसा है कि:

$$\forall \alpha \in \Lambda .\,\forall p'\in S.\,p{\overset {\alpha }{\rightarrow }}p'\,\Rightarrow \,\exists q'\in S.\,q{\overset {\alpha }{\rightarrow }}q'\,{\textrm {and}}\,(p',q')\in R$$

और

$$\forall \alpha \in \Lambda .\,\forall q'\in S.\,q{\overset {\alpha }{\rightarrow }}q'\,\Rightarrow \,\exists p'\in S.\,p{\overset {\alpha }{\rightarrow }}p'\,{\textrm {and}}\,(p',q')\in R$$

तब द्विसमानता को सबसे बड़े निश्चित बिंदु के रूप में परिभाषित किया जाता है $F$.

एहरनफ्यूच्ट-फ्रैसे गेम परिभाषा

बिसिम्यूलेशन को दो खिलाड़ियों के बीच खेल के संदर्भ में भी सोचा जा सकता है: हमलावर और रक्षक।

हमलावर पहले जाता है और कोई भी वैध संक्रमण चुन सकता है, $\alpha$, से $(p,q)$. वह है,

$$(p,q){\overset {\alpha }{\rightarrow }}(p',q)$$

या

$$(p,q){\overset {\alpha }{\rightarrow }}(p,q')$$

फिर डिफेंडर को उस परिवर्तन से मेल खाने का प्रयास करना चाहिए, $\alpha$ दोनों से $(p',q)$ या $(p,q')$ हमलावर की चाल पर निर्भर करता है. यानी, उन्हें एक खोजना होगा $\alpha$ ऐसा है कि:

$$(p',q){\overset {\alpha }{\rightarrow }}(p',q')$$

या

$$(p,q'){\overset {\alpha }{\rightarrow }}(p',q')$$

हमलावर और बचावकर्ता तब तक बारी-बारी से मोड़ लेते रहते हैं:

• रक्षक हमलावर की चाल से मेल खाने के लिए कोई वैध बदलाव ढूंढने में असमर्थ है। इस स्थिति में हमलावर जीत जाता है.
• गेम राज्यों तक पहुंचता है $(p,q)$ वे दोनों 'मृत' हैं (अर्थात, किसी भी राज्य से कोई परिवर्तन नहीं हुआ है) इस मामले में रक्षक जीतता है
• खेल हमेशा चलता रहता है, ऐसी स्थिति में रक्षक जीतता है।
• गेम राज्यों तक पहुंचता है $(p,q)$, जिसका दौरा पहले ही किया जा चुका है। यह एक अनंत खेल के बराबर है और डिफेंडर के लिए जीत के रूप में गिना जाता है।

उपरोक्त परिभाषा के अनुसार सिस्टम एक द्विसिमुलेशन है यदि और केवल तभी जब रक्षक के लिए जीतने की रणनीति मौजूद हो।

कोलगेब्रिक परिभाषा

राज्य संक्रमण प्रणालियों के लिए एक द्विसिमुलेशन सहसंयोजक पॉवरसेट ऑपरेटर के प्रकार के लिए कोलजेब्रा में द्विसिमुलेशन का एक विशेष मामला है। ध्यान दें कि प्रत्येक राज्य संक्रमण प्रणाली $(S,\Lambda ,\rightarrow )$ क्या द्विभाजन एक फ़ंक्शन है $\xi _{\rightarrow }$ से $S$ के सत्ता स्थापित के लिए $S$ द्वारा अनुक्रमित $\Lambda$ के रूप में लिखा गया है ${\mathcal {P}}(\Lambda \times S)$, द्वारा परिभाषित

$$p\mapsto \{(\alpha ,q)\in \Lambda \times S:p{\overset {\alpha }{\rightarrow }}q\}.$$

होने देना $\pi _{i}\colon S\times S\to S$ होना $i$-वां उत्पाद (श्रेणी सिद्धांत) मानचित्रण $(p,q)$ को $p$ और $q$ क्रमशः के लिए $i=1,2$; और ${\mathcal {P}}(\Lambda \times \pi _{1})$ की आगे की छवि $\pi _{1}$ तीसरे घटक को हटाकर परिभाषित किया गया

$$P\mapsto \{(\alpha ,p)\in \Lambda \times S:\exists q.(\alpha ,p,q)\in P\}$$

कहाँ $P$ का एक उपसमुच्चय है $\Lambda \times S\times S$. इसी प्रकार के लिए ${\mathcal {P}}(\Lambda \times \pi _{2})$.

उपरोक्त नोटेशन का उपयोग करते हुए, एक संबंध $R\subseteq S\times S$ एक संक्रमण प्रणाली पर एक द्विसिमुलेशन है $(S,\Lambda ,\rightarrow )$ यदि और केवल यदि कोई संक्रमण प्रणाली मौजूद है $\gamma \colon R\to {\mathcal {P}}(\Lambda \times R)$ रिश्ते पर $R$ जैसे कि क्रमविनिमेय आरेख

आवागमन, अर्थात् के लिए $i=1,2$, समीकरण

$$\xi _{\rightarrow }\circ \pi _{i}={\mathcal {P}}(\Lambda \times \pi _{i})\circ \gamma$$

पकड़ कहाँ $\xi _{\rightarrow }$ का कार्यात्मक प्रतिनिधित्व है $(S,\Lambda ,\rightarrow )$.

द्विसिमुलेशन के प्रकार

विशेष संदर्भों में द्विसिमुलेशन की धारणा को कभी-कभी अतिरिक्त आवश्यकताओं या बाधाओं को जोड़कर परिष्कृत किया जाता है। एक उदाहरण हकलाना द्विसिमुलेशन का है, जिसमें एक प्रणाली के एक संक्रमण को दूसरे के कई संक्रमणों के साथ मिलान किया जा सकता है, बशर्ते कि मध्यवर्ती राज्य शुरुआती स्थिति (हकलाना) के बराबर हों। यदि राज्य संक्रमण प्रणाली में मौन (या आंतरिक) कार्रवाई की धारणा शामिल होती है, तो एक अलग प्रकार लागू होता है, जिसे अक्सर इसके साथ दर्शाया जाता है $\tau$, यानी ऐसी क्रियाएं जो बाहरी पर्यवेक्षकों द्वारा दिखाई नहीं देती हैं, तो द्विसिमुलेशन को कमजोर द्विसिमुलेशन में शिथिल किया जा सकता है, जिसमें यदि दो अवस्थाएं होती हैं $p$ और $q$ द्विसमान हैं और कुछ संख्या में आंतरिक क्रियाएं होती हैं $p$ किसी राज्य के लिए $p'$ तो फिर राज्य का अस्तित्व होना ही चाहिए $q'$ जैसे कि आंतरिक क्रियाओं की कुछ संख्या (संभवतः शून्य) हो $q$ को $q'$. एक रिश्ता ${\mathcal {R}}$ प्रक्रियाओं पर एक कमजोर द्विसिमुलेशन है यदि निम्नलिखित (के साथ) कायम रहता है ${\mathcal {S}}\in \{{\mathcal {R}},{\mathcal {R}}^{-1}\}$, और $a,\tau$ क्रमशः एक अवलोकनीय और मूक संक्रमण होने के नाते):

$$\forall p,q.\quad (p,q)\in {\mathcal {S}}\Rightarrow p{\stackrel {\tau }{\rightarrow }}p'\Rightarrow \exists q'.\quad q{\stackrel {\tau ^{\ast }}{\rightarrow }}q'\wedge (p',q')\in {\mathcal {S}}$$

$$\forall p,q.\quad (p,q)\in {\mathcal {S}}\Rightarrow p{\stackrel {a}{\rightarrow }}p'\Rightarrow \exists q'.\quad q{\stackrel {\tau ^{\ast }a\tau ^{\ast }}{\rightarrow }}q'\wedge (p',q')\in {\mathcal {S}}$$

यह द्विसिमुलेशन से लेकर #कंप्यूटर विज्ञान तक के संबंध से निकटता से संबंधित है।

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

बिसिमुलेशन और मोडल तर्क

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

एल्गोरिथम

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

यह भी देखें

• सिमुलेशन प्रीऑर्डर
• सर्वांगसम संबंध
• संभाव्य द्विसिमुलेशन

अग्रिम पठन

• Park, David (1981). "Concurrency and Automata on Infinite Sequences". In Deussen, Peter (ed.). Theoretical Computer Science. Proceedings of the 5th GI-Conference, Karlsruhe. Lecture Notes in Computer Science. Vol. 104. Springer-Verlag. pp. 167–183. doi:10.1007/BFb0017309. ISBN 978-3-540-10576-3.
• Milner, Robin (1989). Communication and Concurrency. Prentice Hall. ISBN 0-13-114984-9.
• Sangiorgi, Davide (2011). An introduction to Bisimulation and Coinduction. Cambridge, UK: Cambridge University Press. ISBN 9781107003637. OCLC 773040572.

बाहरी संबंध

सॉफ्टवेयर उपकरण

• सीएडीपी: विभिन्न द्विसिमुलेशन के अनुसार परिमित-राज्य प्रणालियों को कम करने और तुलना करने के लिए उपकरण
• mCRL2: विभिन्न द्विसिमुलेशन के अनुसार परिमित-अवस्था प्रणालियों को छोटा करने और तुलना करने के लिए उपकरण
• द बिसिमुलेशन गेम गेम

श्रेणी:सैद्धांतिक कंप्यूटर विज्ञान श्रेणी:औपचारिक तरीके श्रेणी:कंप्यूटर विज्ञान में तर्क श्रेणी:संक्रमण प्रणालियाँ