ट्रेस मोनॉयड

कंप्यूटर विज्ञान में, ट्रेस औपचारिक भाषाओं का एक सेट है, जिसमें स्ट्रिंग में कुछ अक्षरों को क्रमविनिमेय संपत्ति की अनुमति है, लेकिन अन्य को नहीं। यह अक्षरों को हमेशा एक निश्चित क्रम में रहने के लिए मजबूर न करके, बल्कि कुछ फेरबदल करने की अनुमति देकर, एक स्ट्रिंग की अवधारणा को सामान्यीकृत करता है। मैकमोहन के मास्टर प्रमेय का संयुक्त प्रमाण देने के लिए 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\}$. एक संभावित निर्भरता संबंध है