ट्रेस मोनॉयड: Difference between revisions
From Vigyanwiki
No edit summary |
m (5 revisions imported from alpha:ट्रेस_मोनॉयड) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Generalization of strings in computer science}}[[कंप्यूटर विज्ञान]] में, ट्रेस [[औपचारिक भाषा]]ओं का एक | {{Short description|Generalization of strings in computer science}}[[कंप्यूटर विज्ञान]] में, '''ट्रेस''' [[औपचारिक भाषा]]ओं का एक समूह है, जिसमें स्ट्रिंग में कुछ अक्षरों को क्रमविनिमेय संपत्ति की अनुमति है, किन्तु अन्य को नहीं। यह अक्षरों को सदैव एक निश्चित क्रम में रहने के लिए मजबूर न करके, किंतु कुछ फेरबदल करने की अनुमति देकर, एक स्ट्रिंग की अवधारणा को सामान्यीकृत करता है। मैकमोहन के मास्टर प्रमेय का संयुक्त प्रमाण देने के लिए 1969 में [[पियरे कार्टियर (गणितज्ञ)]] और [[डोमिनिक फोटा]] द्वारा ट्रेस प्रस्तुत किए गए थे। ट्रेस का उपयोग [[समानांतर कंप्यूटिंग]] के सिद्धांतों में किया जाता है, जहां कम्यूटिंग अक्षर किसी कार्य के कुछ हिस्सों को दर्शाते हैं जो एक दूसरे से स्वतंत्र रूप से निष्पादित हो सकते हैं, जबकि गैर-कम्यूटिंग अक्षर ताले, सिंक्रोनाइज़ेशन (कंप्यूटर विज्ञान) या [[थ्रेड (कंप्यूटिंग)]] के लिए होते हैं।<ref name="CS161">Sándor & Crstici (2004) p.161</ref> | ||
ट्रेस मोनोइड्स का उपयोग | '''ट्रेस मोनॉइड''' या '''मुक्त आंशिक रूप से क्रमविनिमेय मोनॉइड''', ट्रेस का एक मोनॉइड है। संक्षेप में, इसका निर्माण इस प्रकार किया गया है: कम्यूटिंग अक्षरों के समूह एक [[निर्भरता संबंध]] द्वारा दिए गए हैं। यह समतुल्य तारों के समतुल्य संबंध को प्रेरित करते हैं; तुल्यता वर्गों के तत्व निशान हैं। तुल्यता संबंध तब मुक्त मोनॉइड (परिमित लंबाई के सभी तारों का समूह) को तुल्यता वर्गों के एक समूह में विभाजित करता है; परिणाम अभी भी एक [[मोनोइड]] है; यह एक [[ अर्धसमूह |अर्धसमूह]] है और इसे ''ट्रेस मोनॉइड'' कहा जाता है। ट्रेस मोनॉइड [[सार्वभौमिक संपत्ति]] है, जिसमें सभी निर्भरता-होमोमोर्फिक (नीचे देखें) मोनॉइड वास्तव में आइसोमोर्फिक हैं। | ||
ट्रेस मोनोइड्स का उपयोग सामान्यतः समानांतर कंप्यूटिंग को मॉडल करने के लिए किया जाता है, जो प्रक्रिया कैलकुलस की नींव बनाता है। वह [[ट्रेस सिद्धांत]] में अध्ययन की वस्तु हैं। ट्रेस मोनोइड्स की उपयोगिता इस तथ्य से आती है कि वह [[निर्भरता ग्राफ]] के मोनोइड के [[समरूपी]] हैं; इस प्रकार बीजगणितीय विधि को [[ग्राफ़ (अलग गणित)|ग्राफ़ (भिन्न गणित)]] पर प्रयुक्त करने की अनुमति मिलती है, और इसके विपरीत। वह इतिहास मोनोइड के समरूपी भी हैं, जो एक या अधिक कंप्यूटरों पर सभी निर्धारित प्रक्रियाओं के संदर्भ में व्यक्तिगत प्रक्रियाओं की गणना के इतिहास को मॉडल करते हैं। | |||
==ट्रेस== | ==ट्रेस== | ||
होने देना <math>\Sigma^*</math> मुक्त मोनॉइड को निरूपित करें, अर्थात वर्णमाला में लिखे सभी तारों का समूह <math>\Sigma</math>. यहां, तारांकन, | होने देना <math>\Sigma^*</math> मुक्त मोनॉइड को निरूपित करें, अर्थात वर्णमाला में लिखे सभी तारों का समूह <math>\Sigma</math>. यहां, तारांकन, सदैव की तरह, [[क्लेन स्टार]] को दर्शाता है। एक निर्भरता संबंध <math>I</math> पर <math>\Sigma</math> फिर एक (सममित) द्विआधारी संबंध उत्पन्न करता है <math>\sim</math> पर <math>\Sigma^*</math>, कहाँ <math>u\sim v</math> यदि और केवल यदि अस्तित्व है <math>x,y\in \Sigma^*</math>, और एक जोड़ी <math>(a,b)\in I</math> ऐसा है कि <math>u=xaby</math> और <math>v=xbay</math>. यहाँ, <math>u,v,x</math> और <math>y</math> स्ट्रिंग्स (तत्वों) के रूप में समझा जाता है <math>\Sigma^*</math>), जबकि <math>a</math> और <math>b</math> अक्षर हैं (के तत्व) <math>\Sigma</math>). | ||
ट्रेस को रिफ्लेक्सिव ट्रांजिटिव क्लोजर के रूप में परिभाषित किया गया है <math>\sim</math>. इस प्रकार ट्रेस एक तुल्यता संबंध है <math>\Sigma^*</math>, और द्वारा दर्शाया गया है <math>\equiv_D</math>, कहाँ <math>D</math> के अनुरूप निर्भरता संबंध है <math>I ,</math> वह है <math>D = (\Sigma \times \Sigma) \setminus I</math> और इसके विपरीत <math>I = (\Sigma \times \Sigma) \setminus D .</math> | ट्रेस को रिफ्लेक्सिव ट्रांजिटिव क्लोजर के रूप में परिभाषित किया गया है <math>\sim</math>. इस प्रकार ट्रेस एक तुल्यता संबंध है <math>\Sigma^*</math>, और द्वारा दर्शाया गया है <math>\equiv_D</math>, कहाँ <math>D</math> के अनुरूप निर्भरता संबंध है <math>I ,</math> वह है <math>D = (\Sigma \times \Sigma) \setminus I</math> और इसके विपरीत <math>I = (\Sigma \times \Sigma) \setminus D .</math> प्रकट है, भिन्न-भिन्न निर्भरताएं भिन्न-भिन्न तुल्यता संबंध देंगी। | ||
[[सकर्मक समापन]] का तात्पर्य यह है <math>u\equiv v</math> यदि और केवल यदि स्ट्रिंग्स का एक क्रम | [[सकर्मक समापन]] का तात्पर्य यह है <math>u\equiv v</math> यदि और केवल यदि स्ट्रिंग्स का एक क्रम उपस्तिथ है <math>(w_0,w_1,\cdots,w_n)</math> ऐसा है कि <math>u\sim w_0</math> और <math>v\sim w_n</math> और <math>w_i\sim w_{i+1}</math> सभी के लिए <math>0\le i < n</math>. मोनोइड ऑपरेशन के अनुसार ट्रेस स्थिर है <math>\Sigma^*</math> (संयोजन) और इसलिए यह एक [[सर्वांगसम संबंध]] है <math>\Sigma^*</math>. | ||
ट्रेस मोनॉइड, जिसे | ट्रेस मोनॉइड, जिसे सामान्यतः इस रूप में दर्शाया जाता है <math>\mathbb {M}(D)</math>, को भागफल मोनोइड के रूप में परिभाषित किया गया है | ||
:<math>\mathbb {M}(D) = \Sigma^* / \equiv_D.</math> | :<math>\mathbb {M}(D) = \Sigma^* / \equiv_D.</math> | ||
समरूपता | समरूपता | ||
:<math>\phi_D:\Sigma^*\to \mathbb {M}(D)</math> | :<math>\phi_D:\Sigma^*\to \mathbb {M}(D)</math> | ||
इसे | इसे सामान्यतः [[प्राकृतिक परिवर्तन]] या विहित समरूपता के रूप में जाना जाता है। ''प्राकृतिक'' या ''विहित'' शब्द योग्य हैं, यह इस तथ्य से पता चलता है कि यह रूपवाद एक सार्वभौमिक संपत्ति का प्रतीक है, जैसा कि पश्चात् के अनुभाग में चर्चा की गई है। | ||
किसी को ट्रेस मोनॉयड भी मिलेगा जिसे इस रूप में दर्शाया गया है <math>M(\Sigma,I)</math> कहाँ <math>I</math> स्वतंत्रता संबंध है. भ्रामक रूप से, कोई व्यक्ति स्वतंत्रता संबंध के | किसी को ट्रेस मोनॉयड भी मिलेगा जिसे इस रूप में दर्शाया गया है <math>M(\Sigma,I)</math> कहाँ <math>I</math> स्वतंत्रता संबंध है. भ्रामक रूप से, कोई व्यक्ति स्वतंत्रता संबंध के अतिरिक्त उपयोग किए गए कम्यूटेशन संबंध को भी पा सकता है (यह सभी विकर्ण तत्वों को सम्मिलित करके भिन्न होता है)। | ||
==उदाहरण== | ==उदाहरण== | ||
| Line 37: | Line 38: | ||
==गुण== | ==गुण== | ||
रद्दीकरण संपत्ति बताती है कि [[ स्ट्रिंग ऑपरेशन ]] के | '''रद्दीकरण संपत्ति''' बताती है कि [[ स्ट्रिंग ऑपरेशन |स्ट्रिंग ऑपरेशन]] के अनुसार समतुल्यता बनाए रखी जाती है। अर्थात यदि <math>w\equiv v</math>, तब <math>(w\div a)\equiv (v\div a)</math>. यहाँ, संकेतन <math>w\div a</math> दाएँ रद्दीकरण को दर्शाता है, दाहिनी ओर से प्रारंभ होने वाली स्ट्रिंग w से अक्षर a की पहली घटना को हटाना। वाम-निरस्तीकरण से भी समतुल्यता बनी रहती है। अनेक परिणाम इस प्रकार हैं: | ||
* एंबेडिंग: <math>w \equiv v</math> | * एंबेडिंग: <math>w \equiv v</math> यदि और केवल यदि <math>xwy\equiv xvy</math> स्ट्रिंग्स x और y के लिए। इस प्रकार, ट्रेस मोनॉइड एक वाक्यात्मक मोनॉइड है। | ||
*स्वतंत्रता: यदि <math>ua\equiv vb</math> और <math>a\ne b</math>, | *स्वतंत्रता: यदि <math>ua\equiv vb</math> और <math>a\ne b</math>, तब a, b से स्वतंत्र है। वह है, <math>(a,b)\in I_D</math>. इसके अतिरिक्त, एक स्ट्रिंग w ऐसी उपस्तिथ है <math>u\equiv wb</math> और <math>v\equiv wa</math>. | ||
* प्रोजेक्शन नियम: स्ट्रिंग ऑपरेशंस#स्ट्रिंग_प्रोजेक्शन के | * प्रोजेक्शन नियम: स्ट्रिंग ऑपरेशंस#स्ट्रिंग_प्रोजेक्शन के अनुसार समतुल्यता बनाए रखी जाती है, जिससे कि यदि <math>w\equiv v</math>, तब <math>\pi_\Sigma(w)\equiv \pi_\Sigma(v)</math>. | ||
लेवी के लेम्मा का एक | लेवी के लेम्मा का एक शक्तिशाली रूप निशान रखता है। विशेष रूप से, यदि <math>uv\equiv xy</math> स्ट्रिंग्स के लिए u, v, x, y, तब स्ट्रिंग्स उपस्तिथ हैं <math>z_1, z_2, z_3</math> और <math>z_4</math> ऐसा है कि <math>(w_2, w_3)\in I_D</math> | ||
सभी पत्रों के लिए <math>w_2\in\Sigma</math> और <math>w_3\in\Sigma</math> ऐसा है कि <math>w_2</math> में होता है <math>z_2</math> और <math>w_3</math> में होता है <math>z_3</math>, और | सभी पत्रों के लिए <math>w_2\in\Sigma</math> और <math>w_3\in\Sigma</math> ऐसा है कि <math>w_2</math> में होता है <math>z_2</math> और <math>w_3</math> में होता है <math>z_3</math>, और | ||
| Line 49: | Line 50: | ||
:<math>x\equiv z_1z_3,\qquad y\equiv z_2z_4.</math><ref>Proposition 2.2, Diekert and Métivier 1997.</ref> | :<math>x\equiv z_1z_3,\qquad y\equiv z_2z_4.</math><ref>Proposition 2.2, Diekert and Métivier 1997.</ref> | ||
==सार्वभौमिक संपत्ति== | ==सार्वभौमिक संपत्ति== | ||
एक निर्भरता रूपवाद (निर्भरता ''डी'' के संबंध में) एक रूपवाद है | एक '''निर्भरता रूपवाद''' (निर्भरता ''डी'' के संबंध में) एक रूपवाद है | ||
:<math>\psi:\Sigma^*\to M</math> | :<math>\psi:\Sigma^*\to M</math> | ||
कुछ मोनॉइड एम के लिए, जैसे कि सामान्य ट्रेस गुण धारण करते हैं, अर्थात्: | कुछ मोनॉइड एम के लिए, जैसे कि सामान्य ट्रेस गुण धारण करते हैं, अर्थात्: | ||
| Line 56: | Line 57: | ||
:2. <math>(a,b)\in I_D</math> इसका आशय है <math>\psi(ab)=\psi(ba)</math> | :2. <math>(a,b)\in I_D</math> इसका आशय है <math>\psi(ab)=\psi(ba)</math> | ||
:3. <math>\psi(ua)=\psi(v)</math> इसका आशय है <math>\psi(u)=\psi(v\div a)</math> | :3. <math>\psi(ua)=\psi(v)</math> इसका आशय है <math>\psi(u)=\psi(v\div a)</math> | ||
:4. <math>\psi(ua)=\psi(vb)</math> और <math>a\ne b</math> इसका | :4. <math>\psi(ua)=\psi(vb)</math> और <math>a\ne b</math> इसका कारण यह है <math>(a,b)\in I_D</math> | ||
निर्भरता रूपवाद सार्वभौमिक हैं, इस अर्थ में कि किसी दिए गए, निश्चित निर्भरता डी के लिए, यदि <math>\psi:\Sigma^*\to M</math> एक मोनॉइड एम के लिए निर्भरता रूपवाद है, | निर्भरता रूपवाद सार्वभौमिक हैं, इस अर्थ में कि किसी दिए गए, निश्चित निर्भरता डी के लिए, यदि <math>\psi:\Sigma^*\to M</math> एक मोनॉइड एम के लिए निर्भरता रूपवाद है, तब एम ट्रेस मोनॉयड के लिए [[ समाकृतिकता |समाकृतिकता]] है <math>\mathbb{M}(D)</math>. विशेष रूप से, प्राकृतिक समरूपता एक निर्भरता रूपवाद है। | ||
==सामान्य रूप== | ==सामान्य रूप== | ||
ट्रेस मोनोइड्स में शब्दों के दो प्रसिद्ध सामान्य रूप हैं। एक एनाटोलिज वी. अनिसिमोव और [[डोनाल्ड नुथ]] के कारण [[ शब्दकोषीय क्रम ]] सामान्य रूप है, और दूसरा पियरे कार्टियर (गणितज्ञ) और डोमिनिक फोटा के कारण फोटा सामान्य रूप है, जिन्होंने 1960 के दशक में इसके [[ साहचर्य ]] के लिए ट्रेस मोनॉयड का अध्ययन किया था।<ref>Section 2.3, Diekert and Métivier 1997.</ref> | ट्रेस मोनोइड्स में शब्दों के दो प्रसिद्ध सामान्य रूप हैं। एक एनाटोलिज वी. अनिसिमोव और [[डोनाल्ड नुथ]] के कारण [[ शब्दकोषीय क्रम |शब्दकोषीय क्रम]] सामान्य रूप है, और दूसरा पियरे कार्टियर (गणितज्ञ) और डोमिनिक फोटा के कारण फोटा सामान्य रूप है, जिन्होंने 1960 के दशक में इसके [[ साहचर्य |साहचर्य]] के लिए ट्रेस मोनॉयड का अध्ययन किया था।<ref>Section 2.3, Diekert and Métivier 1997.</ref> | ||
यूनिकोड का यूनिकोड तुल्यता # सामान्य रूप (एनएफडी) एक लेक्सिकोग्राफ़िक सामान्य रूप का एक उदाहरण है - क्रम उस वर्ग द्वारा गैर-शून्य विहित संयोजन वर्ग के साथ लगातार वर्णों को क्रमबद्ध करना है। | यूनिकोड का यूनिकोड तुल्यता # सामान्य रूप (एनएफडी) एक लेक्सिकोग्राफ़िक सामान्य रूप का एक उदाहरण है - क्रम उस वर्ग द्वारा गैर-शून्य विहित संयोजन वर्ग के साथ लगातार वर्णों को क्रमबद्ध करना है। | ||
==भाषाओं का पता लगाएं== | ==भाषाओं का पता लगाएं== | ||
जिस प्रकार एक औपचारिक भाषा को एक उपसमुच्चय के रूप में माना जा सकता है <math>\Sigma^*</math>, सभी संभावित स्ट्रिंग्स का | जिस प्रकार एक औपचारिक भाषा को एक उपसमुच्चय के रूप में माना जा सकता है <math>\Sigma^*</math>, सभी संभावित स्ट्रिंग्स का समूह, इसलिए एक ट्रेस भाषा को सबसेट के रूप में परिभाषित किया गया है <math>\mathbb{M}(D)</math> सभी संभावित निशान. | ||
वैकल्पिक रूप से, | वैकल्पिक रूप से, किन्तु समकक्ष रूप से, एक भाषा <math>L\subseteq\Sigma^*</math> एक ट्रेस भाषा है, या इसे निर्भरता D के अनुरूप कहा जाता है यदि | ||
:<math>L = [L]_D</math> | :<math>L = [L]_D</math> | ||
| Line 73: | Line 74: | ||
:<math>[L]_D = \bigcup_{w \in L} [w]_D</math> | :<math>[L]_D = \bigcup_{w \in L} [w]_D</math> | ||
स्ट्रिंग्स के एक | स्ट्रिंग्स के एक समूह का ट्रेस क्लोजर है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
| Line 89: | Line 90: | ||
'''मौलिक प्रकाशन''' | '''मौलिक प्रकाशन''' | ||
* पियरे कार्टियर और डोमिनिक फोटा, प्रोब्लेम्स कॉम्बिनेटर्स डी कम्यूटेशन एट रीअरेंजमेंट्स, गणित में व्याख्यान नोट्स 85, स्प्रिंगर-वेरलाग, बर्लिन, 1969, [http://www.emis.de/journals/SLC/books/cartfoa.html Free 2006 reprint] नये परिशिष्टों के साथ | * पियरे कार्टियर और डोमिनिक फोटा, प्रोब्लेम्स कॉम्बिनेटर्स डी कम्यूटेशन एट रीअरेंजमेंट्स, गणित में व्याख्यान नोट्स 85, स्प्रिंगर-वेरलाग, बर्लिन, 1969, [http://www.emis.de/journals/SLC/books/cartfoa.html Free 2006 reprint] नये परिशिष्टों के साथ | ||
* एंटोनी माज़ुर्किविज़, समवर्ती कार्यक्रम योजनाएं और उनकी व्याख्याएं, DAIMI | * एंटोनी माज़ुर्किविज़, समवर्ती कार्यक्रम योजनाएं और उनकी व्याख्याएं, DAIMI सूची पीबी 78, आरहूस विश्वविद्यालय, 1977 | ||
[[Category: अर्धसमूह सिद्धांत]] [[Category: औपचारिक भाषाएँ]] [[Category: निःशुल्क बीजगणितीय संरचनाएँ]] [[Category: साहचर्य]] [[Category: ट्रेस सिद्धांत]] | [[Category: अर्धसमूह सिद्धांत]] [[Category: औपचारिक भाषाएँ]] [[Category: निःशुल्क बीजगणितीय संरचनाएँ]] [[Category: साहचर्य]] [[Category: ट्रेस सिद्धांत]] | ||
| Line 96: | Line 97: | ||
[[Category: Machine Translated Page]] | [[Category: Machine Translated Page]] | ||
[[Category:Created On 17/11/2023]] | [[Category:Created On 17/11/2023]] | ||
[[Category:Vigyan Ready]] | |||
Latest revision as of 09:56, 1 December 2023
कंप्यूटर विज्ञान में, ट्रेस औपचारिक भाषाओं का एक समूह है, जिसमें स्ट्रिंग में कुछ अक्षरों को क्रमविनिमेय संपत्ति की अनुमति है, किन्तु अन्य को नहीं। यह अक्षरों को सदैव एक निश्चित क्रम में रहने के लिए मजबूर न करके, किंतु कुछ फेरबदल करने की अनुमति देकर, एक स्ट्रिंग की अवधारणा को सामान्यीकृत करता है। मैकमोहन के मास्टर प्रमेय का संयुक्त प्रमाण देने के लिए 1969 में पियरे कार्टियर (गणितज्ञ) और डोमिनिक फोटा द्वारा ट्रेस प्रस्तुत किए गए थे। ट्रेस का उपयोग समानांतर कंप्यूटिंग के सिद्धांतों में किया जाता है, जहां कम्यूटिंग अक्षर किसी कार्य के कुछ हिस्सों को दर्शाते हैं जो एक दूसरे से स्वतंत्र रूप से निष्पादित हो सकते हैं, जबकि गैर-कम्यूटिंग अक्षर ताले, सिंक्रोनाइज़ेशन (कंप्यूटर विज्ञान) या थ्रेड (कंप्यूटिंग) के लिए होते हैं।[1]
ट्रेस मोनॉइड या मुक्त आंशिक रूप से क्रमविनिमेय मोनॉइड, ट्रेस का एक मोनॉइड है। संक्षेप में, इसका निर्माण इस प्रकार किया गया है: कम्यूटिंग अक्षरों के समूह एक निर्भरता संबंध द्वारा दिए गए हैं। यह समतुल्य तारों के समतुल्य संबंध को प्रेरित करते हैं; तुल्यता वर्गों के तत्व निशान हैं। तुल्यता संबंध तब मुक्त मोनॉइड (परिमित लंबाई के सभी तारों का समूह) को तुल्यता वर्गों के एक समूह में विभाजित करता है; परिणाम अभी भी एक मोनोइड है; यह एक अर्धसमूह है और इसे ट्रेस मोनॉइड कहा जाता है। ट्रेस मोनॉइड सार्वभौमिक संपत्ति है, जिसमें सभी निर्भरता-होमोमोर्फिक (नीचे देखें) मोनॉइड वास्तव में आइसोमोर्फिक हैं।
ट्रेस मोनोइड्स का उपयोग सामान्यतः समानांतर कंप्यूटिंग को मॉडल करने के लिए किया जाता है, जो प्रक्रिया कैलकुलस की नींव बनाता है। वह ट्रेस सिद्धांत में अध्ययन की वस्तु हैं। ट्रेस मोनोइड्स की उपयोगिता इस तथ्य से आती है कि वह निर्भरता ग्राफ के मोनोइड के समरूपी हैं; इस प्रकार बीजगणितीय विधि को ग्राफ़ (भिन्न गणित) पर प्रयुक्त करने की अनुमति मिलती है, और इसके विपरीत। वह इतिहास मोनोइड के समरूपी भी हैं, जो एक या अधिक कंप्यूटरों पर सभी निर्धारित प्रक्रियाओं के संदर्भ में व्यक्तिगत प्रक्रियाओं की गणना के इतिहास को मॉडल करते हैं।
ट्रेस
होने देना मुक्त मोनॉइड को निरूपित करें, अर्थात वर्णमाला में लिखे सभी तारों का समूह . यहां, तारांकन, सदैव की तरह, क्लेन स्टार को दर्शाता है। एक निर्भरता संबंध पर फिर एक (सममित) द्विआधारी संबंध उत्पन्न करता है पर , कहाँ यदि और केवल यदि अस्तित्व है , और एक जोड़ी ऐसा है कि और . यहाँ, और स्ट्रिंग्स (तत्वों) के रूप में समझा जाता है ), जबकि और अक्षर हैं (के तत्व) ).
ट्रेस को रिफ्लेक्सिव ट्रांजिटिव क्लोजर के रूप में परिभाषित किया गया है . इस प्रकार ट्रेस एक तुल्यता संबंध है , और द्वारा दर्शाया गया है , कहाँ के अनुरूप निर्भरता संबंध है