ट्रेस सिद्धांत

For trace theory in natural language syntax, see Trace (linguistics).

गणित और कंप्यूटर विज्ञान में, ग्राफ सिद्धांत का उद्देश्य समवर्ती संगणना और प्रक्रिया गणना के अध्ययन के लिए एक ठोस गणितीय आधार प्रदान करना है। अंडरपिनिंग मुक्त आंशिक रूप से कम्यूटेटिव मोनॉयड या ट्रेस मोनोइड की एक सार बीजगणित परिभाषा द्वारा प्रदान की जाती है, या समकक्ष, इतिहास मोनोइड, जो एक ठोस बीजगणितीय नींव प्रदान करता है, जिस तरह से मुक्त मोनोइड औपचारिक भाषाओं के लिए आधार प्रदान करता है।

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

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

संदर्भ

• Volker Diekert, Grzegorz Rozenberg, eds. The Book of Traces, (1995) World Scientific, Singapore ISBN 981-02-2058-8
• Volker Diekert, Yves Metivier, "Partial Commutation and Traces", In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Vol. 3, Beyond Words. Springer-Verlag, Berlin, 1997.
• Volker Diekert, Combinatorics on traces, LNCS 454, Springer, 1990, ISBN 3-540-53031-2