ट्रेस मोनॉयड

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

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

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

ट्रेस

होने देना $\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 के लिए। इस प्रकार, ट्रेस मोनॉइड एक वाक्यात्मक मोनॉइड है।Template:Non-sequitur
• स्वतंत्रता: यदि $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}.$

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

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

$\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 के दशक में इसके साहचर्य ्स के लिए ट्रेस मोनॉयड का अध्ययन किया था। यूनिकोड का यूनिकोड तुल्यता # सामान्य रूप (एनएफडी) एक लेक्सिकोग्राफ़िक सामान्य रूप का एक उदाहरण है - क्रम उस वर्ग द्वारा गैर-शून्य विहित संयोजन वर्ग के साथ लगातार वर्णों को क्रमबद्ध करना है।

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

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

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

$L=[L]_{D}$

कहाँ

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

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

यह भी देखें

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

संदर्भ

General references

• Diekert, Volker; Métivier, Yves (1997), "Partial Commutation and Traces", in Rozenberg, G.; Salomaa, A. (eds.), Handbook of Formal Languages Vol. 3; Beyond Words, Springer-Verlag, Berlin, pp. 457–534, ISBN 3-540-60649-1
• Lothaire, M. (2011), Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 90, With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.), Cambridge University Press, 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
• Volker Diekert, Combinatorics on traces, LNCS 454, Springer, 1990, ISBN 3-540-53031-2, pp. 9–29
• Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, pp. 32–36, ISBN 1-4020-2546-7, 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, Free 2006 reprint with new appendixes
• Antoni Mazurkiewicz, Concurrent program schemes and their interpretations, DAIMI Report PB 78, Aarhus University, 1977