सिमुलेशन (कंप्यूटर विज्ञान)

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

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

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

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

एक लेबल अवस्था ट्रांजिशन प्रणाली ($S$, $\Lambda$, →) को देखते हुए, जहां $S$ अवस्था का एक समुच्चय है, $\Lambda$ लेबलों का एक समुच्चय है और → लेबल किए गए ट्रांजिशन का एक समुच्चय है (अर्थात, $S\times \Lambda \times S$ का एक उपसमुच्चय), एक संबंध $R\subseteq S\times S$ सिमुलेशन है यदि और केवल यदि $R$ में अवस्था की प्रत्येक जोड़ी $(p,q)$ और $\Lambda$ में सभी लेबल α के लिए:

यदि $p{\overset {\alpha }{\rightarrow }}p'$, तो $q{\overset {\alpha }{\rightarrow }}q'$ ऐसा है कि $(p',q')\in R$

समान रूप से, संबंधात्मक कम्पोजीशन के संदर्भ में:

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

$S$ में दो अवस्था $p$ और $q$ दिए जाने पर, $p$ को $q$ द्वारा सिमुलेशन किया जा सकता है, जिसे $p\,\leq \,q$ लिखा जाता है, यदि और केवल यदि कोई सिमुलेशन $R$ जैसे कि $(p,q)\in R$ है। संबंध $\leq$ को सिमुलेशन पूर्व-ऑर्डर कहा जाता है, और यह सभी सिमुलेशन का यूनियन है: $(p,q)\in \,\leq \,$ यथार्थतः जब $(p,q)\in R$ कुछ सिमुलेशन $R$ के लिए है।

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

दो अवस्था $p$ और $q$ को समान कहा जाता है, $p\leq \geq q$ लिखा जाता है, यदि और केवल यदि $p$ को $q$ द्वारा सिमुलेशन किया जा सकता है और $q$ को $p$ द्वारा सिमुलेशन किया जा सकता है। इस प्रकार समानता सिमुलेशन पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह रिफ्लेक्सिव, सममित और ट्रांजिटिव है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक सिमुलेशन नहीं है, और यथार्थतः उन प्रकरणों में जब यह एक सिमुलेशन नहीं है, यह पूरी तरह से द्विसमानता से अधिक स्थूल है (अर्थात् यह द्विसमानता का एक अधिसमुच्चय है)। प्रमाण देने के लिए, एक समानता पर विचार करें जो एक सिमुलेशन है। यह सममित है, यह एक द्विसिमुलेशन है। यह द्विसमानता का एक उपसमुच्चय होना चाहिए, जो सभी द्विसिमुलेशन का यूनियन है। यह देखना आसान है कि समानता हमेशा द्विसमानता का अधिसमुच्चय है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक सिमुलेशन है, तो यह द्विसमानता के समान है। यह द्विसमानता के समान है, तो यह स्वाभाविक रूप से एक सिमुलेशन है (क्योंकि द्विसमानता एक सिमुलेशन है)। इसलिए, समानता एक सिमुलेशन है यदि और केवल यदि यह द्विसमानता के समान है। यदि ऐसा नहीं होता है, तो यह इसका यथार्थ रूप से अधिसमुच्चय होना चाहिए; इसलिए यथार्थ रूप से स्थूल तुल्यता संबंध है।

---

अलग-अलग ट्रांजिशन प्रणाली की समानता

दो अलग-अलग ट्रांजिशन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, सिमुलेशन और समानता की मूल धारणाओं का उपयोग दो मशीनों की असंयुक्त संरचना बनाकर किया जा सकता है, (S, Λ, →) S = S' ∐ S", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त यूनियन संचालक है।

यह भी देखें

• अवस्था ट्रांजिशन प्रणाली
• द्विसिमुलेशन
• सहसंयोजन
• संक्रियात्मक शब्दार्थ

संदर्भ

1. Park, David (1981). "Concurrency and Automata on Infinite Sequences" (PDF). In Deussen, Peter (ed.). 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.
2. van Glabbeek, R. J. (2001). "The Linear Time – Branching Time Spectrum I: The Semantics of Concrete, Sequential Processes". Handbook of Process Algebra. Elsevier. pp. 3–99.