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

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

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

रॉबर्ट पी. दिलवर्थ (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$, चिप को प्रत्येक पड़ोसी शीर्ष पर ले जाना। वह घटना जो $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).