ट्रेस मोनॉयड

कंप्यूटर विज्ञान में, ट्रेस औपचारिक भाषाओं का एक समूह है, जिसमें स्ट्रिंग में कुछ अक्षरों को क्रमविनिमेय संपत्ति की अनुमति है, किन्तु अन्य को नहीं। यह अक्षरों को सदैव एक निश्चित क्रम में रहने के लिए मजबूर न करके, किंतु कुछ फेरबदल करने की अनुमति देकर, एक स्ट्रिंग की अवधारणा को सामान्यीकृत करता है। मैकमोहन के मास्टर प्रमेय का संयुक्त प्रमाण देने के लिए 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{array}{ccc}D& =& \{a,b\}\times <!--\; \times \; -->\{a,b\}\cup <!--\; \cup \; -->\{a,c\}\times <!--\; \times \; -->\{a,c\}\\ & =& {\{a,b\}}^2\cup <!--\; \cup \; -->{\{}^{}\end{array}$