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

Revision as of 13:04, 10 June 2023

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

चलो ए^* अक्षर A पर मुक्त मोनॉइड बनें। मान लीजिए X_i ए के उपसमुच्चय का एक क्रम हो^* एक पूरी तरह से व्यवस्थित सेट सूचकांक सेट 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] चेन-फॉक्स-लिंडन प्रमेय कहता है कि लिंडन शब्दों के एक गैर-बढ़ते अनुक्रम को जोड़कर प्रत्येक स्ट्रिंग को एक अनूठे तरीके से बनाया जा सकता है। इसलिए 'एक्स' लेना_l प्रत्येक लिंडन शब्द l के लिए सिंगलटन सेट {l} होने के लिए, लिंडन शब्दों के सूचकांक सेट L के साथ लेक्सिकोग्राफिक रूप से आदेशित, हम A का एक कारक प्राप्त करते हैं^{*</सुप>.^[2] ऐसा गुणनखण्ड रैखिक समय में पाया जा सकता है।^[3]}

हॉल शब्द

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

द्विभाजन

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

ए = {ए, बी}, एक्स₀ = {अ^*बी}, एक्स₁ = {ए}।

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

YX\cup A=X\cup Y\ .

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

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

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

ए का हर तत्व^* आवश्यक रूप में कम से कम एक अभिव्यक्ति है;
ए का हर तत्व^* में आवश्यक रूप में अधिकतम एक अभिव्यक्ति है;
प्रत्येक संयुग्म वर्ग C केवल एक मोनोइड M से मिलता है_i = एक्स_i* और एम में सी के तत्व_i एम में संयुग्मी हैं_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> एक अभिव्यक्ति है
+चलो ए<sup>*</sup> अक्षर A पर मुक्त मोनॉइड बनें। मान लीजिए X<sub>''i''</sub> ए के उपसमुच्चय का एक क्रम हो<sup>*</sup> एक पूरी तरह से व्यवस्थित सेट [[ सूचकांक सेट |सूचकांक सेट]] I द्वारा अनुक्रमित। A में एक शब्द w का गुणनखंड<sup>*</sup> एक अभिव्यक्ति है
 :<math>w = x_{i_1} x_{i_2} \cdots x_{i_n} \ </math>
@@ Line 9: / Line 9: @@
 पूरी तरह से आदेशित वर्णमाला 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
   | journal = Journal of Algorithms | pages = 363–381 | title = एक आदेशित वर्णमाला पर शब्दों का गुणनखंडन करना| volume = 4 | year = 1983}}.</ref>
 == हॉल शब्द ==
 [[हॉल सेट]] एक गुणनखंड प्रदान करता है।<ref name="melancon">
@@ Line 25: / Line 23: @@
 :<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>
 == शुट्ज़ेनबर्गर प्रमेय ==
 यह प्रमेय बताता है कि अनुक्रम X<sub>''i''</sub> ए के सबसेट के<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}}
+* ए का हर तत्व<sup>*</sup> आवश्यक रूप में कम से कम एक अभिव्यक्ति है;
 * ए का हर तत्व<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> = एक्स<sub>''i''</sub>* और एम में सी के तत्व<sub>''i''</sub> एम में संयुग्मी हैं<sub>''i''</sub>.<ref name=L92>Lothaire (1997) p.92</ref>
 == यह भी देखें ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 13:04, 10 June 2023

Contents

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

हॉल शब्द

द्विभाजन

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 13:04, 10 June 2023

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

हॉल शब्द

द्विभाजन

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories