ट्रेस मोनॉयड: Difference between revisions

Latest revision as of 09:56, 1 December 2023

कंप्यूटर विज्ञान में, ट्रेस औपचारिक भाषाओं का एक समूह है, जिसमें स्ट्रिंग में कुछ अक्षरों को क्रमविनिमेय संपत्ति की अनुमति है, किन्तु अन्य को नहीं। यह अक्षरों को सदैव एक निश्चित क्रम में रहने के लिए मजबूर न करके, किंतु कुछ फेरबदल करने की अनुमति देकर, एक स्ट्रिंग की अवधारणा को सामान्यीकृत करता है। मैकमोहन के मास्टर प्रमेय का संयुक्त प्रमाण देने के लिए 1969 में पियरे कार्टियर (गणितज्ञ) और डोमिनिक फोटा द्वारा ट्रेस प्रस्तुत किए गए थे। ट्रेस का उपयोग समानांतर कंप्यूटिंग के सिद्धांतों में किया जाता है, जहां कम्यूटिंग अक्षर किसी कार्य के कुछ हिस्सों को दर्शाते हैं जो एक दूसरे से स्वतंत्र रूप से निष्पादित हो सकते हैं, जबकि गैर-कम्यूटिंग अक्षर ताले, सिंक्रोनाइज़ेशन (कंप्यूटर विज्ञान) या थ्रेड (कंप्यूटिंग) के लिए होते हैं।^[1]

ट्रेस मोनॉइड या मुक्त आंशिक रूप से क्रमविनिमेय मोनॉइड, ट्रेस का एक मोनॉइड है। संक्षेप में, इसका निर्माण इस प्रकार किया गया है: कम्यूटिंग अक्षरों के समूह एक निर्भरता संबंध द्वारा दिए गए हैं। यह समतुल्य तारों के समतुल्य संबंध को प्रेरित करते हैं; तुल्यता वर्गों के तत्व निशान हैं। तुल्यता संबंध तब मुक्त मोनॉइड (परिमित लंबाई के सभी तारों का समूह) को तुल्यता वर्गों के एक समूह में विभाजित करता है; परिणाम अभी भी एक मोनोइड है; यह एक अर्धसमूह है और इसे ट्रेस मोनॉइड कहा जाता है। ट्रेस मोनॉइड सार्वभौमिक संपत्ति है, जिसमें सभी निर्भरता-होमोमोर्फिक (नीचे देखें) मोनॉइड वास्तव में आइसोमोर्फिक हैं।

ट्रेस मोनोइड्स का उपयोग सामान्यतः समानांतर कंप्यूटिंग को मॉडल करने के लिए किया जाता है, जो प्रक्रिया कैलकुलस की नींव बनाता है। वह ट्रेस सिद्धांत में अध्ययन की वस्तु हैं। ट्रेस मोनोइड्स की उपयोगिता इस तथ्य से आती है कि वह निर्भरता ग्राफ के मोनोइड के समरूपी हैं; इस प्रकार बीजगणितीय विधि को ग्राफ़ (भिन्न गणित) पर प्रयुक्त करने की अनुमति मिलती है, और इसके विपरीत। वह इतिहास मोनोइड के समरूपी भी हैं, जो एक या अधिक कंप्यूटरों पर सभी निर्धारित प्रक्रियाओं के संदर्भ में व्यक्तिगत प्रक्रियाओं की गणना के इतिहास को मॉडल करते हैं।

ट्रेस

