एंटीमैट्रोइड

एक एंटीमेट्रोइड के तीन विचार: व्यावहारिक समुच्चयों के अपने समूह पर समावेशन आदेश, औपचारिक भाषा और संबंधित पथ पोसमुच्चय।

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

रॉबर्ट पी. दिलवर्थ (1940) फिन्टर (आदेश) पर आधारित और स्व सत्यापन का उपयोग करते हुए एंटीमेट्रोइड्स का अध्ययन करने वाले पहले व्यक्ति थे, इस प्रकार उन्हें प्रायः अन्य संदर्भों में फिर से खोजा गया है।

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

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

एंटीमैट्रोइड्स समतुल्य हैं, पूरक (समुच्चय थ्योरी) द्वारा, 'उत्तल ज्यामिति' के लिए, ज्यामिति में उत्तल समुच्चयों का संयोजी रूप हैं।

जॉब शॉप शेड्यूलिंग, सिमुलेशन में संभावित घटना क्रम, कृत्रिम होशियारी में टास्क प्लानिंग और मानव शिक्षार्थियों के ज्ञान की अवस्थाओं में मॉडल पूर्ववर्ती बाधाओं के लिए एंटीमैट्रोइड्स लागू किए गए हैं।

परिभाषाएँ

एक एंटीमैट्रोइड को परिमित समूह ${\mathcal {F}}$के रूप में परिभाषित किया जा सकता है , इस प्रकार निम्नलिखित दो गुणों के साथ, परिमित समुच्चय, जिसे व्यावहारिक समुच्चय कहा जाता है:

• किसी भी दो संभव समुच्चयों का संघ (समुच्चय सिद्धांत) भी संभव है। वह ${\mathcal {F}}$ है जो यूनियनों के अनुसार क्लोजर (गणित) करता है।
• यदि $S$ गैर-रिक्त संभव समुच्चय है, तो $S$ तत्व होता है $x$ जिसके लिए $S\setminus \{x\}$ (हटाने से गठित समुच्चय $x$ से $S$) भी संभव है। वह ${\mathcal {F}}$ है जो सुलभ समुच्चय प्रणाली प्रकट करता हैं।

एंटीमैट्रोइड्स की औपचारिक भाषा के रूप में समकक्ष परिभाषा भी है, जो कि स्ट्रिंग (कंप्यूटर विज्ञान) के समुच्चय के रूप में प्रतीकों के परिमित वर्णमाला से परिभाषित है। इस समुच्चय से संबंधित स्ट्रिंग को भाषा का शब्द कहा जाता है। भाषा ${\mathcal {L}}$ एंटीमैट्रोइड को परिभाषित करने से निम्नलिखित गुणों को पूरा करना चाहिए:

• वर्णमाला का प्रत्येक प्रतीक ${\mathcal {L}}$ द्वारा कम से कम शब्द में प्रकट करता है।
• इसका प्रत्येक शब्द ${\mathcal {L}}$ प्रत्येक प्रतीक की अधिकतम प्रति सम्मिलित है। इस गुण वाली भाषा को सामान्य कहा जाता है।
• प्रत्येक उपसर्ग (कंप्यूटर विज्ञान) शब्द में ${\mathcal {L}}$ में भी है ${\mathcal {L}}$. इस संपत्ति वाली भाषा को वंशानुगत कहा जाता है।
• यदि $S$ और $T$ में शब्द हैं ${\mathcal {L}}$, और $S$ कम से कम प्रतीक है जो $T$ के अंदर नहीं है, तो प्रतीक $x$ में $S$ है जो इस प्रकार हैं कि संघ $Tx$ में और शब्द ${\mathcal {L}}$ है।

परिभाषा के इन दो रूपों की समानता को निम्नानुसार देखा जा सकता है। यदि ${\mathcal {L}}$ औपचारिक भाषा के रूप में परिभाषित एंटीमेट्रोइड है, फिर शब्दों के प्रतीकों का समुच्चय ${\mathcal {L}}$ सुलभ संघ-बंद समुच्चय सिस्टम के रूप में बनाया जाता हैं। इस प्रकार यह स्ट्रिंग्स की वंशानुगत संपत्ति द्वारा सुलभ है, और इसे स्ट्रिंग्स के संयोजन गुण के बार-बार उपयोग द्वारा संघ-बंद दिखाया जा सकता है। इस प्रकार दूसरी दिशा में, सुलभ संघ-बंद समुच्चय प्रणाली से ${\mathcal {F}}$, सामान्य स्ट्रिंग्स की भाषा जिसके सभी उपसर्गों से संबंधित ${\mathcal {F}}$ प्रतीकों के समुच्चय होते हैं, औपचारिक भाषा के लिए एंटीमेट्रोइड होने की आवश्यकताओं को पूरा करता है। ये दो परिवर्तन दूसरे के प्रतिलोम हैं: औपचारिक भाषा को निर्धारित समूह में बदलना और इसके विपरीत, ही प्रणाली का निर्माण करता है। इस प्रकार, ये दो परिभाषाएँ गणितीय रूप से वस्तुओं के समतुल्य वर्गों की ओर ले जाती हैं।

