मोनॉइड गुणनखंडन

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

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

हॉल शब्द

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

द्विभाजन

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

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

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

$YX\cup A=X\cup Y\ .$

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

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

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

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

यह भी देखें

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

संदर्भ

• 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