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

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

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

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

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

एक लेबल अवस्था परिवर्तन प्रणाली ($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.