द्विअनुकरण

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

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

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

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

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