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

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

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

हॉल शब्द

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

द्विभाजन

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

उदाहरण:

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

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

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

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

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

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

• A^* का हर तत्व आवश्यक रूप में कम से कम एक अभिव्यक्ति है;
• A^* का हर तत्व में आवश्यक रूप में अधिकतम एक अभिव्यक्ति है;
• प्रत्येक संयुग्म वर्ग C केवल एक मोनोइड M_i = X_i* से मिलता है और M_i में C के तत्व M_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