होने देना $\Sigma ^{*}$ मुक्त मोनॉइड को निरूपित करें, अर्थात वर्णमाला में लिखे सभी तारों का समूह $\Sigma$ . यहां, तारांकन, सदैव की तरह, क्लेन स्टार को दर्शाता है। एक निर्भरता संबंध $I$ पर $\Sigma$ फिर एक (सममित) द्विआधारी संबंध उत्पन्न करता है $\sim$ पर $\Sigma ^{*}$ , कहाँ $u\sim v$ यदि और केवल यदि अस्तित्व है $x,y\in \Sigma ^{*}$ , और एक जोड़ी $(a,b)\in I$ ऐसा है कि $u=xaby$ और $v=xbay$ . यहाँ, $u,v,x$ और $y$ स्ट्रिंग्स (तत्वों) के रूप में समझा जाता है $\Sigma ^{*}$ ), जबकि $a$ और $b$ अक्षर हैं (के तत्व) $\Sigma$ ).

ट्रेस को रिफ्लेक्सिव ट्रांजिटिव क्लोजर के रूप में परिभाषित किया गया है $\sim$ . इस प्रकार ट्रेस एक तुल्यता संबंध है $\Sigma ^{*}$ , और द्वारा दर्शाया गया है $\equiv _{D}$ , कहाँ $D$ के अनुरूप निर्भरता संबंध है $I,$ वह है $D=(\Sigma \times \Sigma )\setminus I$ और इसके विपरीत $I=(\Sigma \times \Sigma )\setminus D.$ प्रकट है, भिन्न-भिन्न निर्भरताएं भिन्न-भिन्न तुल्यता संबंध देंगी।

सकर्मक समापन का तात्पर्य यह है $u\equiv v$ यदि और केवल यदि स्ट्रिंग्स का एक क्रम उपस्तिथ है $(w_{0},w_{1},\cdots ,w_{n})$ ऐसा है कि $u\sim w_{0}$ और $v\sim w_{n}$ और $w_{i}\sim w_{i+1}$ सभी के लिए $0\leq i<n$ . मोनोइड ऑपरेशन के अनुसार ट्रेस स्थिर है $\Sigma ^{*}$ (संयोजन) और इसलिए यह एक सर्वांगसम संबंध है $\Sigma ^{*}$ .

ट्रेस मोनॉइड, जिसे सामान्यतः इस रूप में दर्शाया जाता है $\mathbb {M} (D)$ , को भागफल मोनोइड के रूप में परिभाषित किया गया है

\mathbb {M} (D)=\Sigma ^{*}/\equiv _{D}.

समरूपता

\phi _{D}:\Sigma ^{*}\to \mathbb {M} (D)

इसे सामान्यतः प्राकृतिक परिवर्तन या विहित समरूपता के रूप में जाना जाता है। प्राकृतिक या विहित शब्द योग्य हैं, यह इस तथ्य से पता चलता है कि यह रूपवाद एक सार्वभौमिक संपत्ति का प्रतीक है, जैसा कि पश्चात् के अनुभाग में चर्चा की गई है।

किसी को ट्रेस मोनॉयड भी मिलेगा जिसे इस रूप में दर्शाया गया है $M(\Sigma ,I)$ कहाँ $I$ स्वतंत्रता संबंध है. भ्रामक रूप से, कोई व्यक्ति स्वतंत्रता संबंध के अतिरिक्त उपयोग किए गए कम्यूटेशन संबंध को भी पा सकता है (यह सभी विकर्ण तत्वों को सम्मिलित करके भिन्न होता है)।

उदाहरण

वर्णमाला पर विचार करें $\Sigma =\{a,b,c\}$ . एक संभावित निर्भरता संबंध है

{\begin{matrix}D&=&\{a,b\}\times \{a,b\}\quad \cup \quad \{a,c\}\times \{a,c\}\\&=&\{a,b\}^{2}\cup \{a,c\}^{2}\\&=&\{(a,b),(b,a),(a,c),(c,a),(a,a),(b,b),(c,c)\}\end{matrix}}

तत्संबंधी स्वतंत्रता है

I_{D}=\{(b,c)\,,\,(c,b)\}

इसलिए, पत्र $b,c$ आना-जाना। इस प्रकार, उदाहरण के लिए, स्ट्रिंग के लिए एक ट्रेस तुल्यता वर्ग $abababbca$ होगा

[abababbca]_{D}=\{abababbca\,,\;abababcba\,,\;ababacbba\}

तुल्यता वर्ग $[abababbca]_{D}$ ट्रेस मोनॉइड का एक तत्व है।

गुण

रद्दीकरण संपत्ति बताती है कि स्ट्रिंग ऑपरेशन के अनुसार समतुल्यता बनाए रखी जाती है। अर्थात यदि $w\equiv v$ , तब $(w\div a)\equiv (v\div a)$ . यहाँ, संकेतन $w\div a$ दाएँ रद्दीकरण को दर्शाता है, दाहिनी ओर से प्रारंभ होने वाली स्ट्रिंग w से अक्षर a की पहली घटना को हटाना। वाम-निरस्तीकरण से भी समतुल्यता बनी रहती है। अनेक परिणाम इस प्रकार हैं:

एंबेडिंग: $w\equiv v$ यदि और केवल यदि $xwy\equiv xvy$ स्ट्रिंग्स x और y के लिए। इस प्रकार, ट्रेस मोनॉइड एक वाक्यात्मक मोनॉइड है।
स्वतंत्रता: यदि $ua\equiv vb$ और $a\neq b$ , तब a, b से स्वतंत्र है। वह है, $(a,b)\in I_{D}$ . इसके अतिरिक्त, एक स्ट्रिंग w ऐसी उपस्तिथ है $u\equiv wb$ और $v\equiv wa$ .
प्रोजेक्शन नियम: स्ट्रिंग ऑपरेशंस#स्ट्रिंग_प्रोजेक्शन के अनुसार समतुल्यता बनाए रखी जाती है, जिससे कि यदि $w\equiv v$ , तब $\pi _{\Sigma }(w)\equiv \pi _{\Sigma }(v)$ .

लेवी के लेम्मा का एक शक्तिशाली रूप निशान रखता है। विशेष रूप से, यदि $uv\equiv xy$ स्ट्रिंग्स के लिए u, v, x, y, तब स्ट्रिंग्स उपस्तिथ हैं $z_{1},z_{2},z_{3}$ और $z_{4}$ ऐसा है कि $(w_{2},w_{3})\in I_{D}$ सभी पत्रों के लिए $w_{2}\in \Sigma$ और $w_{3}\in \Sigma$ ऐसा है कि $w_{2}$ में होता है $z_{2}$ और $w_{3}$ में होता है $z_{3}$ , और

u\equiv z_{1}z_{2},\qquad v\equiv z_{3}z_{4},

x\equiv z_{1}z_{3},\qquad y\equiv z_{2}z_{4}.

^[2]

सार्वभौमिक संपत्ति

एक निर्भरता रूपवाद (निर्भरता डी के संबंध में) एक रूपवाद है

\psi :\Sigma ^{*}\to M

कुछ मोनॉइड एम के लिए, जैसे कि सामान्य ट्रेस गुण धारण करते हैं, अर्थात्:

1.

\psi (w)=\psi (\varepsilon )

इसका आशय है

w=\varepsilon

2.

(a,b)\in I_{D}

इसका आशय है

\psi (ab)=\psi (ba)

3.

\psi (ua)=\psi (v)

इसका आशय है

\psi (u)=\psi (v\div a)

4.

\psi (ua)=\psi (vb)

और

a\neq b

इसका कारण यह है

(a,b)\in I_{D}

निर्भरता रूपवाद सार्वभौमिक हैं, इस अर्थ में कि किसी दिए गए, निश्चित निर्भरता डी के लिए, यदि $\psi :\Sigma ^{*}\to M$ एक मोनॉइड एम के लिए निर्भरता रूपवाद है, तब एम ट्रेस मोनॉयड के लिए समाकृतिकता है $\mathbb {M} (D)$ . विशेष रूप से, प्राकृतिक समरूपता एक निर्भरता रूपवाद है।

सामान्य रूप

ट्रेस मोनोइड्स में शब्दों के दो प्रसिद्ध सामान्य रूप हैं। एक एनाटोलिज वी. अनिसिमोव और डोनाल्ड नुथ के कारण शब्दकोषीय क्रम सामान्य रूप है, और दूसरा पियरे कार्टियर (गणितज्ञ) और डोमिनिक फोटा के कारण फोटा सामान्य रूप है, जिन्होंने 1960 के दशक में इसके साहचर्य के लिए ट्रेस मोनॉयड का अध्ययन किया था।^[3]

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

भाषाओं का पता लगाएं

जिस प्रकार एक औपचारिक भाषा को एक उपसमुच्चय के रूप में माना जा सकता है $\Sigma ^{*}$ , सभी संभावित स्ट्रिंग्स का समूह, इसलिए एक ट्रेस भाषा को सबसेट के रूप में परिभाषित किया गया है $\mathbb {M} (D)$ सभी संभावित निशान.

वैकल्पिक रूप से, किन्तु समकक्ष रूप से, एक भाषा $L\subseteq \Sigma ^{*}$ एक ट्रेस भाषा है, या इसे निर्भरता D के अनुरूप कहा जाता है यदि

L=[L]_{D}

कहाँ

[L]_{D}=\bigcup _{w\in L}[w]_{D}

स्ट्रिंग्स के एक समूह का ट्रेस क्लोजर है।

यह भी देखें

कैश का पता लगाएं

संदर्भ

सामान्य सन्दर्भ

डाइकर्ट, वोल्कर; मेटिविएर, Yves (1997), "आंशिक रूपान्तरण और निशान", in रोज़ेनबर्ग, G.; सलोमा, A. (eds.), औपचारिक भाषाओं की पुस्तिका खंड। 3; शब्दों से परे, स्प्रिंगर-वेरलाग, बर्लिन, pp. 457–534, ISBN 3-540-60649-1
Lothaire, M. (2011), शब्दों पर बीजगणितीय संयोजन विज्ञान, गणित और उसके अनुप्रयोगों का विश्वकोश, vol. 90, जीन बर्स्टेल और डोमिनिक पेरिन द्वारा प्रस्तावना के साथ (2002 हार्डबैक का पुनर्मुद्रण ed.), कैम्ब्रिज यूनिवर्सिटी प्रेस, ISBN 978-0-521-18071-9, Zbl 1221.68183
एंटोनी माज़ुरकिविज़, "इंट्रोडक्शन टू ट्रेस थ्योरी", पीपी 3-41, द बुक ऑफ़ ट्रेसेस में, वी. डाइकर्ट, जी. रोज़ेनबर्ग, संस्करण। (1995) विश्व वैज्ञानिक, सिंगापुर ISBN 981-02-2058-8
वोल्कर डाइकर्ट, कॉम्बिनेटरिक्स ऑन ट्रेसेस, LNCS 454, Springer, 1990, ISBN 3-540-53031-2, pp. 9–29
सांडोर, जोज़सेफ; क्रिस्टिसी, बोरिस्लाव (2004), संख्या सिद्धांत II की पुस्तिका, डॉर्ड्रेक्ट: क्लूवर अकादमिक, pp. 32–36, ISBN 1-4020-2546-7, Zbl 1079.11001

मौलिक प्रकाशन

पियरे कार्टियर और डोमिनिक फोटा, प्रोब्लेम्स कॉम्बिनेटर्स डी कम्यूटेशन एट रीअरेंजमेंट्स, गणित में व्याख्यान नोट्स 85, स्प्रिंगर-वेरलाग, बर्लिन, 1969, Free 2006 reprint नये परिशिष्टों के साथ
एंटोनी माज़ुर्किविज़, समवर्ती कार्यक्रम योजनाएं और उनकी व्याख्याएं, DAIMI सूची पीबी 78, आरहूस विश्वविद्यालय, 1977

