मोनॉइड गुणनखंडन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
गणित में, एक मुक्त मोनॉइड का गुणनखंड शब्दों के [[सबसेट]] का एक अनुक्रम है, जिसमें गुण के साथ मुक्त मोनॉइड में प्रत्येक शब्द को उपसमुच्चय से खींचे गए तत्वों के संयोजन के रूप में लिखा जा सकता है। चेन-[[राल्फ फॉक्स]]-[[रोजर लिंडन]] प्रमेय कहता है कि [[लिंडन शब्द]] एक गुणनखंड प्रस्तुत करते हैं। मार्सेल शुत्जेनबर्गर प्रमेय एक गुणात्मक गुण के संदर्भ में परिभाषा को एक योगात्मक गुण से संबंधित करता है। | गणित में, एक मुक्त मोनॉइड का गुणनखंड शब्दों के [[सबसेट]] का एक अनुक्रम है, जिसमें गुण के साथ मुक्त मोनॉइड में प्रत्येक शब्द को उपसमुच्चय से खींचे गए तत्वों के संयोजन के रूप में लिखा जा सकता है। चेन-[[राल्फ फॉक्स]]-[[रोजर लिंडन]] प्रमेय कहता है कि [[लिंडन शब्द]] एक गुणनखंड प्रस्तुत करते हैं। मार्सेल शुत्जेनबर्गर प्रमेय एक गुणात्मक गुण के संदर्भ में परिभाषा को एक योगात्मक गुण से संबंधित करता है। | ||
चलो A* अक्षर A पर मुक्त मोनॉइड है। मान लीजिए X<sub>''i''</sub> A* के उपसमुच्चय का अनुक्रम है, एक पूरी तरह से व्यवस्थित सेट [[ सूचकांक सेट |सूचकांक सेट]] I द्वारा अनुक्रमित। A* | चलो A* अक्षर A पर मुक्त मोनॉइड है। मान लीजिए X<sub>''i''</sub> A* के उपसमुच्चय का अनुक्रम है, एक पूरी तरह से व्यवस्थित सेट [[ सूचकांक सेट |सूचकांक सेट]] I द्वारा अनुक्रमित। A* में एक शब्द w का गुणनखंड<sup>*</sup> एक अभिव्यक्ति है | ||
:<math>w = x_{i_1} x_{i_2} \cdots x_{i_n} \ </math> | :<math>w = x_{i_1} x_{i_2} \cdots x_{i_n} \ </math> | ||
| Line 7: | Line 7: | ||
== चेन-फॉक्स-लिंडन प्रमेय == | == चेन-फॉक्स-लिंडन प्रमेय == | ||
पूरी तरह से आदेशित वर्णमाला A पर एक लिंडन शब्द एक ऐसा शब्द है जो अपने सभी घुमावों से कम [[लेक्सिकोग्राफिक ऑर्डर]] है।<ref name=L64>Lothaire (1997) p.64</ref> चेन-फॉक्स-लिंडन प्रमेय कहता है कि लिंडन शब्दों के एक गैर-बढ़ते अनुक्रम को जोड़कर प्रत्येक स्ट्रिंग को एक अनूठे विधि | पूरी तरह से आदेशित वर्णमाला 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> | | journal = Journal of Algorithms | pages = 363–381 | title = एक आदेशित वर्णमाला पर शब्दों का गुणनखंडन करना| volume = 4 | year = 1983}}.</ref> | ||
== हॉल शब्द == | == हॉल शब्द == | ||
| Line 15: | Line 15: | ||
== द्विभाजन == | == द्विभाजन == | ||
एक मुक्त मोनॉइड का द्विभाजन केवल दो वर्गों ''X''<sub>0</sub>, ''X''<sub>1</sub> | एक मुक्त मोनॉइड का द्विभाजन केवल दो वर्गों ''X''<sub>0</sub>, ''X''<sub>1</sub> के साथ एक गुणनखंड है।<ref name="L68">Lothaire (1997) p.68</ref> | ||
उदाहरण: | उदाहरण: | ||
| Line 22: | Line 22: | ||
यदि एक्स, वाई गैर-रिक्त शब्दों के असम्बद्ध सेट हैं, तो (''X'',''Y'') ''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> | :<math>YX \cup A = X \cup Y \ . </math> | ||
परिणामस्वरूप,''A''<sup>+</sup> के किसी भी विभाजन P, Q के लिए एक अद्वितीय समद्विभाजन (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> | यह प्रमेय बताता है कि अनुक्रम X<sub>''i''</sub> ''A''<sup>*</sup> के सबसेट के एक गुणनखण्ड बनाता है यदि और केवल यदि निम्नलिखित तीन कथनों में से दो कथन धारण करते हैं: | ||
* ''A''<sup>*</sup> का हर तत्व आवश्यक रूप में कम से कम एक अभिव्यक्ति है; | * ''A''<sup>*</sup> का हर तत्व आवश्यक रूप में कम से कम एक अभिव्यक्ति है; | ||
* ''A''<sup>*</sup> का हर तत्व में आवश्यक रूप में अधिकतम एक अभिव्यक्ति है; | * ''A''<sup>*</sup> का हर तत्व में आवश्यक रूप में अधिकतम एक अभिव्यक्ति है; | ||
* प्रत्येक संयुग्म वर्ग C केवल एक [[मोनोइड]] ''M<sub>i</sub>'' = ''X<sub>i</sub>''* से मिलता है और ''M<sub>i</sub>'' | * प्रत्येक संयुग्म वर्ग 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> | ||
'''गैर-बढ़ते अनुक्रम को जोड़कर प्रत्येक स्ट्रिंग को एक अनूठे विधि | '''गैर-बढ़ते अनुक्रम को जोड़कर प्रत्येक स्ट्रिंग को एक अनूठे विधि से बनाया जा सकता''' | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 13:14, 10 June 2023
गणित में, एक मुक्त मोनॉइड का गुणनखंड शब्दों के सबसेट का एक अनुक्रम है, जिसमें गुण के साथ मुक्त मोनॉइड में प्रत्येक शब्द को उपसमुच्चय से खींचे गए तत्वों के संयोजन के रूप में लिखा जा सकता है। चेन-राल्फ फॉक्स-रोजर लिंडन प्रमेय कहता है कि लिंडन शब्द एक गुणनखंड प्रस्तुत करते हैं। मार्सेल शुत्जेनबर्गर प्रमेय एक गुणात्मक गुण के संदर्भ में परिभाषा को एक योगात्मक गुण से संबंधित करता है।
चलो A* अक्षर A पर मुक्त मोनॉइड है। मान लीजिए Xi A* के उपसमुच्चय का अनुक्रम है, एक पूरी तरह से व्यवस्थित सेट सूचकांक सेट I द्वारा अनुक्रमित। A* में एक शब्द w का गुणनखंड* एक अभिव्यक्ति है
साथ और . कुछ लेखक असमानताओं के क्रम को विपरीत कर देते हैं।
चेन-फॉक्स-लिंडन प्रमेय
पूरी तरह से आदेशित वर्णमाला A पर एक लिंडन शब्द एक ऐसा शब्द है जो अपने सभी घुमावों से कम लेक्सिकोग्राफिक ऑर्डर है।[1] चेन-फॉक्स-लिंडन प्रमेय कहता है कि लिंडन शब्दों के एक गैर-बढ़ते अनुक्रम को जोड़कर प्रत्येक स्ट्रिंग को एक अनूठे विधि से बनाया जा सकता है। इसलिए 'Xl प्रत्येक लिंडन शब्द l के लिए सिंगलटन सेट {l} होने के लिए, लिंडन शब्दों के सूचकांक सेट L के साथ लेक्सिकोग्राफिक रूप से आदेशित, हम A * का एक कारक प्राप्त करते हैं.[2] ऐसा गुणनखण्ड रैखिक समय में पाया जा सकता है।[3]
हॉल शब्द
हॉल सेट एक गुणनखंड प्रदान करता है।[4] वास्तव में लिंडन शब्द हॉल शब्द का एक विशेष स्थिति है। हॉल वर्ड्स पर लेख इस गुणनखंड के प्रमाण को स्थापित करने के लिए आवश्यक सभी तंत्रों का एक रेखाचित्र प्रदान करता है।
द्विभाजन
एक मुक्त मोनॉइड का द्विभाजन केवल दो वर्गों X0, X1 के साथ एक गुणनखंड है।[5]
उदाहरण:
- A = {a,b}, X0 = {a*b}, X1 = {a}.
यदि एक्स, वाई गैर-रिक्त शब्दों के असम्बद्ध सेट हैं, तो (X,Y) A* का एक समद्विभाजन है यदि और केवल यदि[6]
परिणामस्वरूप,A+ के किसी भी विभाजन P, Q के लिए एक अद्वितीय समद्विभाजन (X,Y) होता है जिसमें X, P का एक उपसमुच्चय और Y, Q का एक उपसमुच्चय होता है।[7]
शुट्ज़ेनबर्गर प्रमेय
यह प्रमेय बताता है कि अनुक्रम Xi A* के सबसेट के एक गुणनखण्ड बनाता है यदि और केवल यदि निम्नलिखित तीन कथनों में से दो कथन धारण करते हैं:
- A* का हर तत्व आवश्यक रूप में कम से कम एक अभिव्यक्ति है;
- A* का हर तत्व में आवश्यक रूप में अधिकतम एक अभिव्यक्ति है;
- प्रत्येक संयुग्म वर्ग C केवल एक मोनोइड Mi = Xi* से मिलता है और Mi में C के तत्व Mi में संयुग्मी हैं.[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
