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

From Vigyanwiki
No edit summary
No edit summary
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>, को भागफल मोनोइड के रूप में परिभाषित किया गया है
Line 38: 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 के लिए। इस प्रकार, ट्रेस मोनॉइड एक वाक्यात्मक मोनॉइड है।
* एंबेडिंग: <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>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 50: 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 57: 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> इसका कारण यह है <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>. विशेष रूप से, प्राकृतिक समरूपता एक निर्भरता रूपवाद है।


==सामान्य रूप==
==सामान्य रूप==
ट्रेस मोनोइड्स में शब्दों के दो प्रसिद्ध सामान्य रूप हैं। एक एनाटोलिज वी. अनिसिमोव और [[डोनाल्ड नुथ]] के कारण [[ शब्दकोषीय क्रम ]] सामान्य रूप है, और दूसरा पियरे कार्टियर (गणितज्ञ) और डोमिनिक फोटा के कारण फोटा सामान्य रूप है, जिन्होंने 1960 के दशक में इसके [[ साहचर्य ]] के लिए ट्रेस मोनॉयड का अध्ययन किया था।<ref>Section 2.3, Diekert and Métivier 1997.</ref>
ट्रेस मोनोइड्स में शब्दों के दो प्रसिद्ध सामान्य रूप हैं। एक एनाटोलिज वी. अनिसिमोव और [[डोनाल्ड नुथ]] के कारण [[ शब्दकोषीय क्रम |शब्दकोषीय क्रम]] सामान्य रूप है, और दूसरा पियरे कार्टियर (गणितज्ञ) और डोमिनिक फोटा के कारण फोटा सामान्य रूप है, जिन्होंने 1960 के दशक में इसके [[ साहचर्य |साहचर्य]] के लिए ट्रेस मोनॉयड का अध्ययन किया था।<ref>Section 2.3, Diekert and Métivier 1997.</ref>


यूनिकोड का यूनिकोड तुल्यता # सामान्य रूप (एनएफडी) एक लेक्सिकोग्राफ़िक सामान्य रूप का एक उदाहरण है - क्रम उस वर्ग द्वारा गैर-शून्य विहित संयोजन वर्ग के साथ लगातार वर्णों को क्रमबद्ध करना है।
यूनिकोड का यूनिकोड तुल्यता # सामान्य रूप (एनएफडी) एक लेक्सिकोग्राफ़िक सामान्य रूप का एक उदाहरण है - क्रम उस वर्ग द्वारा गैर-शून्य विहित संयोजन वर्ग के साथ लगातार वर्णों को क्रमबद्ध करना है।
Line 68: Line 68:
जिस प्रकार एक औपचारिक भाषा को एक उपसमुच्चय के रूप में माना जा सकता है <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>
:<math>L = [L]_D</math>

Revision as of 11:04, 29 November 2023

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

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

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

ट्रेस

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

ट्रेस को रिफ्लेक्सिव ट्रांजिटिव क्लोजर के रूप में परिभाषित किया गया है . इस प्रकार ट्रेस एक तुल्यता संबंध है , और द्वारा दर्शाया गया है , कहाँ के अनुरूप निर्भरता संबंध है वह है और इसके विपरीत प्रकट है, भिन्न-भिन्न निर्भरताएं भिन्न-भिन्न तुल्यता संबंध देंगी।

सकर्मक समापन का तात्पर्य यह है यदि और केवल यदि स्ट्रिंग्स का एक क्रम उपस्तिथ है ऐसा है कि