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

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

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

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

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

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