सिमुलेशन (कंप्यूटर विज्ञान): Difference between revisions
(TEXT) |
(TEXT) |
||
| Line 1: | Line 1: | ||
[[सैद्धांतिक कंप्यूटर विज्ञान]] में ''' | [[सैद्धांतिक कंप्यूटर विज्ञान]] में '''सिमुलेशन''' अवस्था परिवर्तन प्रणालियों से संबद्ध प्रणालियों के मध्य एक [[संबंध (गणित)]] है जो उसी तरह से व्यवहार करता है जैसे एक प्रणाली दूसरे का ''सिमुलेशन'' करती है। | ||
सहज रूप से, एक प्रणाली दूसरी प्रणाली का | सहज रूप से, एक प्रणाली दूसरी प्रणाली का सिमुलेशन करती है यदि वह उसकी सभी परिवर्तन के समान होती है। | ||
मूल परिभाषा एक परिवर्तन प्रणाली के अंतर्गत अवस्था से संबंधित है, लेकिन इसे संबंधित घटकों के [[असंयुक्त संघ|असंयुक्त सम्मिलन]] से युक्त एक प्रणाली का निर्माण करके दो अलग-अलग परिवर्तन प्रणालियों को जोड़ने के लिए आसानी से अनुकूलित किया जा सकता है। | मूल परिभाषा एक परिवर्तन प्रणाली के अंतर्गत अवस्था से संबंधित है, लेकिन इसे संबंधित घटकों के [[असंयुक्त संघ|असंयुक्त सम्मिलन]] से युक्त एक प्रणाली का निर्माण करके दो अलग-अलग परिवर्तन प्रणालियों को जोड़ने के लिए आसानी से अनुकूलित किया जा सकता है। | ||
==औपचारिक परिभाषा== | ==औपचारिक परिभाषा== | ||
एक लेबल अवस्था परिवर्तन प्रणाली (<math>S</math>, <math>\Lambda</math>, →) को देखते हुए, जहां <math>S</math> अवस्था का एक समुच्चय है, <math>\Lambda</math> लेबलों का एक समुच्चय है और → लेबल किए गए परिवर्तन का एक समुच्चय है (अर्थात, <math>S \times \Lambda \times S</math> का एक उपसमुच्चय), एक संबंध <math>R \subseteq S \times S</math> एक ''' | एक लेबल अवस्था परिवर्तन प्रणाली (<math>S</math>, <math>\Lambda</math>, →) को देखते हुए, जहां <math>S</math> अवस्था का एक समुच्चय है, <math>\Lambda</math> लेबलों का एक समुच्चय है और → लेबल किए गए परिवर्तन का एक समुच्चय है (अर्थात, <math>S \times \Lambda \times S</math> का एक उपसमुच्चय), एक संबंध <math>R \subseteq S \times S</math> एक '''सिमुलेशन''' है यदि और केवल यदि <math>R</math> में अवस्था की प्रत्येक जोड़ी <math>(p,q)</math> और <math>\Lambda</math> में सभी लेबल α के लिए: | ||
:<b>यदि <math>p \overset{\alpha}{\rightarrow} p'</math>, तो <math>q \overset{\alpha}{\rightarrow} q'</math> ऐसा है कि <math>(p',q') \in R</math></b> | :<b>यदि <math>p \overset{\alpha}{\rightarrow} p'</math>, तो <math>q \overset{\alpha}{\rightarrow} q'</math> ऐसा है कि <math>(p',q') \in R</math></b> | ||
| Line 12: | Line 12: | ||
समान रूप से, [[संबंधों की संरचना|संबंधपरक संरचना]] के संदर्भ में: | समान रूप से, [[संबंधों की संरचना|संबंधपरक संरचना]] के संदर्भ में: | ||
:<math>R^{-1}\,;\, \overset{\alpha}{\rightarrow}\quad {\subseteq}\quad \overset{\alpha}{\rightarrow}\,;\, R^{-1}</math> | :<math>R^{-1}\,;\, \overset{\alpha}{\rightarrow}\quad {\subseteq}\quad \overset{\alpha}{\rightarrow}\,;\, R^{-1}</math> | ||
<math>S</math> में दो अवस्था <math>p</math> और <math>q</math> दिए जाने पर, <math>p</math> को <math>q</math> द्वारा ''' | <math>S</math> में दो अवस्था <math>p</math> और <math>q</math> दिए जाने पर, <math>p</math> को <math>q</math> द्वारा '''सिमुलेशन''' किया जा सकता है, जिसे <math>p \, \leq \, q</math> लिखा जाता है, यदि और केवल यदि कोई सिमुलेशन <math>R</math> जैसे कि <math>(p, q) \in R</math> है। संबंध <math>\leq</math> को '''सिमुलेशन पूर्व-ऑर्डर''' कहा जाता है, और यह सभी सिमुलेशन का संघ है: <math>(p,q) \in\,\leq\,</math> यथार्थतः जब <math>(p, q) \in R</math> कुछ सिमुलेशन <math>R</math> के लिए है। | ||
संघ के अंतर्गत | संघ के अंतर्गत सिमुलेशन का समुच्चय बंद है;<ref group="Note"> | ||
Meaning the union of two simulations is a simulation. | Meaning the union of two simulations is a simulation. | ||
</ref> इसलिए, | </ref> इसलिए, सिमुलेशन [[पूर्व आदेश|पूर्व ऑर्डर]] स्वयं एक सिमुलेशन है। यह सभी सिमुलेशन का संघ है, यह अद्वितीय सबसे बड़ा सिमुलेशन है। निजवाचक और सकर्मक संवरक के अंतर्गत सिमुलेशन भी बंद हैं; इसलिए, सबसे बड़ा सिमुलेशन प्रतिवर्ती और सकर्मक होना चाहिए। इससे यह पता चलता है कि सबसे बड़ा सिमुलेशन - सिमुलेशन पूर्व-ऑर्डर - वास्तव में एक पूर्व-ऑर्डर संबंध है।<ref>{{cite book |last=Milner |first=Robin |title=संचार और समवर्ती|year=1989 |isbn=0131149849 |publisher=Prentice-Hall, Inc. |location=USA}}</ref> ध्यान दें कि एक से अधिक संबंध हो सकते हैं जो सिमुलेशन और पूर्व-ऑर्डर दोनों हैं;<ref group="Note">Consider the relations <math>\{\}</math> and <math>\{(0, 0)\}</math> — each is both a simulation and a preorder.</ref> सिमुलेशन पूर्व-ऑर्डर शब्द उनमें से सबसे बड़े को संदर्भित करता है (जो अन्य सभी का अधिसमुच्चय है)। | ||
दो अवस्था <math>p</math> और <math>q</math> को '''समान''' कहा जाता है, <math>p \leq\geq q</math> लिखा जाता है, यदि और केवल यदि <math>p</math> को <math>q</math> द्वारा | दो अवस्था <math>p</math> और <math>q</math> को '''समान''' कहा जाता है, <math>p \leq\geq q</math> लिखा जाता है, यदि और केवल यदि <math>p</math> को <math>q</math> द्वारा सिमुलेशन किया जा सकता है और <math>q</math> को <math>p</math> द्वारा सिमुलेशन किया जा सकता है। इस प्रकार समानता सिमुलेशन पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह प्रतिवर्ती, सममित और सकर्मक है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक सिमुलेशन नहीं है, और यथार्थतः उन प्रकरणों में जब यह एक सिमुलेशन नहीं है, यह पूरी तरह से [[द्विसमानता]] से अधिक स्थूल है (अर्थात् यह द्विसमानता का एक अधिसमुच्चय है)।<ref group="Note">For an example, see '''Fig. 1''' in {{cite journal | ||
|last1 = Champarnaud | |last1 = Champarnaud | ||
|first1 = J.-M | |first1 = J.-M | ||
| Line 32: | Line 32: | ||
|doi = 10.1016/j.tcs.2004.02.048 | |doi = 10.1016/j.tcs.2004.02.048 | ||
|doi-access = free | |doi-access = free | ||
}}</ref> प्रमाण देने के लिए, एक समानता पर विचार करें जो एक | }}</ref> प्रमाण देने के लिए, एक समानता पर विचार करें जो एक सिमुलेशन है। यह सममित है, यह एक ''द्विसिमुलेशन'' है। यह द्विसमानता का एक ''उपसमुच्चय'' होना चाहिए, जो सभी द्विसिमुलेशन का संघ है। यह देखना आसान है कि समानता हमेशा द्विसमानता का ''अधिसमुच्चय'' है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक सिमुलेशन है, तो यह द्विसमानता के समान है। यह द्विसमानता के समान है, तो यह स्वाभाविक रूप से एक सिमुलेशन है (क्योंकि द्विसमानता एक सिमुलेशन है)। इसलिए, समानता एक सिमुलेशन है यदि और केवल यदि यह द्विसमानता के समान है। यदि ऐसा नहीं होता है, तो यह इसका यथार्थ रूप से अधिसमुच्चय होना चाहिए; इसलिए यथार्थ रूप से स्थूल तुल्यता संबंध है। | ||
------ | ------ | ||
| Line 38: | Line 38: | ||
==अलग-अलग परिवर्तन प्रणालियों की समानता== | ==अलग-अलग परिवर्तन प्रणालियों की समानता== | ||
दो अलग-अलग परिवर्तन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, | दो अलग-अलग परिवर्तन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, सिमुलेशन और समानता की मूल धारणाओं का उपयोग दो मशीनों की असंयुक्त संरचना बनाकर किया जा सकता है, (S, Λ, →) S = S' ∐ S", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त सम्मिलन संचालक है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[स्थिति परिवर्तन प्रणाली|अवस्था परिवर्तन प्रणाली]] | * [[स्थिति परिवर्तन प्रणाली|अवस्था परिवर्तन प्रणाली]] | ||
* [[द्विसिमुलेशन | * [[द्विसिमुलेशन]] | ||
*[[सहसंयोजन]] | *[[सहसंयोजन]] | ||
* [[संक्रियात्मक शब्दार्थ]] | * [[संक्रियात्मक शब्दार्थ]] | ||
Revision as of 10:55, 4 August 2023
सैद्धांतिक कंप्यूटर विज्ञान में सिमुलेशन अवस्था परिवर्तन प्रणालियों से संबद्ध प्रणालियों के मध्य एक संबंध (गणित) है जो उसी तरह से व्यवहार करता है जैसे एक प्रणाली दूसरे का सिमुलेशन करती है।
सहज रूप से, एक प्रणाली दूसरी प्रणाली का सिमुलेशन करती है यदि वह उसकी सभी परिवर्तन के समान होती है।
मूल परिभाषा एक परिवर्तन प्रणाली के अंतर्गत अवस्था से संबंधित है, लेकिन इसे संबंधित घटकों के असंयुक्त सम्मिलन से युक्त एक प्रणाली का निर्माण करके दो अलग-अलग परिवर्तन प्रणालियों को जोड़ने के लिए आसानी से अनुकूलित किया जा सकता है।
औपचारिक परिभाषा
एक लेबल अवस्था परिवर्तन प्रणाली (, , →) को देखते हुए, जहां अवस्था का एक समुच्चय है, लेबलों का एक समुच्चय है और → लेबल किए गए परिवर्तन का एक समुच्चय है (अर्थात, का एक उपसमुच्चय), एक संबंध एक सिमुलेशन है यदि और केवल यदि में अवस्था की प्रत्येक जोड़ी और में सभी लेबल α के लिए:
- यदि , तो ऐसा है कि
समान रूप से, संबंधपरक संरचना के संदर्भ में:
में दो अवस्था और दिए जाने पर, को द्वारा सिमुलेशन किया जा सकता है, जिसे लिखा जाता है, यदि और केवल यदि कोई सिमुलेशन जैसे कि है। संबंध को सिमुलेशन पूर्व-ऑर्डर कहा जाता है, और यह सभी सिमुलेशन का संघ है: यथार्थतः जब कुछ सिमुलेशन के लिए है।
संघ के अंतर्गत सिमुलेशन का समुच्चय बंद है;[Note 1] इसलिए, सिमुलेशन पूर्व ऑर्डर स्वयं एक सिमुलेशन है। यह सभी सिमुलेशन का संघ है, यह अद्वितीय सबसे बड़ा सिमुलेशन है। निजवाचक और सकर्मक संवरक के अंतर्गत सिमुलेशन भी बंद हैं; इसलिए, सबसे बड़ा सिमुलेशन प्रतिवर्ती और सकर्मक होना चाहिए। इससे यह पता चलता है कि सबसे बड़ा सिमुलेशन - सिमुलेशन पूर्व-ऑर्डर - वास्तव में एक पूर्व-ऑर्डर संबंध है।[1] ध्यान दें कि एक से अधिक संबंध हो सकते हैं जो सिमुलेशन और पूर्व-ऑर्डर दोनों हैं;[Note 2] सिमुलेशन पूर्व-ऑर्डर शब्द उनमें से सबसे बड़े को संदर्भित करता है (जो अन्य सभी का अधिसमुच्चय है)।
दो अवस्था और को समान कहा जाता है, लिखा जाता है, यदि और केवल यदि को द्वारा सिमुलेशन किया जा सकता है और को द्वारा सिमुलेशन किया जा सकता है। इस प्रकार समानता सिमुलेशन पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह प्रतिवर्ती, सममित और सकर्मक है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक सिमुलेशन नहीं है, और यथार्थतः उन प्रकरणों में जब यह एक सिमुलेशन नहीं है, यह पूरी तरह से द्विसमानता से अधिक स्थूल है (अर्थात् यह द्विसमानता का एक अधिसमुच्चय है)।[Note 3] प्रमाण देने के लिए, एक समानता पर विचार करें जो एक सिमुलेशन है। यह सममित है, यह एक द्विसिमुलेशन है। यह द्विसमानता का एक उपसमुच्चय होना चाहिए, जो सभी द्विसिमुलेशन का संघ है। यह देखना आसान है कि समानता हमेशा द्विसमानता का अधिसमुच्चय है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक सिमुलेशन है, तो यह द्विसमानता के समान है। यह द्विसमानता के समान है, तो यह स्वाभाविक रूप से एक सिमुलेशन है (क्योंकि द्विसमानता एक सिमुलेशन है)। इसलिए, समानता एक सिमुलेशन है यदि और केवल यदि यह द्विसमानता के समान है। यदि ऐसा नहीं होता है, तो यह इसका यथार्थ रूप से अधिसमुच्चय होना चाहिए; इसलिए यथार्थ रूप से स्थूल तुल्यता संबंध है।
- ↑ Meaning the union of two simulations is a simulation.
- ↑ Consider the relations and — each is both a simulation and a preorder.
- ↑ For an example, see Fig. 1 in Champarnaud, J.-M; Coulon, F. (2004). "NFA reduction algorithms by means of regular inequalities". Theoretical Computer Science. 327 (3): 241–253. doi:10.1016/j.tcs.2004.02.048. ISSN 0304-3975.
अलग-अलग परिवर्तन प्रणालियों की समानता
दो अलग-अलग परिवर्तन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, सिमुलेशन और समानता की मूल धारणाओं का उपयोग दो मशीनों की असंयुक्त संरचना बनाकर किया जा सकता है, (S, Λ, →) S = S' ∐ S", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त सम्मिलन संचालक है।
यह भी देखें
संदर्भ
- 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.
- 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.
- ↑ Milner, Robin (1989). संचार और समवर्ती. USA: Prentice-Hall, Inc. ISBN 0131149849.
