प्रपांतरण अर्धसमूह
बीजगणित में, एक रूपांतरण अर्धसमूह या संघटन अर्धसमूह परिवर्तन (फ़ंक्शन गणित एक संग्रह से स्वयं) का एक संग्रह है जो फ़ंक्शन संरचना के तहत क्लोजर गणित है। यदि इसमें पहचान कार्य शामिल है, तो यह एक मोनोइड है, जिसे एक परिवर्तन या रचना मोनोइड कहा जाता है। यह क्रमपरिवर्तन समूह का अर्धसमूह एनालॉग है।
एक संग्रह के परिवर्तन अर्धसमूह में एक टॉटोलॉजिकल अर्धसमूह क्रिया होती है। इस तरह के कार्यों मे यथातथ्य होने की विशेषता होती है, अर्थात, यदि अर्धसमूह के दो तत्वों में समान क्रिया होती है, तो वे समान होते हैं।
केली के प्रमेय के एक एनालॉग से पता चलता है कि किसी भी सेमिग्रुप को कुछ सेट के रूपांतरण सेमीग्रुप के रूप में महसूस किया जा सकता है।
ऑटोमेटा सिद्धांत में, कुछ लेखक सेमीग्रुप के बेस सेट से अलग राज्यों के एक सेट पर एक सेमीग्रुप सेमीग्रुप एक्शन को संदर्भित करने के लिए 'ट्रांसफॉर्मेशन सेमीग्रुप' शब्द का उपयोग करते हैं।[1] सेमीग्रुप एक्शन # ट्रांसफॉर्मेशन सेमीग्रुप्स है।
परिवर्तन सेमिग्रुप्स और मोनोइड्स
एक ट्रांसफ़ॉर्मेशन सेमीग्रुप एक जोड़ी (X,S) है, जहाँ X एक सेट है और S X के ट्रांसफ़ॉर्मेशन का सेमीग्रुप है। यहाँ X का रूपांतरण X के उपसमुच्चय से X तक केवल एक फ़ंक्शन (गणित) है, जरूरी नहीं कि उलटा हो, और इसलिए S केवल परिवर्तनों का एक सेट है X जो कार्यों की संरचना के अंतर्गत क्लोजर (गणित) है। किसी दिए गए बेस सेट, X पर सभी आंशिक कार्यों का सेट, एक नियमित सेमीग्रुप बनाता है जिसे सभी आंशिक परिवर्तनों का सेमीग्रुप कहा जाता है (या X पर आंशिक ट्रांसफ़ॉर्मेशन सेमीग्रुप), जिसे आमतौर पर निरूपित किया जाता है .[2] अगर S में X का आइडेंटिटी ट्रांसफॉर्मेशन शामिल है, तो इसे 'ट्रांसफॉर्मेशन मोनोइड' कहा जाता है। स्पष्ट रूप से कोई भी परिवर्तन सेमीग्रुप एस पहचान परिवर्तन के साथ एस के संघ को ले कर एक परिवर्तन मोनोइड एम निर्धारित करता है। एक परिवर्तन मोनोइड जिसका तत्व उलटा हो सकता है एक क्रमचय समूह है।
X के सभी परिवर्तनों का समुच्चय एक रूपांतरण मोनोइड है जिसे X का 'पूर्ण परिवर्तन मोनोइड' (या 'सेमीग्रुप') कहा जाता है। इसे X का 'सममित अर्धसमूह' भी कहा जाता है और इसे T द्वारा दर्शाया जाता है।X. इस प्रकार एक रूपांतरण उपार्ध समूह (या मोनोइड) एक्स के पूर्ण परिवर्तन मोनोइड का सिर्फ एक उपसमूह (या submonoid) है।
यदि (एक्स, एस) एक रूपांतरण अर्धसमूह है तो एक्स को मूल्यांकन द्वारा एस की एक अर्धसमूह कार्रवाई में बनाया जा सकता है:
यह एक मोनोइड क्रिया है यदि S एक रूपांतरण मोनोइड है।
क्रियाओं के रूप में परिवर्तन अर्धसमूहों की विशेषता यह है कि वे वफादार हैं, अर्थात, यदि
फिर एस = टी। विलोमतः यदि एक अर्धसमूह S समुच्चय X पर T(s,x) = s • x द्वारा कार्य करता है तो हम s ∈ S के लिए एक परिवर्तन T को परिभाषित कर सकते हैंs एक्स द्वारा
टी को नक्शा भेज रहा हैs इंजेक्शन है अगर और केवल अगर (एक्स, टी) वफादार है, इस मामले में इस मानचित्र की छवि एस के लिए एक परिवर्तन सेमीग्रुप आइसोमोर्फिक है।
केली प्रतिनिधित्व
समूह सिद्धांत में, केली के प्रमेय का दावा है कि कोई भी समूह जी जी के सममित समूह (एक सेट के रूप में माना जाता है) के एक उपसमूह के लिए आइसोमोर्फिक है, ताकि जी एक क्रमचय समूह हो। यह प्रमेय सीधे तौर पर मोनोइड्स के लिए सामान्यीकृत होता है: कोई भी मोनोइड एम इसके अंतर्निहित सेट का एक रूपांतरण मोनोइड है, जो बाएं (या दाएं) गुणन द्वारा दी गई क्रिया के माध्यम से होता है। यह क्रिया सत्य है क्योंकि यदि M में सभी x के लिए ax = bx है, तो x को सर्वसमिका अवयव के बराबर लेने पर, हमें a = b प्राप्त होता है।
एक (बाएं या दाएं) पहचान तत्व के बिना एक सेमीग्रुप एस के लिए, हम एक्स को मोनॉयड # उदाहरण के अंतर्निहित सेट के रूप में लेते हैं ताकि एस को एक्स के रूपांतरण सेमीग्रुप के रूप में महसूस किया जा सके। विशेष रूप से किसी भी परिमित सेमीग्रुप को परिवर्तनों के उप-समूह के रूप में दर्शाया जा सकता है एक सेट एक्स के साथ | एक्स | ≤ |एस| + 1, और यदि S एक मोनोइड है, तो हमारे पास शार्प बाउंड |X| है ≤ |S|, जैसा परिमित समूहों के मामले में है।[3]: 21
कंप्यूटर विज्ञान में
कंप्यूटर विज्ञान में, केली के अभ्यावेदन को कई रचित गुणन को पुन: संबद्ध करके सेमीग्रुप की स्पर्शोन्मुख दक्षता में सुधार करने के लिए लागू किया जा सकता है। बाएं गुणन द्वारा दी गई क्रिया का परिणाम दाएं-संबद्ध गुणन में होता है, और इसके विपरीत सही गुणन द्वारा दी गई क्रिया के लिए। किसी भी अर्धसमूह के लिए समान परिणाम होने के बावजूद, स्पर्शोन्मुख दक्षता भिन्न होगी। बाएं गुणन की एक क्रिया द्वारा दिए गए उपयोगी परिवर्तन मोनोइड्स के दो उदाहरण अंतर सूची डेटा संरचना के कार्यात्मक रूपांतर हैं, और मोनैडिक कोडेन्सिटी ट्रांसफ़ॉर्मेशन (एक मोनाड (श्रेणी सिद्धांत) का केली प्रतिनिधित्व, जो एक विशेष मोनोइडल श्रेणी में एक मोनोइड है फ़ंक्टर श्रेणी)।[4]
== एक automaton == का परिवर्तन मोनोइड
एम को राज्य स्थान एस और वर्णमाला ए के साथ एक निर्धारक automaton होने दें। मुक्त मोनोइड ए में शब्द∗ A से एक मोनोइड आकारिकी को जन्म देते हुए S के परिवर्तनों को प्रेरित करें∗ पूर्ण परिवर्तन मोनोइड टी के लिएS. इस आकारिकी की छवि एम का परिवर्तन अर्धसमूह है।[3]: 78
एक नियमित भाषा के लिए, सिंटैक्टिक मोनोइड भाषा के न्यूनतम automaton के परिवर्तन मोनोइड के लिए आइसोमोर्फिक है।[3]: 81
यह भी देखें
- अर्धस्वचालित
- क्रोहन-रोड्स सिद्धांत
- सममित उलटा अर्धसमूह
- बायोआर्डर सेट
- सेमीग्रुप्स की विशेष कक्षाएं
- रचना की अंगूठी
संदर्भ
- ↑ 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 3.2 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.
