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

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

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

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

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

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

परिभाषाएँ

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

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

Antimatroids की एक औपचारिक भाषा के रूप में एक समकक्ष परिभाषा भी है, जो कि स्ट्रिंग (कंप्यूटर विज्ञान) के एक सेट के रूप में प्रतीकों के परिमित वर्णमाला से परिभाषित है। इस समुच्चय से संबंधित एक स्ट्रिंग को भाषा का शब्द कहा जाता है। एक भाषा ${\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$, एक चिप को प्रत्येक पड़ोसी शीर्ष पर ले जाना। वह घटना जो $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: Convex set, Convex geometry, and Closure operator

अगर ${\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$ इसे एक और बंद सेट बनाने के लिए इसमें जोड़ा जा सकता है। यह संपत्ति एंटीमेट्रोइड्स की पहुंच क्षमता की संपत्ति का पूरक है, और तथ्य यह है कि बंद सेटों के चौराहे बंद हैं संपत्ति के पूरक हैं कि एक एंटीमैट्रोइड में व्यवहार्य सेटों के संघ संभव हैं। इसलिए, किसी भी एंटी-एक्सचेंज क्लोजर के बंद सेट के पूरक एक एंटीमैट्रोइड बनाते हैं।

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

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

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

• विवरण मूल रूप से माना जाता है Dilworth (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$ जाली में।

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

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

कॉक्सेटर समूह के तत्वों पर आंशिक आदेशों को परिभाषित करने की समस्या से प्रेरित होकर, Armstrong (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 \,.$$

अनुप्रयोग

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

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

Parmar (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).