प्रपांतरण अर्धसमूह
बीजगणित में, रूपांतरण अर्धसमूह या संघटन अर्धसमूह परिवर्तन (फ़ंक्शन गणित एक संग्रह से स्वयं) का एक संग्रह है जो फ़ंक्शन संरचना के तहत क्लोजर गणित है। यदि इसमें पहचान कार्य शामिल है, तो यह एक मोनोइड है, जिसे एक परिवर्तन या रचना मोनोइड कहा जाता है। यह क्रमपरिवर्तन समूह का अर्धसमूह एनालॉग है।
संग्रह के परिवर्तन अर्धसमूह में एक टॉटोलॉजिकल अर्धसमूह क्रिया होती है। इस तरह के कार्यों मे यथातथ्य होने की विशेषता होती है, अर्थात, यदि अर्धसमूह के दो तत्वों में समान क्रिया होती है, तो वे समान होते हैं।
केली प्रमेय के एक एनालॉग से पता चलता है कि किसी भी अर्धसमूह के कुछ संग्रह के रूपांतरण को अर्धसमूह के रूप में संवेदन किया जा सकता है।
ऑटोमेटा सिद्धांत में, कुछ लेखक अर्धसमूह के आधार संग्रह से अलग संग्रह की एक स्थिति पर अर्धसमूह क्रिया को संदर्भित करने के लिए 'परिवर्तन अर्धसमूह' शब्द का उपयोग करते हैं।[1] दो धारणाओं के बीच एक पत्राचार है।
परिवर्तन सेमिग्रुप्स और मोनोइड्स
परिवर्तन अर्धसमूह एक जोड़ी X,S है, जहाँ X एक संग्रह है और SX परिवर्तन का अर्धसमूह है। यहाँ X का रूपांतरण X के उपसमुच्चय से X तक केवल एक फ़ंक्शन (गणित) है, जरूरी नहीं कि उलटा हो, और इसलिए S केवल परिवर्तनों का एक संग्रह है X जो कार्यों की संरचना के अंतर्गत क्लोजर (गणित) है। किसी दिए गए आधार संग्रह X पर सभी आंशिक कार्यों का संग्रह, एक नियमित अर्धसमूह बनाता है जिसे सभी आंशिक परिवर्तनों का अर्धसमूह कहा जाता है (या X पर आंशिक परिवर्तन अर्धसमूह), जिसे आमतौर पर निरूपित किया जाता है .[2] अगर SX (S में X का आइडेंटिटी परिवर्तनों शामिल है, तो इसे 'परिवर्तनों मोनोइड' कहा जाता है। स्पष्ट रूप से कोई भी परिवर्तन अर्धसमूह S पहचान परिवर्तन के साथ S के संघ को ले कर एक परिवर्तन मोनोइड M निर्धारित करता है। एक परिवर्तन मोनोइड जिसका तत्व उलटा हो सकता है एक क्रमचय समूह है।
X के सभी परिवर्तनों का समुच्चय एक रूपांतरण मोनोइड है जिसे X का 'पूर्ण परिवर्तन मोनोइड' (या 'अर्धसमूह') कहा जाता है। इसे X का 'सममित अर्धसमूह' भी कहा जाता है और इसे टी (T) द्वारा दर्शाया जाता है।X. इस प्रकार एक रूपांतरण उपार्ध समूह (या मोनोइड) X के पूर्ण परिवर्तन मोनोइड का सिर्फ एक उपसमूह (या सबमोनोइड़) है।
यदि X, S (X =T) एक रूपांतरण अर्धसमूह है तो X को मूल्यांकन द्वारा S (S)की एक अर्धसमूह कार्रवाई में बनाया जा सकता है:
यह एक मोनोइड क्रिया है यदि S एक रूपांतरण मोनोइड है।
क्रियाओं के रूप में परिवर्तन अर्धसमूहों की विशेषता यह है कि वे कर्त्तव्यनिष्ठ हैं, अर्थात, यदि
फिर S = टी (T)। विलोमतः यदि एक अर्धसमूह S समुच्चय X पर टी (T) SX (s,x) = s • x द्वारा कार्य करता है तो हम s ∈ S के लिए एक परिवर्तन टी (T) को परिभाषित कर सकते हैंs X द्वारा
TS (Ts) को S भेजने वाला नक्शा इंजेक्शन है तो (X, टी (X,T) कर्त्तव्यनिष्ठ है, इस मामले में इस मानचित्र की छवि S परिवर्तन अर्धसमूह आइसोमोर्फिक है।
केली प्रतिनिधित्व
समूह सिद्धांत में, केली के प्रमेय का दावा है कि कोई भी समूह जी (G) के सममित समूह (एक सेट के रूप में माना जाता है) के एक उपसमूह के लिए समरुप है, ताकि जी (G) एक क्रमचय समूह मे रहे। यह प्रमेय सीधे तौर पर मोनोइड्स के लिए सामान्यीकृत होता है, कोई भी मोनोइड M मे अंतर्निहित संग्रह का एक रूपांतरण मोनोइड है, जो बाएं (या दाएं) गुणन द्वारा दी गई क्रिया के माध्यम से होता है। यह क्रिया सत्य है क्योंकि यदि M में सभी x के लिए ax = bx है, तो x को सर्वसमिका अवयव के बराबर लेने पर, हमें a = b प्राप्त होता है।
(बाएं या दाएं) पहचान तत्व के बिना एक अर्धसमूह Sके लिए, हम X को मोनॉयड # उदाहरण के अंतर्निहित संग्रह के रूप में लेते हैं ताकि Sको X के रूपांतरण अर्धसमूह के रूप में संवेदन किया जा सके। विशेष रूप से किसी भी परिमित अर्धसमूह को परिवर्तनों के उप-समूह के रूप में दर्शाया जा सकता है एक संग्रह X के साथ | X | ≤ |S| + 1, और यदि S एक मोनोइड है, तो हमारे पास शार्प बाउंड |X| है ≤ |S|, जैसा परिमित समूह के मामले में है।[3]: 21
कंप्यूटर विज्ञान
कंप्यूटर विज्ञान में, केली के अभ्यावेदन को कई रचित गुणन मे पुन: संबद्ध करके अर्धसमूह की स्पर्शोन्मुख दक्षता में सुधार करने के लिए लागू किया जा सकता है। बाएं गुणन द्वारा दी गई क्रिया का परिणाम दाएं-संबद्ध गुणन में होता है, और इसके विपरीत सही गुणन द्वारा दी गई क्रिया के लिए किसी भी अर्धसमूह के लिए समान परिणाम होने के बावजूद, स्पर्शोन्मुख दक्षता भिन्न होती है। बाएं गुणन की एक क्रिया द्वारा दिए गए उपयोगी परिवर्तन मोनोइड्स के दो उदाहरण अंतर सूची डेटा संरचना के कार्यात्मक रूपांतर हैं, और मोनैडिक घनत्व परिवर्तन (मोनैड का एक केली प्रतिनिधित्व, जो एक विशेष मोनोइडल फ़ंक्टर श्रेणी में एक मोनोइड है)।[4]
एक ऑटोमेटन का परिवर्तन मोनोइड
M को राज्य स्थान S और वर्णमाला ए (A) के साथ एक निर्धारक ऑटोमेटन होने दें। मुक्त मोनोइड A∗ में शब्द S के परिवर्तनों को प्रेरित करते हैं जो A∗ से पूर्ण परिवर्तन मोनोइड TS तक एक मोनोइड आकारिकी को उत्पत्ति देते हैं। इस आकारिकी की छवि M का परिवर्तन अर्धसमूह है।
नियमित भाषा के लिए, सिंटैक्टिक मोनॉयड भाषा के न्यूनतम ऑटोमेटन के परिवर्तन मोनोइड के लिए समरूप है। [3]
यह भी देखें
- अर्धस्वचालित
- क्रोहन-रोड्स सिद्धांत
- सममित उलटा अर्धसमूह
- बायोआर्डर सेट
- सेमीग्रुप्स की विशेष कक्षाएं
- रचना की अंगूठी
संदर्भ
- ↑ Dominique Perrin; Jean Eric Pin (2004). Infinite Words: Automata, Semigroups, Logic and Games. Academic Press. p. 448. ISBN 978-0-12-532111-2.
- ↑ Alfred Hoblitzelle Clifford; G. B. Preston (1967). The Algebraic Theory of Semigroups. Volume II. American Mathematical Soc. p. 254. ISBN 978-0-8218-0272-4.
- ↑ 3.0 3.1 Anderson, James A. (2006). Automata Theory with Modern Applications. With contributions by Tom Head. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511607202. ISBN 978-0-521-61324-8. Zbl 1127.68049.
- ↑ Rivas, Exequiel; Jaskelioff, Mauro (2017). "Notions of Computation as Monoids". Journal of Functional Programming. 27 (e21). arXiv:1406.4823. doi:10.1017/S0956796817000132.
- Clifford, A.H.; Preston, G.B. (1961). The algebraic theory of semigroups. Vol. I. Mathematical Surveys. Vol. 7. Providence, R.I.: American Mathematical Society. ISBN 978-0-8218-0272-4. Zbl 0111.03403.
- Howie, John M. (1995). Fundamentals of Semigroup Theory. London Mathematical Society Monographs. New Series. Vol. 12. Oxford: Clarendon Press. ISBN 978-0-19-851194-6. Zbl 0835.20077.
- Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs, Expositions in Mathematics 29, Walter de Gruyter, Berlin, ISBN 978-3-11-015248-7.
