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

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

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

रॉबर्ट पी. दिलवर्थ (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$ को कहा जाता है, और व्यावहारिक समुच्चय जिसमें केवल समापन बिंदु होता है, उसे एंटीमैट्रोइड का पथ कहा जाता है। इस प्रकार पथों के समूह को समुच्चय समावेशन द्वारा आंशिक रूप से आदेशित किया जा सकता है, जिससे एंटीमैट्रोइड का पथ पोसमुच्चय बनता है।

इस प्रकार संभवतः समुच्चय के लिए $S$ एंटीमैट्रोइड में, और हर तत्व $x$ का $S$, किसी का पथ उपसमुच्चय मिल सकता है $S$ जिसके लिए $x$ समापन बिंदु है: ऐसा करने के लिए, के अतिरिक्त अन्य तत्वों को समय में $x$ को हटा देते हैं। जब तक ऐसा कोई निष्कासन संभव उपसमुच्चय नहीं छोड़ता हैं। इसलिए एंटीमेट्रोइड में प्रत्येक व्यावहारिक समुच्चय इसके पथ उपसमुच्चय का संघ है। यदि $S$ पथ नहीं है, इस संघ में प्रत्येक उपसमुच्चय का उचित उपसमुच्चय $S$ है, किन्तु यदि $S$ अपने आप में समापन बिंदु वाला पथ $x$ है, जिसका प्रत्येक उचित उपसमुच्चय $S$ जो एंटीमैट्रोइड से संबंधित है, उसमें $x$ का मान सम्मिलित नहीं होता है, इसलिए, एंटीमेट्रोइड के पथ वास्तव में व्यवहारिक समुच्चय हैं जो उनके उचित व्यावहारिक उपसमुच्चय के संघों के बराबर नहीं हैं। इस प्रकार समतुल्य, समुच्चय का दिया गया समूह ${\mathcal {P}}$ एंटीमैट्रोइड के पथों का समूह बनाता है यदि और केवल यदि, प्रत्येक के लिए $S$ में ${\mathcal {P}}$, के उपसमुच्चय का संघ $S$ में ${\mathcal {P}}$ से कम तत्व है, जो $S$ के लिए अपने आप आ जाता है। यदि ऐसा है तो, ${\mathcal {F}}$ ही के उपसमुच्चय के यूनियनों का समूह ${\mathcal {P}}$ है।

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

उत्तल ज्यामिति

See also: उत्तल सेट, उत्तल ज्यामिति, and क्लोजर ऑपरेटर

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

$${\mathcal {G}}=\{U\setminus S\mid S\in {\mathcal {F}}\}$$

पूरक (समुच्चय सिद्धांत) में समुच्चय करने के लिए ${\mathcal {F}}$ इसे कभी-कभी उत्तल ज्यामिति कहा जाता है और समुच्चय हो जाता है ${\mathcal {G}}$ उत्तल समुच्चय कहलाते हैं। उदाहरण के लिए, शेलिंग एंटीमैट्रोइड में, उत्तल समुच्चय यूक्लिडियन अंतरिक्ष के उत्तल उपसमुच्चय के साथ दिए गए बिंदु समुच्चय के अंतः खण्ड हैं। उत्तल ज्यामिति को परिभाषित करने वाली समुच्चय प्रणाली को अंतखण्ड के नीचे बंद किया जाना चाहिए। किसी भी समुच्चय के लिए $S$ में ${\mathcal {G}}$ वह बराबर नहीं है $U$ तत्व होना चाहिए $x$ अंदर नही $S$ जिसे जोड़ा जा सकता है $S$ और समुच्चय बनाने के लिए ${\mathcal {G}}$ का उपयोग किया जाता हैं।

एक बंद करने वाला ऑपरेटर के संदर्भ में उत्तल ज्यामिति $\tau$ को भी परिभाषित किया जा सकता है, जो किसी भी उपसमुच्चय $U$ को मैप करता है , इसके न्यूनतम बंद सुपरसमुच्चय के लिए निर्धारित किया जाता हैं। क्लोजर ऑपरेटर बनने के लिए, $\tau$ निम्नलिखित गुण होने चाहिए:

• $\tau (\emptyset )=\emptyset$: रिक्त समुच्चय का क्लोजर रिक्त है।
• प्रत्येक उपसमुच्चय के लिए $S$ का $U$, $S$ का उपसमुच्चय $\tau (S)$ और $\tau (S)=\tau {\bigl (}\tau (S){\bigr )}$ हैं।
• जब कभी भी $S\subset T\subset U$, $\tau (S)$ का उपसमुच्चय $\tau (T)$ है।

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

• यदि $S$ का उपसमुच्चय है $U$, और $y$ और $z$ के विशिष्ट तत्व हैं $U$ जिसका संबंध नहीं है $\tau (S)$, किन्तु $z$ का है $\tau (S\cup \{y\})$, तब $y$ का मान $\tau (S\cup \{z\})$ नहीं है।

इस स्वयंसिद्ध को संतुष्ट करने वाले क्लोजर ऑपरेशन को एंटी-एक्सचेंज क्लोजर कहा जाता है। यदि $S$ एंटी-एक्सचेंज क्लोजर में बंद समुच्चय है, तो एंटी-एक्सचेंज स्वयंसिद्ध उन तत्वों पर आंशिक क्रम निर्धारित करता है जो इससे संबंधित नहीं हैं $S$, जहाँ $x\leq y$ आंशिक क्रम में जब $x$ से संबंधित $\tau (S\cup \{y\})$ मान के लिए $x$ इस आंशिक क्रम का न्यूनतम तत्व है, तब $S\cup \{x\}$ बन्द रहता है। अर्थात्, एंटी-एक्सचेंज क्लोजर के बंद समुच्चयों के समूह के पास संपत्ति है कि सार्वभौमिक समुच्चय के अतिरिक्त किसी भी समुच्चय के लिए तत्व है $x$ इसे और बंद समुच्चय बनाने के लिए इसमें जोड़ा जा सकता है। यह संपत्ति एंटीमेट्रोइड्स की पहुंच क्षमता की संपत्ति का पूरक है, और तथ्य यह है कि बंद समुच्चयों के अंतः खण्ड बंद हैं संपत्ति के पूरक हैं कि एंटीमैट्रोइड में व्यावहारिक समुच्चयों के संघ संभव हैं। इसलिए, किसी भी एंटी-एक्सचेंज क्लोजर के बंद समुच्चय के पूरक एंटीमैट्रोइड बनाते हैं।

अप्रत्यक्ष रेखांकन जिसमें उत्तल समुच्चय (उपसमुच्चय के उपसमुच्चय जिसमें उपसमुच्चय में कोने के बीच सभी सबसे छोटे रास्ते होते हैं) उत्तल ज्यामिति बनाते हैं, बिल्कुल टॉलेमिक रेखांकन होते हैं।

ज्वाइन-डिस्ट्रीब्यूटिव लैटिस

एंटीमैट्रोइड के प्रत्येक दो व्यावहारिक समुच्चयों में अद्वितीय कम से कम ऊपरी बाउंड (उनका संघ) और अद्वितीय सबसे बड़ा निचला बाउंड होता है (एंटीमैट्रोइड में समुच्चय का संघ जो दोनों में निहित होता है)। इसलिए, एंटीमैट्रोइड के व्यावहारिक समुच्चय, समुच्चय समावेशन द्वारा आंशिक क्रम, फिल्टर (आदेश) बनाते हैं। एंटीमैट्रोइड की विभिन्न महत्वपूर्ण विशेषताओं की व्याख्या फिल्टर-सैद्धांतिक शब्दों में की जा सकती है; उदाहरण के लिए एंटीमैट्रोइड के पथ फिल्टर (क्रम) #महत्वपूर्ण फिल्टर-सैद्धांतिक धारणाएं हैं। संबंधित फिल्टर के सम्मिलित-अप्रासंगिक तत्व हैं, और एंटीमैट्रोइड के मूल शब्द फिल्टर में अधिकतम श्रृंखलाओं के अनुरूप रहता हैं। इस प्रकार एंटीमैट्रोइड्स से उत्पन्न होने वाली फिल्टर, परिमित वितरण संबंधी फिल्टर को सामान्य करती है, और इसे कई अलग-अलग तरीकों से चित्रित किया जा सकता है।

• विवरण मूल रूप से माना जाता है दिलवर्थ (1940) चिंता फिल्टर (आदेश) महत्वपूर्ण फिल्टर-सैद्धांतिक धारणा पर निर्भर रहता हैं। इस प्रकार प्रत्येक तत्व के लिए $x$ एंटीमैट्रोइड का, अद्वितीय अधिकतम संभव समुच्चय सम्मिलित है $S_{x}$ जिसमें सम्मिलित नहीं है $x$: $S_{x}$ सम्‍मिलित नहीं सभी संभव समुच्चयों के संघ के रूप में निर्मित किया जा सकता है $x$. यह समुच्चय $S_{x}$ स्वचालित रूप से मिलने-अपूरणीय है, जिसका अर्थ है कि यह किसी भी दो बड़े फिल्टर तत्वों का मिलन नहीं है। यह सच है क्योंकि का हर संभव सुपरसमुच्चय $S_{x}$ रोकना $x$, और इसलिए यह संभव सुपरसमुच्चय के हर अंतः खण्ड के बारे में भी सच है। मनमाना फिल्टर के प्रत्येक तत्व को मीट-इरिड्यूसिबल समुच्चय के मिलन के रूप में विघटित किया जा सकता है, प्रायः कई तरीकों से, किन्तु फिल्टर में प्रत्येक तत्व एंटीमैट्रोइड के अनुरूप होता है। $T$ मीट-इरिड्यूसिबल समुच्चय का अनूठा न्यूनतम समूह है जिसका मिलन है $T$; इस समूह में समुच्चय सम्मिलित हैं $S_{x}$ तत्वों के लिए $x$ ऐसा है कि $T\cup \{x\}$ व्यवहारिक रूप से निर्भर करता हैं। अर्थात्, फिल्टर में अद्वितीय मिल-इरेड्यूसबल अपघटन होते हैं।
• एक दूसरा लक्षण वर्णन फिल्टर में अंतरालों की चिंता करता है, फिल्टर तत्वों की जोड़ी द्वारा परिभाषित उप-वर्ग $x\leq y$ सभी फिल्टर तत्वों से मिलकर $z$ साथ $x\leq z\leq y$. अंतराल परमाणु (आदेश सिद्धांत) है यदि इसमें प्रत्येक तत्व परमाणुओं का जुड़ाव है (नीचे के तत्व के ऊपर न्यूनतम तत्व $x$), और यह बूलियन बीजगणित (संरचना) है यदि यह परिमित समुच्चय के सत्ता स्थापित के फिल्टर के लिए आइसोमोर्फिक है। एंटीमैट्रोइड के लिए, प्रत्येक अंतराल जो कि परमाणुवादी है, बूलियन भी है।
• तीसरे, एंटीमैट्रोइड्स से उत्पन्न होने वाली फिल्टर अर्ध-मॉड्यूलर फिल्टर हैं, फिल्टर जो अर्ध-मॉड्यूलर फिल्टर को संतुष्ट करती हैं जो हर दो तत्वों के लिए होती हैं $x$ और $y$, यदि $y$ कवर $x\wedge y$ तब $x\vee y$ कवर $x$. यदि संभव हो तो इस स्थिति को एंटीमैट्रोइड के व्यावहारिक समुच्चय में अनुवाद करना $Y$ केवल तत्व है जो किसी अन्य व्यावहारिक समुच्चय से संबंधित नहीं है $X$ तो उस तत्व को जोड़ा जा सकता है $X$ एंटीमैट्रोइड में और समुच्चय बनाने के लिए। इसके अतिरिक्त, एंटीमैट्रोइड की फिल्टर में मीट-सेमीडिस्ट्रीब्यूशन संपत्ति होती है: सभी फिल्टर तत्वों के लिए $x$, $y$, और $z$, यदि $x\wedge y$ और $x\wedge z$ दूसरे के बराबर तो वे दोनों भी बराबर हैं $x\wedge (y\vee z)$. सेमीमॉड्यूलर और मीट-सेमीडिस्ट्रीब्यूशन लैटिस को जॉइन-डिस्ट्रीब्यूटिव लैटिस कहा जाता है।

ये तीन विशेषताएँ समतुल्य हैं: अद्वितीय मिल-इरेड्यूसिबल अपघटन के साथ किसी भी फिल्टर में बूलियन परमाणु अंतराल होता है और इसमें सम्मिलित-वितरण होता है, बूलियन परमाणु अंतराल के साथ किसी भी फिल्टर में अद्वितीय मिल-इरेड्यूसिबल अपघटन होता है और यह वितरण-वितरण होता है, किसी भी जोड़-वितरण फिल्टर में अद्वितीय होता है मीट-इरेड्यूसिबल अपघटन और बूलियन परमाणु अंतराल। इस प्रकार, हम इन तीन गुणों में से किसी के साथ फिल्टर को जोड़-वितरण के रूप में संदर्भित कर सकते हैं। कोई भी एंटीमैट्रोइड परिमित जॉइन-डिस्ट्रीब्यूटिव फिल्टर को जन्म देता है, और कोई भी परिमित जॉइन-डिस्ट्रीब्यूटिव लैटिस इस तरह से एंटीमैट्रोइड से आता है। इस प्रकार परिमित ज्वाइन-डिस्ट्रीब्यूटिव लैटिस का और समकक्ष लक्षण वर्णन यह है कि वे वर्गीकृत पोसमुच्चय हैं (किसी भी दो अधिकतम श्रृंखलाओं की लंबाई समान है), और अधिकतम श्रृंखला की लंबाई फिल्टर के मिल-इरेड्यूसबल तत्वों की संख्या के बराबर होती है। परिमित जोड़-वितरण फिल्टर का प्रतिनिधित्व करने वाले एंटीमैट्रोइड को फिल्टर से पुनर्प्राप्त किया जा सकता है: एंटीमैट्रॉइड के तत्वों को फिल्टर के मीट-इरिड्यूसिबल तत्वों और किसी भी तत्व के अनुरूप व्यावहारिक समुच्चय के रूप में लिया जा सकता है। $x$ फिल्टर में मिलने-इरेड्यूसबल तत्वों का समुच्चय होता है $y$ ऐसा है कि $y$ से अधिक या बराबर नहीं है $x$ फिल्टर में प्रयोग किया जाता हैं।

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

सुपरसॉल्वेबल एंटीमैट्रोइड्स

कॉक्समुच्चयर समूह के तत्वों पर आंशिक आदेशों को परिभाषित करने की समस्या से प्रेरित होकर, आर्मस्ट्रांग (2009) ने एंटीमैट्रोइड्स का अध्ययन किया जो सुपरसॉल्वेबल लैटिस भी हैं। सुपरसॉल्वेबल एंटीमैट्रोइड को तत्वों के कुल ऑर्डर संग्रह और इन तत्वों के समुच्चय के समूह द्वारा परिभाषित किया गया है। समूह को रिक्त समुच्चय सम्मिलित करना चाहिए। इसके अतिरिक्त, इसमें संपत्ति होनी चाहिए कि यदि दो समुच्चय हो $A$ और $B$ समूह से संबंधित हैं, यदि समुच्चय-सैद्धांतिक अंतर $B\setminus A$ रिक्त नहीं है, और यदि $x$ का सबसे छोटा तत्व है $B\setminus A$, तब $A\cup \{x\}$ समूह का भी है। जैसा कि आर्मस्ट्रांग ने देखा है, इस प्रकार के समुच्चयों का कोई भी समूह एंटीमैट्रोइड बनाता है। आर्मस्ट्रांग एंटीमैट्रोइड्स का फिल्टर-सैद्धांतिक लक्षण वर्णन भी प्रदान करता है जो यह निर्माण बना सकता है।

संचालन और उत्तल आयाम में सम्मिलित हों

यदि ${\mathcal {A}}$ और ${\mathcal {B}}$ दो एंटीमैट्रोइड्स हैं, दोनों को तत्वों के ही ब्रह्मांड पर समुच्चय के समूह के रूप में वर्णित किया गया है, फिर और एंटीमैट्रोइड, का जुड़ाव ${\mathcal {A}}$ और ${\mathcal {B}}$, इस प्रकार बनाया जा सकता है:

$${\mathcal {A}}\vee {\mathcal {B}}=\{S\cup T\mid S\in {\mathcal {A}}\wedge T\in {\mathcal {B}}\}.$$

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

जॉइन क्लोजर ऑपरेशन से निकटता से संबंधित हैं जो औपचारिक भाषाओं को एंटीमैट्रोइड्स में मैप करता है, जहां भाषा ${\mathcal {L}}$ को बंद किया जाता है युक्त सभी एंटीमैट्रोइड्स का प्रतिच्छेदन है ${\mathcal {L}}$ उपभाषा के रूप में। इस क्लोजर ने अपनी व्यावहारिकता के रूप में स्ट्रिंग्स के उपसर्गों के संघों को समुच्चय किया है ${\mathcal {L}}$. इस क्लोजर ऑपरेशन के संदर्भ में, जॉइन की भाषाओं के मिलन का क्लोजर है ${\mathcal {A}}$ और ${\mathcal {B}}$. प्रत्येक एंटीमैट्रोइड को चेन एंटीमैट्रोइड्स के समूह में सम्मिलित होने के रूप में या मूल शब्दों के समुच्चय को बंद करने के रूप में प्रदर्शित किया जा सकता है, एंटीमैट्रोइड का उत्तल आयाम ${\mathcal {A}}$ इस तरह के प्रतिनिधित्व में चेन एंटीमैट्रोइड्स की न्यूनतम संख्या (या समान रूप से मूल शब्दों की न्यूनतम संख्या) है। यदि ${\mathfrak {F}}$ चेन एंटीमेट्रोइड्स का समूह है जिसके मूल शब्द सभी से संबंधित हैं ${\mathcal {A}}$, तब ${\mathfrak {F}}$ उत्पन्न करता है, ${\mathcal {A}}$ यदि व्यावहारिक समुच्चय ${\mathfrak {F}}$ के सभी पथ सम्मिलित करें ${\mathcal {A}}$. के रास्ते ${\mathcal {A}}$ एकल श्रृंखला एंटीमैट्रोइड से संबंधित पथ पोसमुच्चय में श्रृंखला (आदेश सिद्धांत) बनाना चाहिए ${\mathcal {A}}$, इसलिए एंटीमैट्रोइड का उत्तल आयाम पथ पोसमुच्चय को कवर करने के लिए आवश्यक जंजीरों की न्यूनतम संख्या के बराबर होता है, जो दिलवर्थ के प्रमेय द्वारा पथ पोसमुच्चय की चौड़ाई के बराबर होता है।

यदि किसी के पास समुच्चय के बंद होने के रूप में एंटीमेट्रोइड का प्रतिनिधित्व है $d$ मूल शब्द, तो इस प्रतिनिधित्व का उपयोग एंटीमैट्रोइड के संभावित समुच्चयों को इंगित करने के लिए मैप करने के लिए किया जा सकता है $d$-डायमेंशनल यूक्लिडियन स्पेस: प्रति बेसिक शब्द के लिए कोऑर्डिनेट असाइन करें $W$, और व्यावहारिक समुच्चय का समन्वय मान बनाएं $S$ के सबसे लंबे उपसर्ग की लंबाई हो $W$ यह उपसमुच्चय $S$ है। इस एम्बेडिंग के साथ, $S$ अन्य व्यावहारिक समुच्चय का उपसमुच्चय है $T$ यदि और केवल यदि के लिए निर्देशांक $S$ सभी के संगत निर्देशांक से कम या उसके बराबर हैं $T$. इसलिए, व्यावहारिक समुच्चयों के समावेशन क्रम का क्रम आयाम एंटीमैट्रोइड के उत्तल आयाम के बराबर है। चूंकि, सामान्यतः ये दो आयाम बहुत भिन्न हो सकते हैं: आदेश आयाम तीन के साथ एंटीमैट्रोइड्स सम्मिलित हैं किन्तु मनमाने ढंग से बड़े उत्तल आयाम के साथ उपलब्ध रहता हैं।

गणना

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

$$1,3,22,485,59386,133059751,\dots \,.$$

अनुप्रयोग

सैद्धांतिक शेड्यूलिंग समस्याओं के लिए मानक संकेतन में पूर्वता और रिलीज समय की कमी दोनों को एंटीमैट्रोइड्स द्वारा प्रतिरूपित किया जा सकता है। बॉयड & फैगल (1990) यूजीन लॉलर के लालची एल्गोरिदम को सामान्यीकृत करने के लिए एंटीमैट्रोइड्स का उपयोग प्राथमिकता बाधाओं के साथ एकल-प्रोसेसर शेड्यूलिंग समस्याओं को उत्तम ढंग से हल करने के लिए करता है, जिसमें लक्ष्य किसी कार्य के देर से शेड्यूलिंग द्वारा किए गए अधिकतम दंड को कम करना है।

ग्लासमैन & याओ (1994) असतत घटना सिमुलेशन सिस्टम में घटनाओं के क्रम को मॉडल करने के लिए एंटीमैट्रोइड्स का उपयोग करते हैं।

परमार (2003) आर्टिफिशियल इंटेलिजेंस स्वचालित योजना और शेड्यूलिंग समस्याओं में लक्ष्य की दिशा में प्रगति को मॉडल करने के लिए एंटीमैट्रोइड्स का उपयोग करता है।

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

गणितीय मनोविज्ञान में, मानव शिक्षार्थी के ज्ञान स्थान का वर्णन करने के लिए एंटीमैट्रोइड्स का उपयोग किया गया है। एंटीमैट्रोइड का प्रत्येक तत्व अवधारणा का प्रतिनिधित्व करता है जिसे शिक्षार्थी द्वारा समझा जाना है, या समस्याओं का वर्ग जिसे वह सही ढंग से हल करने में सक्षम हो सकता है, और एंटीमेट्रोइड बनाने वाले तत्वों के समुच्चय उन अवधारणाओं के संभावित समुच्चय का प्रतिनिधित्व करते हैं जो हो सकते हैं व्यक्ति द्वारा समझा जाता हैं। एंटीमेट्रोइड को परिभाषित करने वाले सिद्धांतों को अनौपचारिक रूप से कहा जा सकता है कि अवधारणा को सीखने से शिक्षार्थी को दूसरी अवधारणा को सीखने से रोका नहीं जा सकता है, और समय में ही अवधारणा को सीखकर ज्ञान की किसी भी व्यावहारिक स्थिति तक पहुंचा जा सकता है। ज्ञान मूल्यांकन प्रणाली का कार्य किसी दिए गए शिक्षार्थी द्वारा ज्ञात अवधारणाओं के समुच्चय का अनुमान लगाना है, जो समस्याओं के छोटे और अच्छी तरह से चुने गए समुच्चय पर उसकी प्रतिक्रियाओं का विश्लेषण करता है। इस संदर्भ में एंटीमैट्रोइड्स को सीखने के स्थान और अच्छी तरह से वर्गीकृत ज्ञान स्थान भी कहा जाता है।

संदर्भ

• Adaricheva, K. V.; Gorbunov, V. A.; Tumanov, V. I. (2003), "Join-semidistributive lattices and convex geometries", Advances in Mathematics, 173 (1): 1–49, doi:10.1016/S0001-8708(02)00011-7.
• Armstrong, Drew (2009), "The sorting order on a Coxeter group", Journal of Combinatorial Theory, Series A, 116 (8): 1285–1305, arXiv:0712.1047, doi:10.1016/j.jcta.2009.03.009, MR 2568800, S2CID 15474840.
• Birkhoff, Garrett; Bennett, M. K. (1985), "The convexity lattice of a poset", Order, 2 (3): 223–242, doi:10.1007/BF00333128, S2CID 118907732
• Björner, Anders; Lovász, László; Shor, Peter W. (1991), "Chip-firing games on graphs", European Journal of Combinatorics, 12 (4): 283–291, doi:10.1016/S0195-6698(13)80111-4, MR 1120415
• Björner, Anders; Ziegler, Günter M. (1992), "Introduction to greedoids", in White, Neil (ed.), Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge University Press, pp. 284–357, doi:10.1017/CBO9780511662041.009, ISBN 0-521-38165-7, MR 1165537
• Boyd, E. Andrew; Faigle, Ulrich (1990), "An algorithmic characterization of antimatroids", Discrete Applied Mathematics, 28 (3): 197–205, doi:10.1016/0166-218X(90)90002-T, hdl:1911/101636.
• Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003), "Generating and characterizing the perfect elimination orderings of a chordal graph" (PDF), Theoretical Computer Science, 307 (2): 303–317, doi:10.1016/S0304-3975(03)00221-4
• Dilworth, Robert P. (1940), "Lattices with unique irreducible decompositions", Annals of Mathematics, 41 (4): 771–777, doi:10.2307/1968857, JSTOR 1968857.
• Doignon, Jean-Paul; Falmagne, Jean-Claude (1999), Knowledge Spaces, Springer-Verlag, ISBN 3-540-64501-2.
• Edelman, Paul H. (1980), "Meet-distributive lattices and the anti-exchange closure", Algebra Universalis, 10 (1): 290–299, doi:10.1007/BF02482912, S2CID 120403229.
• Edelman, Paul H.; Saks, Michael E. (1988), "Combinatorial representation and convex dimension of convex geometries", Order, 5 (1): 23–32, doi:10.1007/BF00143895, S2CID 119826035.
• Eppstein, David (2008), Learning sequences, arXiv:0803.4030. Partially adapted as Chapters 13 and 14 of Falmagne, Jean-Claude; Albert, Dietrich; Doble, Chris; Eppstein, David; Hu, Xiangen, eds. (2013), Knowledge Spaces: Applications in Education, Springer-Verlag, doi:10.1007/978-3-642-35329-1, ISBN 978-3-642-35328-4.
• Farber, Martin; Jamison, Robert E. (1986), "Convexity in graphs and hypergraphs", SIAM Journal on Algebraic and Discrete Methods, 7 (3): 433–444, doi:10.1137/0607049, hdl:10338.dmlcz/127659, MR 0844046.
• Glasserman, Paul; Yao, David D. (1994), Monotone Structure in Discrete Event Systems, Wiley Series in Probability and Statistics, Wiley Interscience, ISBN 978-0-471-58041-6.
• Gordon, Gary (1997), "A β invariant for greedoids and antimatroids", Electronic Journal of Combinatorics, 4 (1): Research Paper 13, doi:10.37236/1298, MR 1445628.
• Jamison, Robert (1980), "Copoints in antimatroids", Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. II, Congressus Numerantium, vol. 29, pp. 535–544, MR 0608454.
• Kashiwabara, Kenji; Nakamura, Masataka; Okamoto, Yoshio (2005), "The affine representation theorem for abstract convex geometries", Computational Geometry, 30 (2): 129–144, CiteSeerX 10.1.1.14.4965, doi:10.1016/j.comgeo.2004.05.001, MR 2107032.
• Kempner, Yulia; Levit, Vadim E. (2003), "Correspondence between two antimatroid algorithmic characterizations", Electronic Journal of Combinatorics, 10: Research Paper 44, arXiv:math/0307013, Bibcode:2003math......7013K, doi:10.37236/1737, MR 2014531, S2CID 11015967
• Knauer, Kolja (2009), "Chip-firing, antimatroids, and polyhedra", European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electronic Notes in Discrete Mathematics, vol. 34, pp. 9–13, doi:10.1016/j.endm.2009.07.002, MR 2591410
• Korte, Bernhard; Lovász, László; Schrader, Rainer (1991), Greedoids, Springer-Verlag, pp. 19–43, ISBN 3-540-18190-3.
• Merchant, Nazarré; Riggle, Jason (2016), "OT grammars, beyond partial orders: ERC sets and antimatroids", Natural Language & Linguistic Theory, 34: 241–269, doi:10.1007/s11049-015-9297-5, S2CID 170567540.
• Monjardet, Bernard (1985), "A use for frequently rediscovering a concept", Order, 1 (4): 415–417, doi:10.1007/BF00582748, S2CID 119378521.
• Parmar, Aarati (2003), "Some Mathematical Structures Underlying Efficient Planning", AAAI Spring Symposium on Logical Formalization of Commonsense Reasoning (PDF).