उदाहरण

प्लानर पॉइंट समुच्चय का गोलाबारी क्रम में रहते हैं। कुछ बिंदुओं को हटा दिए जाने के बाद रेखा खंड उत्तल पतवार के किनारों को दिखाते हैं।

निम्नलिखित प्रणालियाँ एंटीमैट्रोइड्स के उदाहरण प्रदान करती हैं:

चेन एंटीमैट्रोइड्स

एकल स्ट्रिंग के उपसर्ग, और इन उपसर्गों में प्रतीकों के समुच्चय, एंटीमैट्रोइड बनाते हैं। उदाहरण के लिए स्ट्रिंग द्वारा परिभाषित चेन एंटीमैट्रोइड $abcd$ इसकी औपचारिक भाषा के रूप में स्ट्रिंग्स का समुच्चय है

$$\{\varepsilon ,a,ab,abc,abcd\}$$

(जहाँ $\varepsilon$ रिक्त स्ट्रिंग को दर्शाता है) और जैसा कि संभव है इसका समूह समूह को समुच्चय करता है

$${\bigl \{}\emptyset ,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}{\bigr \}}.$$

पोसमुच्चय एंटीमैट्रोइड्स

एक परिमित आंशिक रूप से आदेशित समुच्चय के निचले समुच्चय एंटीमैट्रोइड बनाते हैं, जिसमें एंटीमैट्रोइड के पूर्ण-लंबाई वाले शब्द आंशिक क्रम के रैखिक एक्सटेंशन बनाते हैं। इस प्रकार बिरखॉफ के वितरण प्रमेय द्वारा वितरण फिल्टर के लिए, पॉसमुच्चय एंटीमेट्रॉइड (समुच्चय समावेशन द्वारा आदेशित) में व्यावहारिक समुच्चय वितरण फिल्टर बनाते हैं, और इस प्रकार सभी वितरण फिल्टर इस प्रकार से बन सकते हैं। इस प्रकार, एंटीमैट्रोइड्स को वितरणात्मक लैटिस के सामान्यीकरण के रूप में देखा जा सकता है। इस प्रकार चेन एंटीमैट्रोइड कुल ऑर्डर के लिए पोसमुच्चय एंटीमैट्रोइड का विशेष स्थिति है।

शेलिंग एंटीमैट्रोइड्स

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

सही निष्कासन

कॉर्डल ग्राफ का पूर्ण विलोपन क्रम उसके शीर्षों का ऐसा क्रम है, जो प्रत्येक शीर्ष के लिए होता है $v$, के पड़ोसी $v$ जो बाद में $v$ ऑर्डरिंग फॉर्म में गुट (ग्राफ सिद्धांत) होता है। इस प्रकार कॉर्डल ग्राफ के पूर्ण उन्मूलन क्रम के उपसर्ग एंटीमैट्रोइड बनाते हैं।

चिप फायरिंग

चिप-फायरिंग गेम जैसे कि एबेलियन सैंडपाइल मॉडल को निर्देशित ग्राफ द्वारा परिभाषित किया जाता है, साथ ही इसके शीर्ष पर चिप्स की प्रणाली होती है। जब भी शीर्ष पर चिप्स की संख्या $v$ कम से कम उतना बड़ा है जितना कि किनारों की संख्या $v$, फायर करना संभव है, इस प्रकार चिप को प्रत्येक पड़ोसी शीर्ष पर ले जाना संभव रहता हैं। वह घटना जो $v$ के लिए आग $i$वें समय केवल तभी हो सकता है जब यह पहले से ही निकाल दिया गया हो $i-1$ बार और संचित $i\cdot \deg(v)$ कुल चिप्स पर निर्भर करता हैं। ये स्थितियाँ पिछली फायरिंग के आदेश पर निर्भर नहीं करती हैं, और तब तक सही रहती हैं $v$ आग, इसलिए किसी दिए गए ग्राफ और चिप्स की प्रारंभिक नियुक्ति जिसके लिए सिस्टम समाप्त हो जाता है, इस प्रकार जोड़े पर एंटीमैट्रोइड $(v,i)$ को परिभाषित करता है, इन प्रणालियों की एंटीमैट्रोइड संपत्ति का परिणाम यह है कि, किसी दिए गए प्रारंभिक राज्य के लिए, प्रत्येक वर्टेक्स की आग की संख्या और इस प्रणाली की अंतिम स्थिर स्थिति फायरिंग ऑर्डर पर निर्भर नहीं होती है।

पथ और मूल शब्द

एक एंटीमैट्रोइड के समुच्चय थ्योरिटिक स्वयंसिद्धीकरण में कुछ विशेष समुच्चय होते हैं जिन्हें पथ कहा जाता है जो पूरे एंटीमैट्रोइड को निर्धारित करते हैं, इस अर्थ में कि एंटीमैट्रोइड के समुच्चय वास्तव में पथों के संघ हैं। यदि $S$ एंटीमैट्रोइड, तत्व का कोई व्यावहारिक समुच्चय है $x$ जिससे $S$ को हटाया जा सकता है और संभव समुच्चय बनाने के लिए समापन बिंदु $S$ को कहा जाता है, �