द्विअनुकरण

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

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

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

एक संक्रमण प्रणाली को देखते हुए ($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: विभिन्न द्विसिमुलेशन के अनुसार परिमित-अवस्था प्रणालियों को छोटा करने और तुलना करने के लिए उपकरण
• द द्विसिमुलेशन गेम गेम

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