मोनॉइड गुणनखंडन: Difference between revisions

Latest revision as of 10:10, 27 June 2023

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

चलो A* अक्षर A पर मुक्त मोनॉइड है। मान लीजिए X_i A* के उपसमुच्चय का अनुक्रम है एक पूरी तरह से व्यवस्थित सेट सूचकांक सेट I द्वारा अनुक्रमित। A* में एक शब्द w का गुणनखंड एक अभिव्यक्ति है

w=x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\

साथ $x_{i_{j}}\in X_{i_{j}}$ और $i_{1}\geq i_{2}\geq \ldots \geq i_{n}$ . कुछ लेखक असमानताओं के क्रम को विपरीत कर देते हैं।

चेन-फॉक्स-लिंडन प्रमेय

पूरी तरह से आदेशित वर्णमाला A पर एक लिंडन शब्द एक ऐसा शब्द है जो अपने सभी घुमावों से कम लेक्सिकोग्राफिक ऑर्डर है।^[1] चेन-फॉक्स-लिंडन प्रमेय कहता है कि लिंडन शब्दों के एक गैर-बढ़ते अनुक्रम को जोड़कर प्रत्येक स्ट्रिंग को एक अनूठे विधि से बनाया जा सकता है। इसलिए 'X_l प्रत्येक लिंडन शब्द l के लिए सिंगलटन सेट {l} होने के लिए, लिंडन शब्दों के सूचकांक सेट L के साथ लेक्सिकोग्राफिक रूप से आदेशित, हम A * का एक कारक प्राप्त करते हैं.^[2] ऐसा गुणनखण्ड रैखिक समय में पाया जा सकता है।^[3]

हॉल शब्द

हॉल सेट एक गुणनखंड प्रदान करता है।^[4] वास्तव में लिंडन शब्द हॉल शब्द का एक विशेष स्थिति है। हॉल वर्ड्स पर लेख इस गुणनखंड के प्रमाण को स्थापित करने के लिए आवश्यक सभी तंत्रों का एक रेखाचित्र प्रदान करता है।

द्विभाजन

एक मुक्त मोनॉइड का द्विभाजन केवल दो वर्गों X₀, X₁ के साथ एक गुणनखंड है।^[5]

उदाहरण:

A = {a,b}, X₀ = {a^*b}, X₁ = {a}.

यदि एक्स, वाई गैर-रिक्त शब्दों के असम्बद्ध सेट हैं, तो (X,Y) A* का एक समद्विभाजन है यदि और केवल यदि^[6]

YX\cup A=X\cup Y\ .

परिणामस्वरूप,A⁺ के किसी भी विभाजन P, Q के लिए एक अद्वितीय समद्विभाजन (X,Y) होता है जिसमें X, P का एक उपसमुच्चय और Y, Q का एक उपसमुच्चय होता है।^[7]

शुट्ज़ेनबर्गर प्रमेय

यह प्रमेय बताता है कि अनुक्रम X_i A^* के सबसेट के एक गुणनखण्ड बनाता है यदि और केवल यदि निम्नलिखित तीन कथनों में से दो कथन धारण करते हैं:

A^* का हर तत्व आवश्यक रूप में कम से कम एक अभिव्यक्ति है;
A^* का हर तत्व में आवश्यक रूप में अधिकतम एक अभिव्यक्ति है;
प्रत्येक संयुग्म वर्ग C केवल एक मोनोइड M_i = X_i* से मिलता है और M_i में C के तत्व M_i में संयुग्मी हैं.^[8]

यह भी देखें

सेस्क्विपॉवर

संदर्भ

↑ Lothaire (1997) p.64
↑ Lothaire (1997) p.67
↑ Duval, Jean-Pierre (1983). "एक आदेशित वर्णमाला पर शब्दों का गुणनखंडन करना". Journal of Algorithms. 4 (4): 363–381. doi:10.1016/0196-6774(83)90017-2..
↑ Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words", Journal of Combinatoric Theory, 59A(2) pp. 285–308.
↑ Lothaire (1997) p.68
↑ Lothaire (1997) p.69
↑ Lothaire (1997) p.71
↑ Lothaire (1997) p.92

Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J.-É.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, R.; Rota, G.-C. Foreword by Roger Lyndon (2nd ed.), Cambridge University Press, ISBN 0-521-59924-5, Zbl 0874.20040

[L64-1] Lothaire (1997) p.64

[L67-2] Lothaire (1997) p.67

[3] Duval, Jean-Pierre (1983). "एक आदेशित वर्णमाला पर शब्दों का गुणनखंडन करना". Journal of Algorithms. 4 (4): 363–381. doi:10.1016/0196-6774(83)90017-2..

[melancon-4] Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words", Journal of Combinatoric Theory, 59A(2) pp. 285–308.

[L68-5] Lothaire (1997) p.68

[L69-6] Lothaire (1997) p.69

[L71-7] Lothaire (1997) p.71

[L92-8] Lothaire (1997) p.92

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
-गणित में, एक मुक्त मोनॉइड का गुणनखंड शब्दों के [[सबसेट]] का एक अनुक्रम है, जिसमें संपत्ति के साथ मुक्त मोनॉइड में प्रत्येक शब्द को उपसमुच्चय से खींचे गए तत्वों के संयोजन के रूप में लिखा जा सकता है। चेन-[[राल्फ फॉक्स]]-[[रोजर लिंडन]] प्रमेय कहता है कि [[लिंडन शब्द]] एक गुणनखंड प्रस्तुत करते हैं। मार्सेल शुटजेनबर्गर | शुत्जेनबर्गर प्रमेय एक गुणात्मक संपत्ति के संदर्भ में परिभाषा को एक योगात्मक संपत्ति से संबंधित करता है।{{clarify|reason=What, exactly, is the "additive property", here? What makes this additive? I have a vague glimmer of what it might be,but this statement is imprecise. |date=October 2020}}
+गणित में एक मुक्त मोनॉइड का गुणनखंड शब्दों के [[सबसेट]] का एक अनुक्रम है जिसमें गुण के साथ मुक्त मोनॉइड में प्रत्येक शब्द को उपसमुच्चय से खींचे गए तत्वों के संयोजन के रूप में लिखा जा सकता है। चेन-[[राल्फ फॉक्स]]-[[रोजर लिंडन]] प्रमेय कहता है कि [[लिंडन शब्द]] एक गुणनखंड प्रस्तुत करते हैं। मार्सेल शुत्जेनबर्गर प्रमेय एक गुणात्मक गुण के संदर्भ में परिभाषा को एक योगात्मक गुण से संबंधित करता है।
-चलो ए<sup>*</sup> अक्षर A पर मुक्त मोनॉइड बनें। मान लीजिए X<sub>''i''</sub> ए के उपसमुच्चय का एक क्रम हो<sup>*</sup> एक पूरी तरह से व्यवस्थित सेट [[ सूचकांक सेट ]] I द्वारा अनुक्रमित। A में एक शब्द w का गुणनखंड<sup>*</sup> एक अभिव्यक्ति है
+चलो A* अक्षर A पर मुक्त मोनॉइड है। मान लीजिए X<sub>''i''</sub> A* के उपसमुच्चय का अनुक्रम है एक पूरी तरह से व्यवस्थित सेट [[ सूचकांक सेट |सूचकांक सेट]] I द्वारा अनुक्रमित। A* में एक शब्द w का गुणनखंड एक अभिव्यक्ति है
 :<math>w = x_{i_1} x_{i_2} \cdots x_{i_n} \ </math>
-साथ <math>x_{i_j} \in X_{i_j}</math> और <math>i_1 \ge i_2 \ge \ldots \ge i_n</math>. कुछ लेखक असमानताओं के क्रम को उलट देते हैं।
+साथ <math>x_{i_j} \in X_{i_j}</math> और <math>i_1 \ge i_2 \ge \ldots \ge i_n</math>. कुछ लेखक असमानताओं के क्रम को विपरीत कर देते हैं।
 == चेन-फॉक्स-लिंडन प्रमेय ==