[CS161-1] Sándor & Crstici (2004) p.161

[2] Proposition 2.2, Diekert and Métivier 1997.

[3] Section 2.3, Diekert and Métivier 1997.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-{{Short description|Generalization of strings in computer science}}[[कंप्यूटर विज्ञान]] में, ट्रेस [[औपचारिक भाषा]]ओं का एक सेट है, जिसमें स्ट्रिंग में कुछ अक्षरों को क्रमविनिमेय संपत्ति की अनुमति है, लेकिन अन्य को नहीं। यह अक्षरों को हमेशा एक निश्चित क्रम में रहने के लिए मजबूर न करके, बल्कि कुछ फेरबदल करने की अनुमति देकर, एक स्ट्रिंग की अवधारणा को सामान्यीकृत करता है। मैकमोहन के मास्टर प्रमेय का संयुक्त प्रमाण देने के लिए 1969 में [[पियरे कार्टियर (गणितज्ञ)]] और [[डोमिनिक फोटा]] द्वारा ट्रेस पेश किए गए थे। ट्रेस का उपयोग [[समानांतर कंप्यूटिंग]] के सिद्धांतों में किया जाता है, जहां कम्यूटिंग अक्षर किसी कार्य के कुछ हिस्सों को दर्शाते हैं जो एक दूसरे से स्वतंत्र रूप से निष्पादित हो सकते हैं, जबकि गैर-कम्यूटिंग अक्षर ताले, सिंक्रोनाइज़ेशन (कंप्यूटर विज्ञान) या [[थ्रेड (कंप्यूटिंग)]] के लिए होते हैं।<ref name="CS161">Sándor & Crstici (2004) p.161</ref>
+{{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>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>\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>(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>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)</math>, को भागफल मोनोइड के रूप में परिभाषित किया गया है
 :<math>\mathbb {M}(D) = \Sigma^* / \equiv_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\div a)\equiv (v\div a)</math>. यहाँ, संकेतन <math>w\div a</math> दाएँ रद्दीकरण को दर्शाता है, दाहिनी ओर से प्रारंभ होने वाली स्ट्रिंग w से अक्षर a की पहली घटना को हटाना। वाम-निरस्तीकरण से भी समतुल्यता बनी रहती है। अनेक परिणाम इस प्रकार हैं:
-* एंबेडिंग: <math>w \equiv v</math> अगर और केवल अगर <math>xwy\equiv xvy</math> स्ट्रिंग्स x और y के लिए। इस प्रकार, ट्रेस मोनॉइड एक वाक्यात्मक मोनॉइड है।{{Non-sequitur|post-text=See [[Talk:Trace monoid#As Syntactic Monoids]]|date=April 2022}}
+* एंबेडिंग: <math>w \equiv v</math> यदि और केवल यदि <math>xwy\equiv xvy</math> स्ट्रिंग्स x और y के लिए। इस प्रकार, ट्रेस मोनॉइड एक वाक्यात्मक मोनॉइड है।
-*स्वतंत्रता: यदि <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>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>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>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>u\equiv z_1z_2,\qquad v\equiv z_3z_4,</math>
 :<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>
 कुछ मोनॉइड एम के लिए, जैसे कि सामान्य ट्रेस गुण धारण करते हैं, अर्थात्:
@@ Line 58: / Line 57: @@
 :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>
-:4. <math>\psi(ua)=\psi(vb)</math> और <math>a\ne b</math> इसका मतलब यह है  <math>(a,b)\in I_D</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>\mathbb{M}(D)</math>. विशेष रूप से, प्राकृतिक समरूपता एक निर्भरता रूपवाद है।
+निर्भरता रूपवाद सार्वभौमिक हैं, इस अर्थ में कि किसी दिए गए, निश्चित निर्भरता डी के लिए, यदि <math>\psi:\Sigma^*\to M</math> एक मोनॉइड एम के लिए निर्भरता रूपवाद है, तब एम ट्रेस मोनॉयड के लिए [[ समाकृतिकता |समाकृतिकता]] है <math>\mathbb{M}(D)</math>. विशेष रूप से, प्राकृतिक समरूपता एक निर्भरता रूपवाद है।
 ==सामान्य रूप==
-{{Expand section|date=December 2009}}
+ट्रेस मोनोइड्स में शब्दों के दो प्रसिद्ध सामान्य रूप हैं। एक एनाटोलिज वी. अनिसिमोव और [[डोनाल्ड नुथ]] के कारण [[ शब्दकोषीय क्रम |शब्दकोषीय क्रम]] सामान्य रूप है, और दूसरा पियरे कार्टियर (गणितज्ञ) और डोमिनिक फोटा के कारण फोटा सामान्य रूप है, जिन्होंने 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>\mathbb{M}(D)</math> सभी संभावित निशान.
+जिस प्रकार एक औपचारिक भाषा को एक उपसमुच्चय के रूप में माना जा सकता है <math>\Sigma^*</math>, सभी संभावित स्ट्रिंग्स का समूह, इसलिए एक ट्रेस भाषा को सबसेट के रूप में परिभाषित किया गया है <math>\mathbb{M}(D)</math> सभी संभावित निशान.
-वैकल्पिक रूप से, लेकिन समकक्ष रूप से, एक भाषा <math>L\subseteq\Sigma^*</math> एक ट्रेस भाषा है, या कहा जाता है कि यह निर्भरता ''डी'' के अनुरूप है
+वैकल्पिक रूप से, किन्तु समकक्ष रूप से, एक भाषा <math>L\subseteq\Sigma^*</math> एक ट्रेस भाषा है, या इसे निर्भरता D के अनुरूप कहा जाता है यदि
 :<math>L = [L]_D</math>
@@ Line 76: / Line 74: @@
 :<math>[L]_D = \bigcup_{w \in L} [w]_D</math>
-स्ट्रिंग्स के एक सेट का ट्रेस क्लोजर है।
+स्ट्रिंग्स के एक समूह का ट्रेस क्लोजर है।
 ==यह भी देखें==
@@ Line 83: / Line 81: @@
 ==टिप्पणियाँ==
 {{reflist}}
 ==संदर्भ==
-'''General references'''
+'''सामान्य सन्दर्भ'''
-*{{Citation | editor-first=G. | editor-last=Rozenberg | editor2-first=A. | editor2-last=Salomaa | last = Diekert | first = Volker | last2 = Métivier | first2 = Yves | title = Handbook of Formal Languages Vol. 3; Beyond Words | publisher = Springer-Verlag, Berlin | year = 1997 | chapter=Partial Commutation and Traces | chapter-url= http://citeseer.ist.psu.edu/diekert97partial.html | pages = 457–534 | isbn = 3-540-60649-1}}
+*{{Citation | editor-first=G. | editor-last=रोज़ेनबर्ग | editor2-first=A. | editor2-last=सलोमा | last = डाइकर्ट | first = वोल्कर | last2 = मेटिविएर | first2 = Yves | title = औपचारिक भाषाओं की पुस्तिका खंड। 3; शब्दों से परे | publisher = स्प्रिंगर-वेरलाग, बर्लिन | year = 1997 | chapter=आंशिक रूपान्तरण और निशान | chapter-url= http://citeseer.ist.psu.edu/diekert97partial.html | pages = 457–534 | isbn = 3-540-60649-1}}
-* {{citation | last=Lothaire | first=M. | author-link=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
+* {{citation | last=Lothaire | first=M. | author-link=एम. लोथायर | title=शब्दों पर बीजगणितीय संयोजन विज्ञान | others=जीन बर्स्टेल और डोमिनिक पेरिन द्वारा प्रस्तावना के साथ | edition=2002 हार्डबैक का पुनर्मुद्रण | series=गणित और उसके अनुप्रयोगों का विश्वकोश | volume=90| publisher=कैम्ब्रिज यूनिवर्सिटी प्रेस | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
-* Antoni Mazurkiewicz, "Introduction to Trace Theory", pp 3–41, in ''The Book of Traces'', V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapore {{isbn|981-02-2058-8}}
+* एंटोनी माज़ुरकिविज़, "इंट्रोडक्शन टू ट्रेस थ्योरी", पीपी 3-41, द बुक ऑफ़ ट्रेसेस में, वी. डाइकर्ट, जी. रोज़ेनबर्ग, संस्करण। (1995) विश्व वैज्ञानिक, सिंगापुर {{isbn|981-02-2058-8}}
-* Volker Diekert, ''Combinatorics on traces'', [[Lecture Notes in Computer Science|LNCS]] 454, Springer, 1990, {{isbn|3-540-53031-2}}, pp.&nbsp;9–29
+* वोल्कर डाइकर्ट, कॉम्बिनेटरिक्स ऑन ट्रेसेस, [[Lecture Notes in Computer Science|LNCS]] 454, Springer, 1990, {{isbn|3-540-53031-2}}, pp.&nbsp;9–29
-* {{citation | last1=Sándor | first1=Jozsef | last2=Crstici | first2=Borislav | title=Handbook of number theory II | location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=1-4020-2546-7 | pages=32–36 | zbl=1079.11001 }}
+* {{citation | last1=सांडोर | first1=जोज़सेफ | last2=क्रिस्टिसी | first2=बोरिस्लाव | title=संख्या सिद्धांत II की पुस्तिका | location=डॉर्ड्रेक्ट | publisher=क्लूवर अकादमिक | year=2004 | isbn=1-4020-2546-7 | pages=32–36 | zbl=1079.11001 }}
-'''Seminal publications'''
+'''मौलिक प्रकाशन'''
-* Pierre Cartier and Dominique Foata, ''Problèmes combinatoires de commutation et réarrangements'', Lecture Notes in Mathematics 85, Springer-Verlag, Berlin, 1969, [http://www.emis.de/journals/SLC/books/cartfoa.html Free 2006 reprint] with new appendixes
+* पियरे कार्टियर और डोमिनिक फोटा, प्रोब्लेम्स कॉम्बिनेटर्स डी कम्यूटेशन एट रीअरेंजमेंट्स, गणित में व्याख्यान नोट्स 85, स्प्रिंगर-वेरलाग, बर्लिन, 1969, [http://www.emis.de/journals/SLC/books/cartfoa.html Free 2006 reprint] नये परिशिष्टों के साथ
-* Antoni Mazurkiewicz, ''Concurrent program schemes and their interpretations'', DAIMI Report PB 78, Aarhus University, 1977
+* एंटोनी माज़ुर्किविज़, समवर्ती कार्यक्रम योजनाएं और उनकी व्याख्याएं, DAIMI सूची पीबी 78, आरहूस विश्वविद्यालय, 1977
 [[Category: अर्धसमूह सिद्धांत]] [[Category: औपचारिक भाषाएँ]] [[Category: निःशुल्क बीजगणितीय संरचनाएँ]] [[Category: साहचर्य]] [[Category: ट्रेस सिद्धांत]]
@@ Line 101: / Line 97: @@
 [[Category: Machine Translated Page]]
 [[Category:Created On 17/11/2023]]
+[[Category:Vigyan Ready]]

Anonymous

Search

ट्रेस मोनॉयड: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:56, 1 December 2023

Contents

ट्रेस

उदाहरण

गुण

सार्वभौमिक संपत्ति

सामान्य रूप

भाषाओं का पता लगाएं

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ट्रेस मोनॉयड: Difference between revisions

Latest revision as of 09:56, 1 December 2023

ट्रेस

उदाहरण

गुण

सार्वभौमिक संपत्ति

सामान्य रूप

भाषाओं का पता लगाएं

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories