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

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

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

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

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

एक राज्य संक्रमण प्रणाली को देखते हुए ($S$, $\Lambda$, →), कहाँ $S$ राज्यों का एक समूह है, $\Lambda$ लेबलों का एक सेट है और → लेबल किए गए ट्रांज़िशन का एक सेट है (यानी, का एक सबसेट) $S\times \Lambda \times S$), एक रिश्ता $R\subseteq S\times S$ यदि और केवल राज्यों के प्रत्येक जोड़े के लिए यह एक अनुकरण है $(p,q)$ में $R$ और सभी लेबल α में $\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}$

दो राज्य दिए गए $p$ और $q$ में $S$, $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$. इस प्रकार समानता सिमुलेशन प्रीऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह प्रतिवर्ती, सममित और सकर्मक है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक अनुकरण नहीं है, और ठीक उन मामलों में जब यह एक अनुकरण नहीं है, यह द्विसमानता की तुलना में सख्ती से अधिक मोटा है (अर्थात् यह द्विसमानता का एक सुपरसेट है)। गवाही देने के लिए, एक समानता पर विचार करें जो एक अनुकरण है। चूँकि यह सममित है, यह एक द्विसिमुलेशन है। फिर यह द्विसमानता का एक उपसमुच्चय होना चाहिए, जो सभी द्विसिमुलेशन का मिलन है। फिर भी यह देखना आसान है कि समानता हमेशा द्विसमानता का सुपरसेट होती है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक अनुकरण है, तो यह द्विसमानता के बराबर है। और यदि यह द्विसमानता के बराबर है, तो यह स्वाभाविक रूप से एक अनुकरण है (क्योंकि द्विसमानता एक अनुकरण है)। इसलिए, समानता एक अनुकरण है यदि और केवल यदि यह द्विसमानता के बराबर हो। यदि ऐसा नहीं होता है, तो यह इसका सख्त सुपरसेट होना चाहिए; इसलिए एक सख्ती से स्थूल तुल्यता संबंध।

---

अलग-अलग संक्रमण प्रणालियों की समानता

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

यह भी देखें

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

संदर्भ

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.