-पूरी तरह से आदेशित वर्णमाला A पर एक लिंडन शब्द एक ऐसा शब्द है जो अपने सभी घुमावों से कम [[लेक्सिकोग्राफिक ऑर्डर]] है।<ref name=L64>Lothaire (1997) p.64</ref> चेन-फॉक्स-लिंडन प्रमेय कहता है कि लिंडन शब्दों के एक गैर-बढ़ते अनुक्रम को जोड़कर प्रत्येक स्ट्रिंग को एक अनूठे तरीके से बनाया जा सकता है। इसलिए 'एक्स' लेना<sub>''l''</sub> प्रत्येक लिंडन शब्द l के लिए [[सिंगलटन सेट]] {l} होने के लिए, लिंडन शब्दों के सूचकांक सेट L के साथ लेक्सिकोग्राफिक रूप से आदेशित, हम A का एक कारक प्राप्त करते हैं<sup>*</सुप>.<ref name=L67>Lothaire (1997) p.67</ref> ऐसा गुणनखण्ड [[रैखिक समय]] में पाया जा सकता है।<ref>{{cite journal | last = Duval | first = Jean-Pierre | doi = 10.1016/0196-6774(83)90017-2 | issue = 4
+पूरी तरह से आदेशित वर्णमाला A पर एक लिंडन शब्द एक ऐसा शब्द है जो अपने सभी घुमावों से कम [[लेक्सिकोग्राफिक ऑर्डर]] है।<ref name=L64>Lothaire (1997) p.64</ref> चेन-फॉक्स-लिंडन प्रमेय कहता है कि लिंडन शब्दों के एक गैर-बढ़ते अनुक्रम को जोड़कर प्रत्येक स्ट्रिंग को एक अनूठे विधि से बनाया जा सकता है। इसलिए '''X<sub>l</sub>'' प्रत्येक लिंडन शब्द l के लिए [[सिंगलटन सेट]] {l} होने के लिए, लिंडन शब्दों के सूचकांक सेट L के साथ लेक्सिकोग्राफिक रूप से आदेशित, हम A * का एक कारक प्राप्त करते हैं.<ref name="L67">Lothaire (1997) p.67</ref> ऐसा गुणनखण्ड [[रैखिक समय]] में पाया जा सकता है।<ref>{{cite journal | last = Duval | first = Jean-Pierre | doi = 10.1016/0196-6774(83)90017-2 | issue = 4
   | journal = Journal of Algorithms | pages = 363–381 | title = एक आदेशित वर्णमाला पर शब्दों का गुणनखंडन करना| volume = 4 | year = 1983}}.</ref>
 == हॉल शब्द ==
 [[हॉल सेट]] एक गुणनखंड प्रदान करता है।<ref name="melancon">
 Guy Melançon, (1992) "[https://core.ac.uk/download/pdf/82581798.pdf Combinatorics of Hall trees and Hall words]", ''Journal of Combinatoric Theory'', '''59A'''(2) pp. 285–308.
-</ref>
+</ref> वास्तव में लिंडन शब्द [[हॉल शब्द]] का एक विशेष स्थिति है। हॉल वर्ड्स पर लेख इस गुणनखंड के प्रमाण को स्थापित करने के लिए आवश्यक सभी तंत्रों का एक रेखाचित्र प्रदान करता है।
-दरअसल, लिंडन शब्द [[हॉल शब्द]]ों का एक विशेष मामला है। हॉल वर्ड्स पर लेख इस गुणनखंड के प्रमाण को स्थापित करने के लिए आवश्यक सभी तंत्रों का एक रेखाचित्र प्रदान करता है।
 == द्विभाजन ==
-एक मुक्त मोनॉइड का द्विभाजन केवल दो वर्गों ''X'' के साथ एक गुणनखंड है<sub>0</sub>, एक्स<sub>1</sub>.<ref name=L68>Lothaire (1997) p.68</ref>
+एक मुक्त मोनॉइड का द्विभाजन केवल दो वर्गों ''X''<sub>0</sub>, ''X''<sub>1</sub> के साथ एक गुणनखंड है।<ref name="L68">Lothaire (1997) p.68</ref>
 उदाहरण:
-: ए = {ए, बी}, एक्स<sub>0</sub> = {अ<sup>*</sup>बी}, एक्स<sub>1</sub> = {ए}।
+: ''A'' = {''a'',''b''}, ''X''<sub>0</sub> = {''a''<sup>*</sup>''b''}, ''X''<sub>1</sub> = {''a''}.
-यदि एक्स, वाई गैर-रिक्त शब्दों के असम्बद्ध सेट हैं, तो (एक्स, वाई) ए * का एक समद्विभाजन है यदि और केवल यदि<ref name=L69>Lothaire (1997) p.69</ref>
+यदि एक्स, वाई गैर-रिक्त शब्दों के असम्बद्ध सेट हैं, तो (''X'',''Y'') ''A''* का एक समद्विभाजन है यदि और केवल यदि<ref name="L69">Lothaire (1997) p.69</ref>
 :<math>YX \cup A = X \cup Y \ . </math>
-परिणामस्वरूप, किसी भी विभाजन P के लिए, A का Q<sup>+</sup> एक अद्वितीय समद्विभाजन (X,Y) है जिसमें X, P का एक उपसमुच्चय है और Y, Q का एक उपसमुच्चय है।<ref name=L71>Lothaire (1997) p.71</ref>
+परिणामस्वरूप,''A''<sup>+</sup> के किसी भी विभाजन P, Q के लिए एक अद्वितीय समद्विभाजन (X,Y) होता है जिसमें X, P का एक उपसमुच्चय और Y, Q का एक उपसमुच्चय होता है।<ref name="L71">Lothaire (1997) p.71</ref>
 == शुट्ज़ेनबर्गर प्रमेय ==
-यह प्रमेय बताता है कि अनुक्रम X<sub>''i''</sub> ए के सबसेट के<sup>*</sup> एक गुणनखण्ड बनाता है यदि और केवल यदि निम्नलिखित तीन कथनों में से दो कथन धारण करते हैं:
+यह प्रमेय बताता है कि अनुक्रम X<sub>''i''</sub> ''A''<sup>*</sup> के सबसेट के एक गुणनखण्ड बनाता है यदि और केवल यदि निम्नलिखित तीन कथनों में से दो कथन धारण करते हैं:
-* ए का हर तत्व<sup>*</sup> आवश्यक रूप में कम से कम एक अभिव्यक्ति है;{{clarify|reason=What does "required form" mean here? I guess I should assume the "required form" is the product in descending order, given previously, right? The wording is awkward.|date=October 2020}}
+* ''A''<sup>*</sup> का हर तत्व आवश्यक रूप में कम से कम एक अभिव्यक्ति है;
-* ए का हर तत्व<sup>*</sup> में आवश्यक रूप में अधिकतम एक अभिव्यक्ति है;
+* ''A''<sup>*</sup> का हर तत्व में आवश्यक रूप में अधिकतम एक अभिव्यक्ति है;
-* प्रत्येक संयुग्म वर्ग C केवल एक [[मोनोइड]] M से मिलता है<sub>''i''</sub> = एक्स<sub>''i''</sub>* और एम में सी के तत्व<sub>''i''</sub> एम में संयुग्मी हैं<sub>''i''</sub>.<ref name=L92>Lothaire (1997) p.92</ref>{{clarify|reason=What, exactly is meant by "meet", here? I assume that it means that the intersection of ''C'' and M_i is non-empty for one and only one i? Right? I dislike having to guess; I sometimes guess incorrectly.|date=October 2020}}
+* प्रत्येक संयुग्म वर्ग C केवल एक [[मोनोइड]] ''M<sub>i</sub>'' = ''X<sub>i</sub>''* से मिलता है और ''M<sub>i</sub>'' में ''C'' के तत्व ''M<sub>i</sub>'' में संयुग्मी हैं.<ref name=L92>Lothaire (1997) p.92</ref>
+== यह भी देखें                                       ==
-== यह भी देखें ==
 * [[सेस्क्विपॉवर]]
@@ Line 39: / Line 35: @@
 {{reflist}}
 *{{Citation | last=Lothaire | first=M. | authorlink=M. Lothaire | others=Perrin, D.; Reutenauer, C.; Berstel, J.; [[Jean-Éric Pin|Pin, J.-É.]]; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, R.; [[Gian-Carlo Rota|Rota, G.-C.]] Foreword by Roger Lyndon | title=Combinatorics on words | edition=2nd | series=Encyclopedia of Mathematics and Its Applications | volume=17 | publisher=[[Cambridge University Press]] | year=1997 | isbn=0-521-59924-5 | zbl=0874.20040 }}
-[[Category: औपचारिक भाषाएँ]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 01/06/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:औपचारिक भाषाएँ]]

Anonymous

Search

मोनॉइड गुणनखंडन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:10, 27 June 2023

Contents

चेन-फॉक्स-लिंडन प्रमेय

हॉल शब्द

द्विभाजन

शुट्ज़ेनबर्गर प्रमेय

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

मोनॉइड गुणनखंडन: Difference between revisions

Latest revision as of 10:10, 27 June 2023

चेन-फॉक्स-लिंडन प्रमेय

हॉल शब्द

द्विभाजन

शुट्ज़ेनबर्गर प्रमेय

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories