प्रपांतरण अर्धसमूह: Difference between revisions

From Vigyanwiki
No edit summary
 
(18 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[बीजगणित]] में, एक रूपांतरण [[अर्धसमूह क्रिया|अर्धसमूह]] या संघटन [[अर्धसमूह क्रिया|अर्धसमूह]] [[परिवर्तन (फ़ंक्शन)|परिवर्तन]]  (फ़ंक्शन गणित एक संग्रह से स्वयं) का एक संग्रह है जो फ़ंक्शन संरचना के तहत क्लोजर गणित है। यदि इसमें पहचान कार्य शामिल है, तो यह एक [[मोनोइड]] है, जिसे एक परिवर्तन या रचना मोनोइड कहा जाता है। यह [[क्रमपरिवर्तन समूह]] का अर्धसमूह एनालॉग है।
[[बीजगणित]] में, रूपांतरण [[अर्धसमूह क्रिया|अर्धसमूह]] या संघटन [[अर्धसमूह क्रिया|अर्धसमूह]] [[परिवर्तन (फ़ंक्शन)|परिवर्तन]]  (फ़ंक्शन गणित एक संग्रह से स्वयं) का एक संग्रह है जो फ़ंक्शन संरचना के तहत क्लोजर गणित है। यदि इसमें पहचान कार्य शामिल है, तो यह एक [[मोनोइड]] है, जिसे एक परिवर्तन या रचना मोनोइड कहा जाता है। यह [[क्रमपरिवर्तन समूह]] का अर्धसमूह एनालॉग है।


एक संग्रह के परिवर्तन [[अर्धसमूह क्रिया|अर्धसमूह]] में एक टॉटोलॉजिकल [[अर्धसमूह क्रिया]] होती है। इस तरह के कार्यों मे यथातथ्य होने की विशेषता होती है, अर्थात, यदि अर्धसमूह के दो तत्वों में समान क्रिया होती है, तो वे समान होते हैं।
संग्रह के परिवर्तन [[अर्धसमूह क्रिया|अर्धसमूह]] में एक टॉटोलॉजिकल [[अर्धसमूह क्रिया]] होती है। इस तरह के कार्यों मे यथातथ्य होने की विशेषता होती है, अर्थात, यदि अर्धसमूह के दो तत्वों में समान क्रिया होती है, तो वे समान होते हैं।


केली प्रमेय के एक एनालॉग से पता चलता है कि किसी भी [[अर्धसमूह क्रिया|अर्धसमूह]] के कुछ संग्रह के रूपांतरण को [[अर्धसमूह क्रिया|अर्धसमूह]] के रूप में महसूस किया जा सकता है।
केली प्रमेय के एक एनालॉग से पता चलता है कि किसी भी [[अर्धसमूह क्रिया|अर्धसमूह]] के कुछ संग्रह के रूपांतरण को [[अर्धसमूह क्रिया|अर्धसमूह]] के रूप में संवेदन किया जा सकता है।


[[ऑटोमेटा सिद्धांत]] में, कुछ लेखक [[अर्धसमूह क्रिया|अर्धसमूह]] के आधार संग्रह से अलग संग्रह की एक स्थिति पर [[अर्धसमूह क्रिया|अर्धसमूह]] क्रिया को संदर्भित करने के लिए 'परिवर्तन [[अर्धसमूह क्रिया|अर्धसमूह]]' शब्द का उपयोग करते हैं।<ref name="PerrinPin2004">{{cite book|author1=Dominique Perrin|author2=Jean Eric Pin|title=Infinite Words: Automata, Semigroups, Logic and Games|url=https://books.google.com/books?id=tfZkZw6-ZTQC&pg=PA448|year=2004|publisher=Academic Press|isbn=978-0-12-532111-2|page=448}}</ref> दो धारणाओं के बीच एक पत्राचार है।
[[ऑटोमेटा सिद्धांत]] में, कुछ लेखक [[अर्धसमूह क्रिया|अर्धसमूह]] के आधार संग्रह से अलग संग्रह की एक स्थिति पर [[अर्धसमूह क्रिया|अर्धसमूह]] क्रिया को संदर्भित करने के लिए 'परिवर्तन [[अर्धसमूह क्रिया|अर्धसमूह]]' शब्द का उपयोग करते हैं।<ref name="PerrinPin2004">{{cite book|author1=Dominique Perrin|author2=Jean Eric Pin|title=Infinite Words: Automata, Semigroups, Logic and Games|url=https://books.google.com/books?id=tfZkZw6-ZTQC&pg=PA448|year=2004|publisher=Academic Press|isbn=978-0-12-532111-2|page=448}}</ref> दो धारणाओं के बीच एक पत्राचार है।
Line 9: Line 9:
== परिवर्तन सेमिग्रुप्स और मोनोइड्स ==
== परिवर्तन सेमिग्रुप्स और मोनोइड्स ==


एक ट्रांसफ़ॉर्मेशन सेमीग्रुप एक जोड़ी (''X'',''S'') है, जहाँ ''X'' एक सेट है और ''S'' ''X'' के ट्रांसफ़ॉर्मेशन का सेमीग्रुप है। यहाँ ''X'' का रूपांतरण ''X'' के उपसमुच्चय से ''X'' तक केवल एक फ़ंक्शन (गणित) है, जरूरी नहीं कि उलटा हो, और इसलिए ''S'' केवल परिवर्तनों का एक सेट है ''X'' जो [[कार्यों की संरचना]] के अंतर्गत क्लोजर (गणित) है। किसी दिए गए बेस सेट, ''X'' पर सभी आंशिक कार्यों का सेट, एक नियमित सेमीग्रुप बनाता है जिसे सभी आंशिक परिवर्तनों का सेमीग्रुप कहा जाता है (या ''X'' पर आंशिक ट्रांसफ़ॉर्मेशन सेमीग्रुप), जिसे आमतौर पर निरूपित किया जाता है <math>\mathcal{PT}_X</math>.<ref name="CliffordPreston1967">{{cite book|author1=Alfred Hoblitzelle Clifford|author2=G. B. Preston|title=The Algebraic Theory of Semigroups. Volume II|url=https://books.google.com/books?id=756KAwAAQBAJ&pg=254|year=1967|publisher=American Mathematical Soc.|isbn=978-0-8218-0272-4|page=254}}</ref>
परिवर्तन [[अर्धसमूह क्रिया|अर्धसमूह]] एक जोड़ी X,S है, जहाँ X एक संग्रह है और SX  परिवर्तन का अर्धसमूह है। यहाँ X का रूपांतरण X के उपसमुच्चय से X तक केवल एक फ़ंक्शन (गणित) है, जरूरी नहीं कि उलटा हो, और इसलिए S केवल परिवर्तनों का एक संग्रह है X जो [[कार्यों की संरचना]] के अंतर्गत क्लोजर (गणित) है। किसी दिए गए आधार संग्रह X पर सभी आंशिक कार्यों का संग्रह, एक नियमित [[अर्धसमूह क्रिया|अर्धसमूह]] बनाता है जिसे सभी आंशिक परिवर्तनों का अर्धसमूह कहा जाता है (या X पर आंशिक परिवर्तन [[अर्धसमूह क्रिया|अर्धसमूह]]), जिसे आमतौर पर निरूपित किया जाता है <math>\mathcal{PT}_X</math>.<ref name="CliffordPreston1967">{{cite book|author1=Alfred Hoblitzelle Clifford|author2=G. B. Preston|title=The Algebraic Theory of Semigroups. Volume II|url=https://books.google.com/books?id=756KAwAAQBAJ&pg=254|year=1967|publisher=American Mathematical Soc.|isbn=978-0-8218-0272-4|page=254}}</ref>
अगर S में X का आइडेंटिटी ट्रांसफॉर्मेशन शामिल है, तो इसे 'ट्रांसफॉर्मेशन मोनोइड' कहा जाता है। स्पष्ट रूप से कोई भी परिवर्तन सेमीग्रुप एस पहचान परिवर्तन के साथ एस के संघ को ले कर एक परिवर्तन मोनोइड एम निर्धारित करता है। एक परिवर्तन मोनोइड जिसका तत्व उलटा हो सकता है एक क्रमचय समूह है।
अगर SX (S में X का आइडेंटिटी परिवर्तनों शामिल है, तो इसे 'परिवर्तनों मोनोइड' कहा जाता है। स्पष्ट रूप से कोई भी परिवर्तन अर्धसमूह S पहचान परिवर्तन के साथ S के संघ को ले कर एक परिवर्तन मोनोइड M निर्धारित करता है। एक परिवर्तन मोनोइड जिसका तत्व उलटा हो सकता है एक क्रमचय समूह है।


X के सभी परिवर्तनों का समुच्चय एक रूपांतरण मोनोइड है जिसे X का 'पूर्ण परिवर्तन मोनोइड' (या 'सेमीग्रुप') कहा जाता है। इसे X का 'सममित अर्धसमूह' भी कहा जाता है और इसे T द्वारा दर्शाया जाता है।<sub>''X''</sub>. इस प्रकार एक रूपांतरण [[उपार्ध समूह]] (या मोनोइड) एक्स के पूर्ण परिवर्तन मोनोइड का सिर्फ एक उपसमूह (या [[submonoid]]) है।
X के सभी परिवर्तनों का समुच्चय एक रूपांतरण मोनोइड है जिसे X का 'पूर्ण परिवर्तन मोनोइड' (या '[[अर्धसमूह क्रिया|अर्धसमूह]]') कहा जाता है। इसे X का 'सममित अर्धसमूह' भी कहा जाता है और इसे टी (T) द्वारा दर्शाया जाता है।<sub>''X''</sub>. इस प्रकार एक रूपांतरण [[उपार्ध समूह]] (या मोनोइड) X के पूर्ण परिवर्तन मोनोइड का सिर्फ एक उपसमूह (या [[submonoid|सबमोनोइड़]]) है।


यदि (एक्स, एस) एक रूपांतरण अर्धसमूह है तो एक्स को मूल्यांकन द्वारा एस की एक अर्धसमूह कार्रवाई में बनाया जा सकता है:
यदि X, S (X =T) एक रूपांतरण अर्धसमूह है तो को मूल्यांकन द्वारा S (S)की एक अर्धसमूह कार्रवाई में बनाया जा सकता है:


:<math> s\cdot x = s(x)\text{ for }s\in S, x\in X.</math>
:<math> s\cdot x = s(x)\text{ for }s\in S, x\in X.</math>
यह एक मोनोइड क्रिया है यदि S एक रूपांतरण मोनोइड है।
यह एक मोनोइड क्रिया है यदि S एक रूपांतरण मोनोइड है।


क्रियाओं के रूप में परिवर्तन अर्धसमूहों की विशेषता यह है कि वे वफादार हैं, अर्थात, यदि
क्रियाओं के रूप में परिवर्तन अर्धसमूहों की विशेषता यह है कि वे कर्त्तव्यनिष्ठ हैं, अर्थात, यदि


:<math> s\cdot x = t\cdot x\text{ for all }x\in X,</math>
:<math> s\cdot x = t\cdot x\text{ for all }x\in X,</math>
फिर एस = टी। विलोमतः यदि एक अर्धसमूह S समुच्चय X पर T(s,x) = s • x द्वारा कार्य करता है तो हम s ∈ S के लिए एक परिवर्तन T को परिभाषित कर सकते हैं<sub>''s''</sub> एक्स द्वारा
फिर S = टी (T)। विलोमतः यदि एक अर्धसमूह S समुच्चय X पर टी (T) SX (s,x) = s • x द्वारा कार्य करता है तो हम s ∈ S के लिए एक परिवर्तन टी (T) को परिभाषित कर सकते हैं<sub>''s''</sub> X द्वारा


:<math> T_s (x) = T(s,x).\,</math>
:<math> T_s (x) = T(s,x).\,</math>
टी को नक्शा भेज रहा है<sub>''s''</sub> इंजेक्शन है अगर और केवल अगर (एक्स, टी) वफादार है, इस मामले में इस मानचित्र की छवि एस के लिए एक परिवर्तन सेमीग्रुप आइसोमोर्फिक है।
TS (Ts) को S भेजने वाला नक्शा इंजेक्शन है तो (X, टी (X,T) कर्त्तव्यनिष्ठ है, इस मामले में इस मानचित्र की छवि S परिवर्तन [[अर्धसमूह क्रिया|अर्धसमूह]] आइसोमोर्फिक है।


== केली प्रतिनिधित्व ==
== केली प्रतिनिधित्व ==


[[समूह सिद्धांत]] में, केली के प्रमेय का दावा है कि कोई भी समूह जी जी के [[सममित समूह]] (एक सेट के रूप में माना जाता है) के एक उपसमूह के लिए आइसोमोर्फिक है, ताकि जी एक क्रमचय समूह हो। यह प्रमेय सीधे तौर पर मोनोइड्स के लिए सामान्यीकृत होता है: कोई भी मोनोइड एम इसके अंतर्निहित सेट का एक रूपांतरण मोनोइड है, जो बाएं (या दाएं) गुणन द्वारा दी गई क्रिया के माध्यम से होता है। यह क्रिया सत्य है क्योंकि यदि M में सभी x के लिए ax = bx है, तो x को सर्वसमिका अवयव के बराबर लेने पर, हमें a = b प्राप्त होता है।
[[समूह सिद्धांत]] में, केली के प्रमेय का दावा है कि कोई भी समूह जी (G) के [[सममित समूह]] (एक सेट के रूप में माना जाता है) के एक उपसमूह के लिए समरुप है, ताकि जी (G) एक क्रमचय समूह मे रहे। यह प्रमेय सीधे तौर पर मोनोइड्स के लिए सामान्यीकृत होता है, कोई भी मोनोइड M  मे अंतर्निहित संग्रह का एक रूपांतरण मोनोइड है, जो बाएं (या दाएं) गुणन द्वारा दी गई क्रिया के माध्यम से होता है। यह क्रिया सत्य है क्योंकि यदि M में सभी x के लिए ax = bx है, तो x को सर्वसमिका अवयव के बराबर लेने पर, हमें a = b प्राप्त होता है।


एक (बाएं या दाएं) पहचान तत्व के बिना एक सेमीग्रुप एस के लिए, हम एक्स को मोनॉयड # उदाहरण के अंतर्निहित सेट के रूप में लेते हैं ताकि एस को एक्स के रूपांतरण सेमीग्रुप के रूप में महसूस किया जा सके। विशेष रूप से किसी भी परिमित सेमीग्रुप को परिवर्तनों के उप-समूह के रूप में दर्शाया जा सकता है एक सेट एक्स के साथ | एक्स | ≤ |एस| + 1, और यदि S एक मोनोइड है, तो हमारे पास शार्प बाउंड |X| है ≤ |S|, जैसा [[परिमित समूह]]ों के मामले में है।<ref name=JAA>{{cite book | last=Anderson | first=James A. | title=Automata Theory with Modern Applications | others=With contributions by Tom Head | location=Cambridge | publisher=[[Cambridge University Press]] | year=2006 | isbn=978-0-521-61324-8 | doi=10.1017/CBO9780511607202|zbl=1127.68049 }}</ref>{{rp|21}}
(बाएं या दाएं) पहचान तत्व के बिना एक [[अर्धसमूह क्रिया|अर्धसमूह]] Sके लिए, हम को मोनॉयड # उदाहरण के अंतर्निहित संग्रह के रूप में लेते हैं ताकि Sको X के रूपांतरण [[अर्धसमूह क्रिया|अर्धसमूह]] के रूप में संवेदन किया जा सके। विशेष रूप से किसी भी परिमित [[अर्धसमूह क्रिया|अर्धसमूह]] को परिवर्तनों के उप-समूह के रूप में दर्शाया जा सकता है एक संग्रह X के साथ | X | ≤ |S| + 1, और यदि S एक मोनोइड है, तो हमारे पास शार्प बाउंड |X| है ≤ |S|, जैसा [[परिमित समूह]] के मामले में है।<ref name=JAA>{{cite book | last=Anderson | first=James A. | title=Automata Theory with Modern Applications | others=With contributions by Tom Head | location=Cambridge | publisher=[[Cambridge University Press]] | year=2006 | isbn=978-0-521-61324-8 | doi=10.1017/CBO9780511607202|zbl=1127.68049 }}</ref>{{rp|21}}
 
=== [[कंप्यूटर विज्ञान]] ===
 
=== [[कंप्यूटर विज्ञान]] में ===


कंप्यूटर विज्ञान में, केली के अभ्यावेदन को कई रचित गुणन मे पुन: संबद्ध करके [[अर्धसमूह क्रिया|अर्धसमूह]] की स्पर्शोन्मुख दक्षता में सुधार करने के लिए लागू किया जा सकता है। बाएं गुणन द्वारा दी गई क्रिया का परिणाम दाएं-संबद्ध गुणन में होता है, और इसके विपरीत सही गुणन द्वारा दी गई क्रिया के लिए किसी भी अर्धसमूह के लिए समान परिणाम होने के बावजूद, स्पर्शोन्मुख दक्षता भिन्न होती है। बाएं गुणन की एक क्रिया द्वारा दिए गए उपयोगी परिवर्तन मोनोइड्स के दो उदाहरण [[अंतर सूची]] डेटा संरचना के कार्यात्मक रूपांतर हैं, और मोनैडिक घनत्व परिवर्तन (मोनैड का एक केली प्रतिनिधित्व, जो एक विशेष मोनोइडल फ़ंक्टर श्रेणी में एक मोनोइड है)।<ref>{{ cite journal | last1=Rivas | first1=Exequiel | last2=Jaskelioff | first2=Mauro | title=''Notions of Computation as Monoids'' | journal=Journal of Functional Programming |year=2017 | volume=27 | issue=e21 | doi=10.1017/S0956796817000132 | arxiv=1406.4823 }}</ref>
कंप्यूटर विज्ञान में, केली के अभ्यावेदन को कई रचित गुणन मे पुन: संबद्ध करके [[अर्धसमूह क्रिया|अर्धसमूह]] की स्पर्शोन्मुख दक्षता में सुधार करने के लिए लागू किया जा सकता है। बाएं गुणन द्वारा दी गई क्रिया का परिणाम दाएं-संबद्ध गुणन में होता है, और इसके विपरीत सही गुणन द्वारा दी गई क्रिया के लिए किसी भी अर्धसमूह के लिए समान परिणाम होने के बावजूद, स्पर्शोन्मुख दक्षता भिन्न होती है। बाएं गुणन की एक क्रिया द्वारा दिए गए उपयोगी परिवर्तन मोनोइड्स के दो उदाहरण [[अंतर सूची]] डेटा संरचना के कार्यात्मक रूपांतर हैं, और मोनैडिक घनत्व परिवर्तन (मोनैड का एक केली प्रतिनिधित्व, जो एक विशेष मोनोइडल फ़ंक्टर श्रेणी में एक मोनोइड है)।<ref>{{ cite journal | last1=Rivas | first1=Exequiel | last2=Jaskelioff | first2=Mauro | title=''Notions of Computation as Monoids'' | journal=Journal of Functional Programming |year=2017 | volume=27 | issue=e21 | doi=10.1017/S0956796817000132 | arxiv=1406.4823 }}</ref>


'''<u>एक ऑटोमेटन का परिवर्तन मोनोइड</u>'''


== एक [[automaton]] == का परिवर्तन मोनोइड
M को राज्य स्थान S और वर्णमाला ए (A) के साथ एक निर्धारक ऑटोमेटन होने दें। [[मुक्त मोनोइड]] A<sup>∗</sup> में शब्द S के परिवर्तनों को प्रेरित करते हैं जो A<sup>∗</sup> से पूर्ण परिवर्तन मोनोइड TS तक एक मोनोइड आकारिकी को उत्पत्ति देते हैं। इस आकारिकी की छवि का परिवर्तन अर्धसमूह है।
एम को राज्य स्थान एस और वर्णमाला ए के साथ एक निर्धारक automaton होने दें। [[मुक्त मोनोइड]] ए में शब्द<sup>∗</sup> A से एक [[मोनोइड आकारिकी]] को जन्म देते हुए S के परिवर्तनों को प्रेरित करें<sup>∗</sup> पूर्ण परिवर्तन मोनोइड टी के लिए<sub>''S''</sub>. इस आकारिकी की छवि एम का परिवर्तन अर्धसमूह है।<ref name=JAA/>{{rp|78}}
एक [[नियमित भाषा]] के लिए, [[सिंटैक्टिक मोनोइड]] भाषा के न्यूनतम automaton के परिवर्तन मोनोइड के लिए आइसोमोर्फिक है।<ref name=JAA/>{{rp|81}}
 


नियमित भाषा के लिए, सिंटैक्टिक मोनॉयड भाषा के न्यूनतम ऑटोमेटन के परिवर्तन मोनोइड के लिए समरूप है।  <ref name="JAA" />
== यह भी देखें ==
== यह भी देखें ==
* [[अर्धस्वचालित]]
* [[अर्धस्वचालित]]
Line 58: Line 55:
* {{cite book | last= Howie | first= John M. |authorlink=John M. Howie| title=Fundamentals of Semigroup Theory | year=1995 | publisher=[[Clarendon Press]] | isbn=978-0-19-851194-6 | zbl=0835.20077 | series=London Mathematical Society Monographs. New Series | volume=12 | location=Oxford }}
* {{cite book | last= Howie | first= John M. |authorlink=John M. Howie| title=Fundamentals of Semigroup Theory | year=1995 | publisher=[[Clarendon Press]] | isbn=978-0-19-851194-6 | zbl=0835.20077 | series=London Mathematical Society Monographs. New Series | volume=12 | location=Oxford }}
* 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}}.
* 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}}.
[[Category: अर्धसमूह सिद्धांत]]


[[Category: Machine Translated Page]]
[[Category:Created On 03/02/2023]]
[[Category:Created On 03/02/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:अर्धसमूह सिद्धांत]]

Latest revision as of 19:00, 10 February 2023

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

संग्रह के परिवर्तन अर्धसमूह में एक टॉटोलॉजिकल अर्धसमूह क्रिया होती है। इस तरह के कार्यों मे यथातथ्य होने की विशेषता होती है, अर्थात, यदि अर्धसमूह के दो तत्वों में समान क्रिया होती है, तो वे समान होते हैं।

केली प्रमेय के एक एनालॉग से पता चलता है कि किसी भी अर्धसमूह के कुछ संग्रह के रूपांतरण को अर्धसमूह के रूप में संवेदन किया जा सकता है।

ऑटोमेटा सिद्धांत में, कुछ लेखक अर्धसमूह के आधार संग्रह से अलग संग्रह की एक स्थिति पर अर्धसमूह क्रिया को संदर्भित करने के लिए 'परिवर्तन अर्धसमूह' शब्द का उपयोग करते हैं।[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]

यह भी देखें

संदर्भ

  1. Dominique Perrin; Jean Eric Pin (2004). Infinite Words: Automata, Semigroups, Logic and Games. Academic Press. p. 448. ISBN 978-0-12-532111-2.
  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. 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.
  4. Rivas, Exequiel; Jaskelioff, Mauro (2017). "Notions of Computation as Monoids". Journal of Functional Programming. 27 (e21). arXiv:1406.4823. doi:10.1017/S0956796817000132.