एंटीमैट्रोइड: Difference between revisions

Revision as of 23:02, 13 March 2023

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

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

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

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

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

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

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

परिभाषाएँ

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

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

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

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

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

उदाहरण

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

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

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

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

abcd

इसकी औपचारिक भाषा के रूप में स्ट्रिंग्स का समुच्चय है

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

(जहाँ

\varepsilon

रिक्त स्ट्रिंग को दर्शाता है) और जैसा कि संभव है इसका समूह समूह को समुच्चय करता है^[7]

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

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

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

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

परिमित समुच्चय का गोलाबारी क्रम

U

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

U

उत्तल समुच्चय के पूरक (समुच्चय सिद्धांत) के साथ उपयोग किया जाता हैं।^[7] इस प्रकार प्रत्येक एंटीमैट्रोइड पर्याप्त उच्च-आयामी अंतरिक्ष में बिंदुओं के शेलिंग एंटीमैट्रोइड के लिए आइसोमोर्फिक है।^[9]

सही निष्कासन

कॉर्डल ग्राफ का पूर्ण विलोपन क्रम उसके शीर्षों का ऐसा क्रम है, जो प्रत्येक शीर्ष के लिए होता है

v

, के पड़ोसी

v

जो बाद में

v

ऑर्डरिंग फॉर्म में गुट (ग्राफ सिद्धांत) होता है। इस प्रकार कॉर्डल ग्राफ के पूर्ण उन्मूलन क्रम के उपसर्ग एंटीमैट्रोइड बनाते हैं।^[10]

चिप फायरिंग

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

v

कम से कम उतना बड़ा है जितना कि किनारों की संख्या

v

, फायर करना संभव है, इस प्रकार चिप को प्रत्येक पड़ोसी शीर्ष पर ले जाना संभव रहता हैं। वह घटना जो

v

के लिए आग

i

वें समय केवल तभी हो सकता है जब यह पहले से ही निकाल दिया गया हो

i-1

बार और संचित

i\cdot \deg(v)

कुल चिप्स पर निर्भर करता हैं। ये स्थितियाँ पिछली फायरिंग के आदेश पर निर्भर नहीं करती हैं, और तब तक सही रहती हैं

v

आग, इसलिए किसी दिए गए ग्राफ और चिप्स की प्रारंभिक नियुक्ति जिसके लिए सिस्टम समाप्त हो जाता है, इस प्रकार जोड़े पर एंटीमैट्रोइड

(v,i)

को परिभाषित करता है, इन प्रणालियों की एंटीमैट्रोइड संपत्ति का परिणाम यह है कि, किसी दिए गए प्रारंभिक राज्य के लिए, प्रत्येक वर्टेक्स की आग की संख्या और इस प्रणाली की अंतिम स्थिर स्थिति फायरिंग ऑर्डर पर निर्भर नहीं होती है।^[11]

पथ और मूल शब्द

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

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

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

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

यदि ${\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}}

का उपयोग किया जाता हैं।^[18]

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

$\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\})$ नहीं है।^[19]

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

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

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

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

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

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

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

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

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

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

यदि ${\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}}\}.

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

जॉइन क्लोजर ऑपरेशन से निकटता से संबंधित हैं जो औपचारिक भाषाओं को एंटीमैट्रोइड्स में मैप करता है, जहां भाषा ${\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}}$ , इसलिए एंटीमैट्रोइड का उत्तल आयाम पथ पोसमुच्चय को कवर करने के लिए आवश्यक जंजीरों की न्यूनतम संख्या के बराबर होता है, जो दिलवर्थ के प्रमेय द्वारा पथ पोसमुच्चय की चौड़ाई के बराबर होता है।^[26]

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

गणना

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

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

अनुप्रयोग

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

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

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

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

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

↑ See Korte, Lovász & Schrader (1991) for a comprehensive survey of antimatroid theory with many additional references.
↑ Two early references are Edelman (1980) and Jamison (1980); Jamison was the first to use the term "antimatroid". Monjardet (1985) surveys the history of rediscovery of antimatroids.
↑ See e.g. Kempner & Levit (2003), Definition 2.1 and Proposition 2.3, p. 2.
↑ Korte, Lovász & Schrader (1991), p. 22.
↑ ^5.0 ^5.1 Korte, Lovász & Schrader (1991), p. 5.
↑ Korte, Lovász & Schrader (1991), Theorem 1.4, p. 24.
↑ ^7.0 ^7.1 ^7.2 Gordon (1997).
↑ Korte, Lovász & Schrader (1991), pp. 24–25.
↑ Kashiwabara, Nakamura & Okamoto (2005).
↑ Gordon (1997) describes several results related to antimatroids of this type, but these antimatroids were mentioned earlier e.g. by Korte, Lovász & Schrader (1991). Chandran et al. (2003) use the connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.
↑ Björner, Lovász & Shor (1991); Knauer (2009).
↑ ^12.0 ^12.1 ^12.2 Korte, Lovász & Schrader (1991), Lemma 3.12, p. 31.
↑ Korte, Lovász & Schrader (1991), p. 31.
↑ Korte, Lovász & Schrader (1991), pp. 39–43.
↑ See Korte, Lovász & Schrader (1991), Theorem 3.13, p. 32, which defines paths as rooted sets, sets with a distinguished element, and states an equivalent characterization on the families of rooted sets that form the paths of antimatroids.
↑ Korte, Lovász & Schrader (1991), pp. 6, 22.
↑ See Korte, Lovász & Schrader (1991), p. 22: "any word in an antimatroid can be extended to a basic word".
↑ ^18.0 ^18.1 Korte, Lovász & Schrader (1991), Theorem 1.1, p. 21.
↑ ^19.0 ^19.1 Korte, Lovász & Schrader (1991), p. 20.
↑ Farber & Jamison (1986).
↑ Adaricheva, Gorbunov & Tumanov (2003), Theorems 1.7 and 1.9; Armstrong (2009), Theorem 2.7.
↑ Edelman (1980), Theorem 3.3; Armstrong (2009), Theorem 2.8.
↑ Monjardet (1985) credits a dual form of this characterization to several papers from the 1960s by S. P. Avann.
↑ Armstrong (2009).
↑ Korte, Lovász & Schrader (1991), p. 42; Eppstein (2008), Section 7.2; Falmagne et al. (2013), section 14.4.
↑ Edelman & Saks (1988); Korte, Lovász & Schrader (1991), Theorem 6.9.
↑ Korte, Lovász & Schrader (1991), Corollary 6.10.
↑ Eppstein (2008), Figure 15.
↑ Sloane, N. J. A. (ed.), "Sequence A119770", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
↑ Merchant & Riggle (2016).
↑ Doignon & Falmagne (1999).

संदर्भ

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

[1] See Korte, Lovász & Schrader (1991) for a comprehensive survey of antimatroid theory with many additional references.

[2] Two early references are Edelman (1980) and Jamison (1980); Jamison was the first to use the term "antimatroid". Monjardet (1985) surveys the history of rediscovery of antimatroids.

[3] See e.g. Kempner & Levit (2003), Definition 2.1 and Proposition 2.3, p. 2.

[FOOTNOTEKorteLovászSchrader199122-4] Korte, Lovász & Schrader (1991), p. 22.

[FOOTNOTEKorteLovászSchrader19915-5] 5.0 ^5.1 Korte, Lovász & Schrader (1991), p. 5.

[FOOTNOTEKorteLovászSchrader1991Theorem_1.4,_p._24-6] Korte, Lovász & Schrader (1991), Theorem 1.4, p. 24.

[FOOTNOTEGordon1997-7] 7.0 ^7.1 ^7.2 Gordon (1997).

[FOOTNOTEKorteLovászSchrader199124–25-8] Korte, Lovász & Schrader (1991), pp. 24–25.

[FOOTNOTEKashiwabaraNakamuraOkamoto2005-9] Kashiwabara, Nakamura & Okamoto (2005).

[10] Gordon (1997) describes several results related to antimatroids of this type, but these antimatroids were mentioned earlier e.g. by Korte, Lovász & Schrader (1991). Chandran et al. (2003) use the connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.

[11] Björner, Lovász & Shor (1991); Knauer (2009).

[FOOTNOTEKorteLovászSchrader1991Lemma_3.12,_p._31-12] 12.0 ^12.1 ^12.2 Korte, Lovász & Schrader (1991), Lemma 3.12, p. 31.

[FOOTNOTEKorteLovászSchrader199131-13] Korte, Lovász & Schrader (1991), p. 31.

[FOOTNOTEKorteLovászSchrader199139–43-14] Korte, Lovász & Schrader (1991), pp. 39–43.

[15] See Korte, Lovász & Schrader (1991), Theorem 3.13, p. 32, which defines paths as rooted sets, sets with a distinguished element, and states an equivalent characterization on the families of rooted sets that form the paths of antimatroids.

[FOOTNOTEKorteLovászSchrader19916,_22-16] Korte, Lovász & Schrader (1991), pp. 6, 22.

[17] See Korte, Lovász & Schrader (1991), p. 22: "any word in an antimatroid can be extended to a basic word".

[FOOTNOTEKorteLovászSchrader1991Theorem_1.1,_p._21-18] 18.0 ^18.1 Korte, Lovász & Schrader (1991), Theorem 1.1, p. 21.

[FOOTNOTEKorteLovászSchrader199120-19] 19.0 ^19.1 Korte, Lovász & Schrader (1991), p. 20.

[FOOTNOTEFarberJamison1986-20] Farber & Jamison (1986).

[21] Adaricheva, Gorbunov & Tumanov (2003), Theorems 1.7 and 1.9; Armstrong (2009), Theorem 2.7.

[22] Edelman (1980), Theorem 3.3; Armstrong (2009), Theorem 2.8.

[23] Monjardet (1985) credits a dual form of this characterization to several papers from the 1960s by S. P. Avann.

[FOOTNOTEArmstrong2009-24] Armstrong (2009).

[25] Korte, Lovász & Schrader (1991), p. 42; Eppstein (2008), Section 7.2; Falmagne et al. (2013), section 14.4.

[26] Edelman & Saks (1988); Korte, Lovász & Schrader (1991), Theorem 6.9.

[FOOTNOTEKorteLovászSchrader1991Corollary_6.10-27] Korte, Lovász & Schrader (1991), Corollary 6.10.

[FOOTNOTEEppstein2008Figure_15-28] Eppstein (2008), Figure 15.

[29] Sloane, N. J. A. (ed.), "Sequence A119770", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

[FOOTNOTEMerchantRiggle2016-30] Merchant & Riggle (2016).

[FOOTNOTEDoignonFalmagne1999-31] Doignon & Falmagne (1999).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

@@ Line 1: / Line 1: @@
 {{Short description|Mathematical system of orderings or sets}}
-[[Image:Antimatroid.svg|thumb|360px|एक एंटीमेट्रोइड के तीन विचार: व्यवहार्य समुच्चयों के अपने परिवार पर समावेशन आदेश, औपचारिक भाषा और संबंधित पथ पोसमुच्चय।]]गणित में, एंटीमैट्रोइड [[औपचारिक प्रणाली]] है जो उन प्रक्रियाओं का वर्णन करती है जिसमें समय में तत्व को सम्मिलित करके [[सेट (गणित)|समुच्चय (गणित)]] बनाया जाता है, और जिसमें तत्व, बार समावेश के लिए उपलब्ध होने तक उपलब्ध रहता है।<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}} for a comprehensive survey of antimatroid theory with many additional references.</ref> एंटीमैट्रोइड्स सामान्यतः [[क्रिप्टोमोर्फिज्म]] हैं, या तो ऐसी प्रक्रिया के संभावित राज्यों को मॉडलिंग करने वाली [[सेट प्रणाली|समुच्चय प्रणाली]] के रूप में, या [[औपचारिक भाषा]] के रूप में विभिन्न अनुक्रमों को मॉडलिंग करते हैं जिसमें तत्व सम्मिलित हो सकते हैं।
+[[Image:Antimatroid.svg|thumb|360px|एक एंटीमेट्रोइड के तीन विचार: व्यावहारिक समुच्चयों के अपने समूह पर समावेशन आदेश, औपचारिक भाषा और संबंधित पथ पोसमुच्चय।]]गणित में, '''एंटीमैट्रोइड''' ऐसी [[औपचारिक प्रणाली]] है जो उन प्रक्रियाओं का वर्णन करती है जिसमें समय में तत्व को सम्मिलित करके [[सेट (गणित)|समुच्चय (गणित)]] बनाया जाता है, और जिसमें तत्व के समावेश के लिए उपलब्ध इसके होने तक उपलब्ध समान रूप से रहते हैं।<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}} for a comprehensive survey of antimatroid theory with many additional references.</ref> एंटीमैट्रोइड्स सामान्यतः [[क्रिप्टोमोर्फिज्म]] हैं, या तो ऐसी प्रक्रिया के संभावित स्थितियों को मॉडलिंग करने वाली [[सेट प्रणाली|समुच्चय प्रणाली]] के रूप में, या [[औपचारिक भाषा]] के रूप में विभिन्न अनुक्रमों को मॉडलिंग करते हैं जिसमें तत्व सम्मिलित हो सकते हैं।
-रॉबर्ट पी. दिलवर्थ (1940) जालक (आदेश) पर आधारित और स्वसिद्धीकरण का उपयोग करते हुए एंटीमेट्रोइड्स का अध्ययन करने वाले पहले व्यक्ति थे, और उन्हें प्रायः अन्य संदर्भों में फिर से खोजा गया है।<ref>Two early references are {{harvtxt|Edelman|1980}} and {{harvtxt|Jamison|1980}}; Jamison was the first to use the term "antimatroid". {{harvtxt|Monjardet|1985}} surveys the history of rediscovery of antimatroids.</ref>
+रॉबर्ट पी. दिलवर्थ (1940) फिन्टर (आदेश) पर आधारित और स्वसिद्धीकरण का उपयोग करते हुए एंटीमेट्रोइड्स का अध्ययन करने वाले पहले व्यक्ति थे, और इस प्रकार उन्हें प्रायः अन्य संदर्भों में फिर से खोजा गया है।<ref>Two early references are {{harvtxt|Edelman|1980}} and {{harvtxt|Jamison|1980}}; Jamison was the first to use the term "antimatroid". {{harvtxt|Monjardet|1985}} surveys the history of rediscovery of antimatroids.</ref>
-एंटीमैट्रोइड्स को समुच्चय सिस्टम के रूप में परिभाषित करने वाले सिद्धांत मैट्रोइड्स के समान हैं, किन्तु जबकि मैट्रोइड्स को मैट्रोइड # स्वतंत्र समुच्चय, बेस और सर्किट द्वारा परिभाषित किया जाता है, एंटीमैट्रोइड्स को एंटी-एक्सचेंज स्वयंसिद्ध द्वारा परिभाषित किया जाता है, जिससे उनका नाम प्राप्त होता है।
+एंटीमैट्रोइड्स को समुच्चय सिस्टम के रूप में परिभाषित करने वाले सिद्धांत मैट्रोइड्स के समान माना जाता हैं, किन्तु जबकि को मैट्रोइड स्वतंत्र समुच्चय, बेस और परिपथ द्वारा परिभाषित किया जाता है, इस प्रकार एंटीमैट्रोइड्स को एंटी-एक्सचेंज स्वयंसिद्ध द्वारा परिभाषित किया जाता है, जिससे उनका नाम प्राप्त होता है।
-एंटीमैट्रोइड्स [[लालची]] और [[अर्ध-मॉड्यूलर जाली]] के विशेष स्थिति के रूप में देखा जा सकता है, और [[आंशिक आदेश]]ों और वितरण संबंधी जाली के सामान्यीकरण के रूप में देखा जा सकता है।
+एंटीमैट्रोइड्स [[अर्ध-मॉड्यूलर जाली|अर्ध-मॉड्यूलर फिल्टर]] की विशेष स्थिति के रूप में देखा जा सकता है, और [[आंशिक आदेश|आंशिक आदेशों]] और वितरण संबंधी फिल्टर के सामान्यीकरण के रूप में देखा जा सकता है।
-एंटीमैट्रोइड्स समतुल्य हैं, पूरक (समुच्चय थ्योरी) द्वारा, 'उत्तल [[ज्यामिति]]' के लिए, ज्यामिति में [[उत्तल सेट|उत्तल समुच्चय]]ों का संयोजी अमूर्त।
+एंटीमैट्रोइड्स समतुल्य हैं, पूरक (समुच्चय थ्योरी) द्वारा, 'उत्तल [[ज्यामिति]]' के लिए, ज्यामिति में [[उत्तल सेट|उत्तल समुच्चयों]] का संयोजी रूप हैं।
 [[जॉब शॉप शेड्यूलिंग]], सिमुलेशन में संभावित घटना क्रम, [[ कृत्रिम होशियारी |कृत्रिम होशियारी]] में टास्क प्लानिंग और मानव शिक्षार्थियों के ज्ञान की अवस्थाओं में मॉडल पूर्ववर्ती बाधाओं के लिए एंटीमैट्रोइड्स लागू किए गए हैं।
 == परिभाषाएँ ==
-एक एंटीमैट्रोइड को परिमित परिवार के रूप में परिभाषित किया जा सकता है <math>\mathcal{F}</math> निम्नलिखित दो गुणों के साथ, परिमित समुच्चय, जिसे व्यवहार्य समुच्चय कहा जाता है:<ref>See e.g. {{harvtxt|Kempner|Levit|2003}}, Definition 2.1 and Proposition 2.3, p. 2.</ref>
+एक एंटीमैट्रोइड को परिमित समूह <math>\mathcal{F}</math>के रूप में परिभाषित किया जा सकता है , इस प्रकार निम्नलिखित दो गुणों के साथ, परिमित समुच्चय, जिसे व्यावहारिक समुच्चय कहा जाता है:<ref>See e.g. {{harvtxt|Kempner|Levit|2003}}, Definition 2.1 and Proposition 2.3, p. 2.</ref>
-* किसी भी दो संभव समुच्चयों का [[संघ (सेट सिद्धांत)|संघ (समुच्चय सिद्धांत)]] भी संभव है। वह है, <math>\mathcal{F}</math> यूनियनों के अनुसार क्लोजर (गणित) है।
+* किसी भी दो संभव समुच्चयों का [[संघ (सेट सिद्धांत)|संघ (समुच्चय सिद्धांत)]] भी संभव है। वह <math>\mathcal{F}</math> है जो यूनियनों के अनुसार क्लोजर (गणित) करता है।
-* यदि <math>S</math> गैर-खाली संभव समुच्चय है, तो <math>S</math> तत्व होता है <math>x</math> जिसके लिए <math>S\setminus\{x\}</math> (हटाने से गठित समुच्चय <math>x</math> से <math>S</math>) भी संभव है। वह है, <math>\mathcal{F}</math> [[सुलभ सेट प्रणाली|सुलभ समुच्चय प्रणाली]] है।
+* यदि <math>S</math> गैर-रिक्त संभव समुच्चय है, तो <math>S</math> तत्व होता है <math>x</math> जिसके लिए <math>S\setminus\{x\}</math> (हटाने से गठित समुच्चय <math>x</math> से <math>S</math>) भी संभव है। वह <math>\mathcal{F}</math> है जो [[सुलभ सेट प्रणाली|सुलभ समुच्चय प्रणाली]] प्रकट करता हैं।
 एंटीमैट्रोइड्स की औपचारिक भाषा के रूप में समकक्ष परिभाषा भी है, जो कि [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के समुच्चय के रूप में [[प्रतीक]]ों के परिमित वर्णमाला से परिभाषित है। इस समुच्चय से संबंधित स्ट्रिंग को भाषा का शब्द कहा जाता है। भाषा <math>\mathcal{L}</math> एंटीमैट्रोइड को परिभाषित करने से निम्नलिखित गुणों को पूरा करना चाहिए:{{sfnp|Korte|Lovász|Schrader|1991|p=22}}
-* वर्णमाला का प्रत्येक प्रतीक कम से कम शब्द में आता है <math>\mathcal{L}</math>.
+* वर्णमाला का प्रत्येक प्रतीक <math>\mathcal{L}</math> द्वारा कम से कम शब्द में प्रकट करता है।
-* का प्रत्येक शब्द <math>\mathcal{L}</math> प्रत्येक प्रतीक की अधिकतम प्रति सम्मिलित है। इस गुण वाली भाषा को सामान्य कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=5}}
+* इसका प्रत्येक शब्द <math>\mathcal{L}</math> प्रत्येक प्रतीक की अधिकतम प्रति सम्मिलित है। इस गुण वाली भाषा को सामान्य कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=5}}
 * प्रत्येक [[उपसर्ग (कंप्यूटर विज्ञान)]] शब्द में <math>\mathcal{L}</math> में भी है <math>\mathcal{L}</math>. इस संपत्ति वाली भाषा को वंशानुगत कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=5}}
-* यदि <math>S</math> और <math>T</math> में शब्द हैं <math>\mathcal{L}</math>, और <math>S</math> कम से कम प्रतीक है जो अंदर नहीं है <math>T</math>, तो प्रतीक है <math>x</math> में <math>S</math> ऐसा है कि संघ <math>Tx</math> में और शब्द है <math>\mathcal{L}</math>.
+* यदि <math>S</math> और <math>T</math> में शब्द हैं <math>\mathcal{L}</math>, और <math>S</math> कम से कम प्रतीक है जो <math>T</math> के अंदर नहीं है, तो प्रतीक <math>x</math>  में <math>S</math> है जो इस प्रकार हैं कि संघ <math>Tx</math> में और शब्द <math>\mathcal{L}</math> है।
-परिभाषा के इन दो रूपों की समानता को निम्नानुसार देखा जा सकता है। यदि <math>\mathcal{L}</math> औपचारिक भाषा के रूप में परिभाषित एंटीमेट्रोइड है, फिर शब्दों के प्रतीकों का समुच्चय <math>\mathcal{L}</math> सुलभ संघ-बंद समुच्चय सिस्टम बनाएं। यह स्ट्रिंग्स की वंशानुगत संपत्ति द्वारा सुलभ है, और इसे स्ट्रिंग्स के संयोजन गुण के बार-बार उपयोग द्वारा संघ-बंद दिखाया जा सकता है। दूसरी दिशा में, सुलभ संघ-बंद समुच्चय प्रणाली से <math>\mathcal{F}</math>, सामान्य स्ट्रिंग्स की भाषा जिसके सभी उपसर्गों से संबंधित प्रतीकों के समुच्चय होते हैं <math>\mathcal{F}</math> औपचारिक भाषा के लिए एंटीमेट्रोइड होने की आवश्यकताओं को पूरा करता है। ये दो परिवर्तन दूसरे के प्रतिलोम हैं: औपचारिक भाषा को निर्धारित परिवार में बदलना और इसके विपरीत, ही प्रणाली का निर्माण करता है। इस प्रकार, ये दो परिभाषाएँ गणितीय रूप से वस्तुओं के समतुल्य वर्गों की ओर ले जाती हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.4, p. 24}}
+परिभाषा के इन दो रूपों की समानता को निम्नानुसार देखा जा सकता है। यदि <math>\mathcal{L}</math> औपचारिक भाषा के रूप में परिभाषित एंटीमेट्रोइड है, फिर शब्दों के प्रतीकों का समुच्चय <math>\mathcal{L}</math> सुलभ संघ-बंद समुच्चय सिस्टम के रूप में बनाया जाता हैं। इस प्रकार यह स्ट्रिंग्स की वंशानुगत संपत्ति द्वारा सुलभ है, और इसे स्ट्रिंग्स के संयोजन गुण के बार-बार उपयोग द्वारा संघ-बंद दिखाया जा सकता है। इस प्रकार दूसरी दिशा में, सुलभ संघ-बंद समुच्चय प्रणाली से <math>\mathcal{F}</math>, सामान्य स्ट्रिंग्स की भाषा जिसके सभी उपसर्गों से संबंधित <math>\mathcal{F}</math> प्रतीकों के समुच्चय होते हैं, औपचारिक भाषा के लिए एंटीमेट्रोइड होने की आवश्यकताओं को पूरा करता है। ये दो परिवर्तन दूसरे के प्रतिलोम हैं: औपचारिक भाषा को निर्धारित समूह में बदलना और इसके विपरीत, ही प्रणाली का निर्माण करता है। इस प्रकार, ये दो परिभाषाएँ गणितीय रूप से वस्तुओं के समतुल्य वर्गों की ओर ले जाती हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.4, p. 24}}
 == उदाहरण ==
-[[Image:Convex shelling.svg|thumb|300px|प्लानर पॉइंट समुच्चय का गोलाबारी क्रम। कुछ बिंदुओं को हटा दिए जाने के बाद रेखा खंड उत्तल पतवार के किनारों को दिखाते हैं।]]निम्नलिखित प्रणालियाँ एंटीमैट्रोइड्स के उदाहरण प्रदान करती हैं:
+[[Image:Convex shelling.svg|thumb|300px|प्लानर पॉइंट समुच्चय का गोलाबारी क्रम में रहते हैं। कुछ बिंदुओं को हटा दिए जाने के बाद रेखा खंड उत्तल पतवार के किनारों को दिखाते हैं।]]निम्नलिखित प्रणालियाँ एंटीमैट्रोइड्स के उदाहरण प्रदान करती हैं:
 चेन एंटीमैट्रोइड्स
-: एकल स्ट्रिंग के उपसर्ग, और इन उपसर्गों में प्रतीकों के समुच्चय, एंटीमैट्रोइड बनाते हैं। उदाहरण के लिए स्ट्रिंग द्वारा परिभाषित चेन एंटीमैट्रोइड <math>abcd</math> इसकी औपचारिक भाषा के रूप में स्ट्रिंग्स का समुच्चय है <math display=block>\{\varepsilon, a, ab, abc, abcd\}</math> (कहाँ <math>\varepsilon</math> [[खाली स्ट्रिंग]] को दर्शाता है) और जैसा कि संभव है इसका परिवार परिवार को समुच्चय करता है{{sfnp|Gordon|1997}} <math display=block>\bigl\{\emptyset,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}\bigr\}.</math>
+: एकल स्ट्रिंग के उपसर्ग, और इन उपसर्गों में प्रतीकों के समुच्चय, एंटीमैट्रोइड बनाते हैं। उदाहरण के लिए स्ट्रिंग द्वारा परिभाषित चेन एंटीमैट्रोइड <math>abcd</math> इसकी औपचारिक भाषा के रूप में स्ट्रिंग्स का समुच्चय है <math display=block>\{\varepsilon, a, ab, abc, abcd\}</math> (जहाँ <math>\varepsilon</math> [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] को दर्शाता है) और जैसा कि संभव है इसका समूह समूह को समुच्चय करता है{{sfnp|Gordon|1997}} <math display=block>\bigl\{\emptyset,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}\bigr\}.</math>
 पोसमुच्चय एंटीमैट्रोइड्स
-: एक परिमित [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समुच्चय]] के निचले समुच्चय एंटीमैट्रोइड बनाते हैं, जिसमें एंटीमैट्रोइड के पूर्ण-लंबाई वाले शब्द आंशिक क्रम के रैखिक एक्सटेंशन बनाते हैं।{{sfnp|Korte|Lovász|Schrader|1991|pp=24–25}} बिरखॉफ के वितरण प्रमेय द्वारा वितरण जाली के लिए, पॉसमुच्चय एंटीमेट्रॉइड (समुच्चय समावेशन द्वारा आदेशित) में व्यवहार्य समुच्चय वितरण जाली बनाते हैं, और सभी वितरण जाल इस तरह से बन सकते हैं। इस प्रकार, एंटीमैट्रोइड्स को वितरणात्मक लैटिस के सामान्यीकरण के रूप में देखा जा सकता है। चेन एंटीमैट्रोइड कुल ऑर्डर के लिए पोसमुच्चय एंटीमैट्रोइड का विशेष स्थिति है।{{sfnp|Gordon|1997}}
+: एक परिमित [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समुच्चय]] के निचले समुच्चय एंटीमैट्रोइड बनाते हैं, जिसमें एंटीमैट्रोइड के पूर्ण-लंबाई वाले शब्द आंशिक क्रम के रैखिक एक्सटेंशन बनाते हैं।{{sfnp|Korte|Lovász|Schrader|1991|pp=24–25}} इस प्रकार बिरखॉफ के वितरण प्रमेय द्वारा वितरण फिल्टर के लिए, पॉसमुच्चय एंटीमेट्रॉइड (समुच्चय समावेशन द्वारा आदेशित) में व्यावहारिक समुच्चय वितरण फिल्टर बनाते हैं, और इस प्रकार सभी वितरण फिल्टर इस प्रकार से बन सकते हैं। इस प्रकार, एंटीमैट्रोइड्स को वितरणात्मक लैटिस के सामान्यीकरण के रूप में देखा जा सकता है। इस प्रकार चेन एंटीमैट्रोइड कुल ऑर्डर के लिए पोसमुच्चय एंटीमैट्रोइड का विशेष स्थिति है।{{sfnp|Gordon|1997}}
 शेलिंग एंटीमैट्रोइड्स
-: परिमित समुच्चय का गोलाबारी क्रम <math>U</math> [[यूक्लिडियन विमान]] या उच्च-आयामी [[यूक्लिडियन अंतरिक्ष]] में बिंदुओं की संख्या उत्तल पतवार के बार-बार हटाने से बनती है। इन अनुक्रमों द्वारा गठित एंटीमेट्रोइड के व्यवहार्य समुच्चय इंटरसेक्शन (समुच्चय सिद्धांत) हैं <math>U</math> उत्तल समुच्चय के पूरक (समुच्चय सिद्धांत) के साथ।{{sfnp|Gordon|1997}} प्रत्येक एंटीमैट्रोइड पर्याप्त उच्च-आयामी अंतरिक्ष में बिंदुओं के शेलिंग एंटीमैट्रोइड के लिए आइसोमोर्फिक है।{{sfnp|Kashiwabara|Nakamura|Okamoto|2005}}
+: परिमित समुच्चय का गोलाबारी क्रम <math>U</math> [[यूक्लिडियन विमान]] या उच्च-आयामी [[यूक्लिडियन अंतरिक्ष]] में बिंदुओं की संख्या उत्तल पतवार के बार-बार हटाने से बनती है। इन अनुक्रमों द्वारा गठित एंटीमेट्रोइड के व्यावहारिक समुच्चय इंटरसेक्शन (समुच्चय सिद्धांत) हैं <math>U</math> उत्तल समुच्चय के पूरक (समुच्चय सिद्धांत) के साथ उपयोग किया जाता हैं।{{sfnp|Gordon|1997}} इस प्रकार प्रत्येक एंटीमैट्रोइड पर्याप्त उच्च-आयामी अंतरिक्ष में बिंदुओं के शेलिंग एंटीमैट्रोइड के लिए आइसोमोर्फिक है।{{sfnp|Kashiwabara|Nakamura|Okamoto|2005}}
 सही निष्कासन
-: [[कॉर्डल ग्राफ]] का पूर्ण विलोपन क्रम उसके शीर्षों का ऐसा क्रम है, जो प्रत्येक शीर्ष के लिए होता है <math>v</math>, के पड़ोसी <math>v</math> जो बाद में होता है <math>v</math> ऑर्डरिंग फॉर्म में [[ गुट (ग्राफ सिद्धांत) |गुट (ग्राफ सिद्धांत)]] । कॉर्डल ग्राफ के पूर्ण उन्मूलन क्रम के उपसर्ग एंटीमैट्रोइड बनाते हैं।<ref>{{harvtxt|Gordon|1997}} describes several results related to antimatroids of this type, but these antimatroids were mentioned earlier e.g. by {{harvtxt|Korte|Lovász|Schrader|1991}}. {{harvtxt|Chandran|Ibarra|Ruskey|Sawada|2003}} use the connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.</ref>
+: [[कॉर्डल ग्राफ]] का पूर्ण विलोपन क्रम उसके शीर्षों का ऐसा क्रम है, जो प्रत्येक शीर्ष के लिए होता है <math>v</math>, के पड़ोसी <math>v</math> जो बाद में <math>v</math> ऑर्डरिंग फॉर्म में [[ गुट (ग्राफ सिद्धांत) |गुट (ग्राफ सिद्धांत)]] होता है। इस प्रकार कॉर्डल ग्राफ के पूर्ण उन्मूलन क्रम के उपसर्ग एंटीमैट्रोइड बनाते हैं।<ref>{{harvtxt|Gordon|1997}} describes several results related to antimatroids of this type, but these antimatroids were mentioned earlier e.g. by {{harvtxt|Korte|Lovász|Schrader|1991}}. {{harvtxt|Chandran|Ibarra|Ruskey|Sawada|2003}} use the connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.</ref>
-[[ चिप फायरिंग का खेल ]]
+[[ चिप फायरिंग का खेल | चिप फायरिंग]]
-: चिप-फायरिंग गेम जैसे कि [[एबेलियन सैंडपाइल मॉडल]] को [[निर्देशित ग्राफ]] द्वारा परिभाषित किया जाता है, साथ ही इसके शीर्ष पर चिप्स की प्रणाली होती है। जब भी शीर्ष पर चिप्स की संख्या <math>v</math> कम से कम उतना बड़ा है जितना कि किनारों की संख्या <math>v</math>, फायर करना संभव है <math>v</math>, चिप को प्रत्येक पड़ोसी शीर्ष पर ले जाना। वह घटना जो <math>v</math> के लिए आग <math>i</math>वें समय केवल तभी हो सकता है जब यह पहले से ही निकाल दिया गया हो <math>i-1</math> बार और संचित <math>i\cdot\deg(v)</math> कुल चिप्स। ये स्थितियाँ पिछली फायरिंग के आदेश पर निर्भर नहीं करती हैं, और तब तक सही रहती हैं <math>v</math> आग, इसलिए किसी दिए गए ग्राफ और चिप्स की प्रारंभिक नियुक्ति जिसके लिए सिस्टम समाप्त हो जाता है, जोड़े पर एंटीमैट्रोइड को परिभाषित करता है <math>(v,i)</math>. इन प्रणालियों की एंटीमैट्रोइड संपत्ति का परिणाम यह है कि, किसी दिए गए प्रारंभिक राज्य के लिए, प्रत्येक वर्टेक्स की आग की संख्या और सिस्टम की अंतिम स्थिर स्थिति फायरिंग ऑर्डर पर निर्भर नहीं होती है।<ref>{{harvtxt|Björner|Lovász|Shor|1991}}; {{harvtxt|Knauer|2009}}.</ref>
+: चिप-फायरिंग गेम जैसे कि [[एबेलियन सैंडपाइल मॉडल]] को [[निर्देशित ग्राफ]] द्वारा परिभाषित किया जाता है, साथ ही इसके शीर्ष पर चिप्स की प्रणाली होती है। जब भी शीर्ष पर चिप्स की संख्या <math>v</math> कम से कम उतना बड़ा है जितना कि किनारों की संख्या <math>v</math>, फायर करना संभव है, इस प्रकार चिप को प्रत्येक पड़ोसी शीर्ष पर ले जाना संभव रहता हैं। वह घटना जो <math>v</math> के लिए आग <math>i</math>वें समय केवल तभी हो सकता है जब यह पहले से ही निकाल दिया गया हो <math>i-1</math> बार और संचित <math>i\cdot\deg(v)</math> कुल चिप्स पर निर्भर करता हैं। ये स्थितियाँ पिछली फायरिंग के आदेश पर निर्भर नहीं करती हैं, और तब तक सही रहती हैं <math>v</math> आग, इसलिए किसी दिए गए ग्राफ और चिप्स की प्रारंभिक नियुक्ति जिसके लिए सिस्टम समाप्त हो जाता है, इस प्रकार जोड़े पर एंटीमैट्रोइड <math>(v,i)</math> को परिभाषित करता है, इन प्रणालियों की एंटीमैट्रोइड संपत्ति का परिणाम यह है कि, किसी दिए गए प्रारंभिक राज्य के लिए, प्रत्येक वर्टेक्स की आग की संख्या और इस प्रणाली की अंतिम स्थिर स्थिति फायरिंग ऑर्डर पर निर्भर नहीं होती है।<ref>{{harvtxt|Björner|Lovász|Shor|1991}}; {{harvtxt|Knauer|2009}}.</ref>
 == पथ और मूल शब्द ==
-एक एंटीमैट्रोइड के समुच्चय थ्योरिटिक स्वयंसिद्धीकरण में कुछ विशेष समुच्चय होते हैं जिन्हें पथ कहा जाता है जो पूरे एंटीमैट्रोइड को निर्धारित करते हैं, इस अर्थ में कि एंटीमैट्रोइड के समुच्चय वास्तव में पथों के संघ हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}} यदि <math>S</math> एंटीमैट्रोइड, तत्व का कोई व्यवहार्य समुच्चय है <math>x</math> जिससे हटाया जा सकता है <math>S</math> और संभव समुच्चय बनाने के लिए समापन बिंदु कहा जाता है <math>S</math>, और व्यवहार्य समुच्चय जिसमें केवल समापन बिंदु होता है, उसे एंटीमैट्रोइड का पथ कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=31}} पथों के परिवार को समुच्चय समावेशन द्वारा आंशिक रूप से आदेशित किया जा सकता है, जिससे एंटीमैट्रोइड का पथ पोसमुच्चय बनता है।{{sfnp|Korte|Lovász|Schrader|1991|pp=39–43}}
+एक एंटीमैट्रोइड के समुच्चय थ्योरिटिक स्वयंसिद्धीकरण में कुछ विशेष समुच्चय होते हैं जिन्हें पथ कहा जाता है जो पूरे एंटीमैट्रोइड को निर्धारित करते हैं, इस अर्थ में कि एंटीमैट्रोइड के समुच्चय वास्तव में पथों के संघ हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}} यदि <math>S</math> एंटीमैट्रोइड, तत्व का कोई व्यावहारिक समुच्चय है <math>x</math> जिससे <math>S</math> को हटाया जा सकता है और संभव समुच्चय बनाने के लिए समापन बिंदु <math>S</math> को कहा जाता है, और व्यावहारिक समुच्चय जिसमें केवल समापन बिंदु होता है, उसे एंटीमैट्रोइड का पथ कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=31}} इस प्रकार पथों के समूह को समुच्चय समावेशन द्वारा आंशिक रूप से आदेशित किया जा सकता है, जिससे एंटीमैट्रोइड का पथ पोसमुच्चय बनता है।{{sfnp|Korte|Lovász|Schrader|1991|pp=39–43}}
-हर संभव समुच्चय के लिए <math>S</math> एंटीमैट्रोइड में, और हर तत्व <math>x</math> का <math>S</math>, किसी का पथ उपसमुच्चय मिल सकता है <math>S</math> जिसके लिए <math>x</math> समापन बिंदु है: ऐसा करने के लिए, के अतिरिक्त अन्य तत्वों को समय में हटा दें <math>x</math> जब तक ऐसा कोई निष्कासन संभव उपसमुच्चय नहीं छोड़ता। इसलिए, एंटीमेट्रोइड में प्रत्येक व्यवहार्य समुच्चय इसके पथ उपसमुच्चय का संघ है।{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}} यदि <math>S</math> पथ नहीं है, इस संघ में प्रत्येक उपसमुच्चय का उचित उपसमुच्चय है <math>S</math>. किन्तु यदि <math>S</math> अपने आप में समापन बिंदु वाला पथ है <math>x</math>, का प्रत्येक उचित उपसमुच्चय <math>S</math> जो एंटीमैट्रोइड से संबंधित है, उसमें सम्मिलित नहीं है <math>x</math>. इसलिए, एंटीमेट्रोइड के पथ वास्तव में व्यवहार्य समुच्चय हैं जो उनके उचित व्यवहार्य उपसमुच्चय के संघों के बराबर नहीं हैं। समतुल्य, समुच्चय का दिया गया परिवार <math>\mathcal{P}</math> एंटीमैट्रोइड के पथों का परिवार बनाता है यदि और केवल यदि, प्रत्येक के लिए <math>S</math> में <math>\mathcal{P}</math>, के सबसमुच्चय का संघ <math>S</math> में <math>\mathcal{P}</math> से कम तत्व है <math>S</math> अपने आप।<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}}, Theorem 3.13, p. 32, which defines paths as ''rooted sets'', sets with a distinguished element, and states an equivalent characterization on the families of rooted sets that form the paths of antimatroids.</ref> यदि ऐसा है तो, <math>\mathcal{F}</math> ही के सबसमुच्चय के यूनियनों का परिवार है <math>\mathcal{P}</math>.{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}}
+इस प्रकार संभवतः समुच्चय के लिए <math>S</math> एंटीमैट्रोइड में, और हर तत्व <math>x</math> का <math>S</math>, किसी का पथ उपसमुच्चय मिल सकता है <math>S</math> जिसके लिए <math>x</math> समापन बिंदु है: ऐसा करने के लिए, के अतिरिक्त अन्य तत्वों को समय में <math>x</math> को हटा देते हैं। जब तक ऐसा कोई निष्कासन संभव उपसमुच्चय नहीं छोड़ता हैं। इसलिए एंटीमेट्रोइड में प्रत्येक व्यावहारिक समुच्चय इसके पथ उपसमुच्चय का संघ है।{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}} यदि <math>S</math> पथ नहीं है, इस संघ में प्रत्येक उपसमुच्चय का उचित उपसमुच्चय <math>S</math> है, किन्तु यदि <math>S</math> अपने आप में समापन बिंदु वाला पथ <math>x</math> है, जिसका प्रत्येक उचित उपसमुच्चय <math>S</math> जो एंटीमैट्रोइड से संबंधित है, उसमें <math>x</math> का मान सम्मिलित नहीं होता है, इसलिए, एंटीमेट्रोइड के पथ वास्तव में व्यवहारिक समुच्चय हैं जो उनके उचित व्यावहारिक उपसमुच्चय के संघों के बराबर नहीं हैं। इस प्रकार समतुल्य, समुच्चय का दिया गया समूह <math>\mathcal{P}</math> एंटीमैट्रोइड के पथों का समूह बनाता है यदि और केवल यदि, प्रत्येक के लिए <math>S</math> में <math>\mathcal{P}</math>, के उपसमुच्चय का संघ <math>S</math> में <math>\mathcal{P}</math> से कम तत्व है, जो <math>S</math>  के लिए अपने आप आ जाता है।<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}}, Theorem 3.13, p. 32, which defines paths as ''rooted sets'', sets with a distinguished element, and states an equivalent characterization on the families of rooted sets that form the paths of antimatroids.</ref> यदि ऐसा है तो, <math>\mathcal{F}</math> ही के उपसमुच्चय के यूनियनों का समूह <math>\mathcal{P}</math> है।{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}}
-एक एंटीमैट्रोइड की औपचारिक भाषा की औपचारिकता में, सबसे लंबे तार को मूल शब्द कहा जाता है। प्रत्येक मूल शब्द पूरे वर्णमाला का क्रमचय बनाता है।{{sfnp|Korte|Lovász|Schrader|1991|pp=6, 22}} यदि <math>B</math> मूल शब्दों का समूह है, <math>\mathcal{L}</math> से परिभाषित किया जा सकता है <math>B</math> शब्दों के उपसर्गों के समुच्चय के रूप में <math>B</math>.<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}}, p. 22: "any word in an antimatroid can be extended to a basic word".</ref>
+एक एंटीमैट्रोइड की औपचारिक भाषा की औपचारिकता में, सबसे लंबे तार को मूल शब्द कहा जाता है। प्रत्येक मूल शब्द पूरे वर्णमाला का क्रमचय बनाता है।{{sfnp|Korte|Lovász|Schrader|1991|pp=6, 22}} यदि <math>B</math> मूल शब्दों का समूह है, <math>\mathcal{L}</math> से परिभाषित किया जा सकता है <math>B</math> शब्दों के उपसर्गों के समुच्चय <math>B</math> के रूप में निर्भर करता हैं।<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}}, p. 22: "any word in an antimatroid can be extended to a basic word".</ref>
 == उत्तल ज्यामिति ==
 {{See also|उत्तल सेट|उत्तल ज्यामिति|क्लोजर ऑपरेटर}}
-यदि <math>\mathcal{F}</math> एंटीमैट्रोइड को परिभाषित करने वाली समुच्चय प्रणाली है <math>U</math> में समुच्चय के संघ के बराबर <math>\mathcal{F}</math>, फिर समुच्चय का परिवार<math display=block>\mathcal{G} = \{U\setminus S\mid S\in \mathcal{F}\}</math>पूरक (समुच्चय सिद्धांत) में समुच्चय करने के लिए <math>\mathcal{F}</math> इसे कभी-कभी उत्तल ज्यामिति कहा जाता है और समुच्चय हो जाता है <math>\mathcal{G}</math> उत्तल समुच्चय कहलाते हैं। उदाहरण के लिए, शेलिंग एंटीमैट्रोइड में, उत्तल समुच्चय यूक्लिडियन अंतरिक्ष के उत्तल उपसमुच्चय के साथ दिए गए बिंदु समुच्चय के चौराहे हैं। उत्तल ज्यामिति को परिभाषित करने वाली समुच्चय प्रणाली को चौराहों के नीचे बंद किया जाना चाहिए। किसी भी समुच्चय के लिए <math>S</math> में <math>\mathcal{G}</math> वह बराबर नहीं है <math>U</math> तत्व होना चाहिए <math>x</math> अंदर नही <math>S</math> जिसे जोड़ा जा सकता है <math>S</math> और समुच्चय बनाने के लिए <math>\mathcal{G}</math>.{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.1, p. 21}}
+यदि <math>\mathcal{F}</math> एंटीमैट्रोइड को परिभाषित करने वाली समुच्चय प्रणाली है <math>U</math> में समुच्चय के संघ के बराबर <math>\mathcal{F}</math>, फिर समुच्चय का समूह<math display=block>\mathcal{G} = \{U\setminus S\mid S\in \mathcal{F}\}</math>पूरक (समुच्चय सिद्धांत) में समुच्चय करने के लिए <math>\mathcal{F}</math> इसे कभी-कभी उत्तल ज्यामिति कहा जाता है और समुच्चय हो जाता है <math>\mathcal{G}</math> उत्तल समुच्चय कहलाते हैं। उदाहरण के लिए, शेलिंग एंटीमैट्रोइड में, उत्तल समुच्चय यूक्लिडियन अंतरिक्ष के उत्तल उपसमुच्चय के साथ दिए गए बिंदु समुच्चय के अंतः खण्ड हैं। उत्तल ज्यामिति को परिभाषित करने वाली समुच्चय प्रणाली को अंतखण्ड के नीचे बंद किया जाना चाहिए। किसी भी समुच्चय के लिए <math>S</math> में <math>\mathcal{G}</math> वह बराबर नहीं है <math>U</math> तत्व होना चाहिए <math>x</math> अंदर नही <math>S</math> जिसे जोड़ा जा सकता है <math>S</math> और समुच्चय बनाने के लिए <math>\mathcal{G}</math> का उपयोग किया जाता हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.1, p. 21}}
-एक [[ बंद करने वाला ऑपरेटर |बंद करने वाला ऑपरेटर]] के संदर्भ में उत्तल ज्यामिति को भी परिभाषित किया जा सकता है <math>\tau</math> जो किसी भी सबसमुच्चय को मैप करता है <math>U</math> इसके न्यूनतम बंद सुपरसमुच्चय के लिए। क्लोजर ऑपरेटर बनने के लिए, <math>\tau</math> निम्नलिखित गुण होने चाहिए:{{sfnp|Korte|Lovász|Schrader|1991|p=20}}
+एक [[ बंद करने वाला ऑपरेटर |बंद करने वाला ऑपरेटर]] के संदर्भ में उत्तल ज्यामिति <math>\tau</math> को भी परिभाषित किया जा सकता है, जो किसी भी उपसमुच्चय <math>U</math> को मैप करता है , इसके न्यूनतम बंद सुपरसमुच्चय के लिए निर्धारित किया जाता हैं। क्लोजर ऑपरेटर बनने के लिए, <math>\tau</math> निम्नलिखित गुण होने चाहिए:{{sfnp|Korte|Lovász|Schrader|1991|p=20}}
-* <math>\tau(\emptyset)=\emptyset</math>: [[खाली सेट|खाली समुच्चय]] का क्लोजर खाली है।
+* <math>\tau(\emptyset)=\emptyset</math>: [[खाली सेट|रिक्त समुच्चय]] का क्लोजर रिक्त है।
-* प्रत्येक उपसमुच्चय के लिए <math>S</math> का <math>U</math>, <math>S</math> का उपसमुच्चय है <math>\tau(S)</math> और <math>\tau(S)=\tau\bigl(\tau(S)\bigr)</math>.
+* प्रत्येक उपसमुच्चय के लिए <math>S</math> का <math>U</math>, <math>S</math> का उपसमुच्चय <math>\tau(S)</math> और <math>\tau(S)=\tau\bigl(\tau(S)\bigr)</math> हैं।
-* जब कभी भी <math>S\subset T\subset U</math>, <math>\tau(S)</math> का उपसमुच्चय है <math>\tau(T)</math>.
+* जब कभी भी <math>S\subset T\subset U</math>, <math>\tau(S)</math> का उपसमुच्चय <math>\tau(T)</math> है।
-इस प्रकार के क्लोजर ऑपरेशन से उत्पन्न बंद समुच्चय का परिवार आवश्यक रूप से चौराहों के नीचे बंद है, किन्तु उत्तल ज्यामिति नहीं हो सकता है। क्लोजर ऑपरेटर जो उत्तल ज्यामिति को परिभाषित करते हैं, अतिरिक्त एंटी-एक्सचेंज स्वयंसिद्ध को भी संतुष्ट करते हैं:
+इस प्रकार के क्लोजर ऑपरेशन से उत्पन्न बंद समुच्चय का समूह आवश्यक रूप से अंतः खण्डों के नीचे बंद है, किन्तु उत्तल ज्यामिति नहीं हो सकता है। क्लोजर ऑपरेटर जो उत्तल ज्यामिति को परिभाषित करते हैं, अतिरिक्त एंटी-एक्सचेंज स्वयंसिद्ध को भी संतुष्ट करते हैं:
-*यदि <math>S</math> का उपसमुच्चय है <math>U</math>, और <math>y</math> और <math>z</math> के विशिष्ट तत्व हैं <math>U</math> जिसका संबंध नहीं है <math>\tau(S)</math>, किन्तु <math>z</math> का है <math>\tau(S\cup\{y\})</math>, तब <math>y</math> का नहीं है <math>\tau(S\cup\{z\})</math>.{{sfnp|Korte|Lovász|Schrader|1991|p=20}}
+*यदि <math>S</math> का उपसमुच्चय है <math>U</math>, और <math>y</math> और <math>z</math> के विशिष्ट तत्व हैं <math>U</math> जिसका संबंध नहीं है <math>\tau(S)</math>, किन्तु <math>z</math> का है <math>\tau(S\cup\{y\})</math>, तब <math>y</math> का मान <math>\tau(S\cup\{z\})</math> नहीं है।{{sfnp|Korte|Lovász|Schrader|1991|p=20}}
-इस स्वयंसिद्ध को संतुष्ट करने वाले क्लोजर ऑपरेशन को एंटी-एक्सचेंज क्लोजर कहा जाता है। यदि <math>S</math> एंटी-एक्सचेंज क्लोजर में बंद समुच्चय है, तो एंटी-एक्सचेंज स्वयंसिद्ध उन तत्वों पर आंशिक क्रम निर्धारित करता है जो इससे संबंधित नहीं हैं <math>S</math>, कहाँ <math>x\le y</math> आंशिक क्रम में जब <math>x</math> से संबंधित <math>\tau(S\cup\{y\})</math>. यदि <math>x</math> इस आंशिक क्रम का न्यूनतम तत्व है, तब <math>S\cup\{x\}</math> बन्द है। अर्थात्, एंटी-एक्सचेंज क्लोजर के बंद समुच्चयों के परिवार के पास संपत्ति है कि सार्वभौमिक समुच्चय के अतिरिक्त किसी भी समुच्चय के लिए तत्व है <math>x</math> इसे और बंद समुच्चय बनाने के लिए इसमें जोड़ा जा सकता है। यह संपत्ति एंटीमेट्रोइड्स की पहुंच क्षमता की संपत्ति का पूरक है, और तथ्य यह है कि बंद समुच्चयों के चौराहे बंद हैं संपत्ति के पूरक हैं कि एंटीमैट्रोइड में व्यवहार्य समुच्चयों के संघ संभव हैं। इसलिए, किसी भी एंटी-एक्सचेंज क्लोजर के बंद समुच्चय के पूरक एंटीमैट्रोइड बनाते हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.1, p. 21}}
+इस स्वयंसिद्ध को संतुष्ट करने वाले क्लोजर ऑपरेशन को एंटी-एक्सचेंज क्लोजर कहा जाता है। यदि <math>S</math> एंटी-एक्सचेंज क्लोजर में बंद समुच्चय है, तो एंटी-एक्सचेंज स्वयंसिद्ध उन तत्वों पर आंशिक क्रम निर्धारित करता है जो इससे संबंधित नहीं हैं <math>S</math>, जहाँ <math>x\le y</math> आंशिक क्रम में जब <math>x</math> से संबंधित <math>\tau(S\cup\{y\})</math> मान के लिए <math>x</math> इस आंशिक क्रम का न्यूनतम तत्व है, तब <math>S\cup\{x\}</math> बन्द रहता है। अर्थात्, एंटी-एक्सचेंज क्लोजर के बंद समुच्चयों के समूह के पास संपत्ति है कि सार्वभौमिक समुच्चय के अतिरिक्त किसी भी समुच्चय के लिए तत्व है <math>x</math> इसे और बंद समुच्चय बनाने के लिए इसमें जोड़ा जा सकता है। यह संपत्ति एंटीमेट्रोइड्स की पहुंच क्षमता की संपत्ति का पूरक है, और तथ्य यह है कि बंद समुच्चयों के अंतः खण्ड बंद हैं संपत्ति के पूरक हैं कि एंटीमैट्रोइड में व्यावहारिक समुच्चयों के संघ संभव हैं। इसलिए, किसी भी एंटी-एक्सचेंज क्लोजर के बंद समुच्चय के पूरक एंटीमैट्रोइड बनाते हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.1, p. 21}}
 अप्रत्यक्ष रेखांकन जिसमें उत्तल समुच्चय (उपसमुच्चय के उपसमुच्चय जिसमें उपसमुच्चय में कोने के बीच सभी सबसे छोटे रास्ते होते हैं) उत्तल ज्यामिति बनाते हैं, बिल्कुल टॉलेमिक रेखांकन होते हैं।{{sfnp|Farber|Jamison|1986}}
 == ज्वाइन-डिस्ट्रीब्यूटिव लैटिस ==
-एंटीमैट्रोइड के प्रत्येक दो व्यवहार्य समुच्चयों में अद्वितीय कम से कम ऊपरी बाउंड (उनका संघ) और अद्वितीय सबसे बड़ा निचला बाउंड होता है (एंटीमैट्रोइड में समुच्चय का संघ जो दोनों में निहित होता है)। इसलिए, एंटीमैट्रोइड के व्यवहार्य समुच्चय, समुच्चय समावेशन द्वारा आंशिक क्रम, जाली (आदेश) बनाते हैं। एंटीमैट्रोइड की विभिन्न महत्वपूर्ण विशेषताओं की व्याख्या जाली-सैद्धांतिक शब्दों में की जा सकती है; उदाहरण के लिए एंटीमैट्रोइड के पथ जाली (क्रम) #महत्वपूर्ण जाली-सैद्धांतिक धारणाएं हैं। संबंधित जाली के सम्मिलित-अप्रासंगिक तत्व हैं, और एंटीमैट्रोइड के मूल शब्द जाली में [[अधिकतम श्रृंखला]]ओं के अनुरूप हैं। इस तरह से एंटीमैट्रोइड्स से उत्पन्न होने वाली जाली, परिमित वितरण संबंधी जाली को सामान्य करती है, और इसे कई अलग-अलग तरीकों से चित्रित किया जा सकता है।
+एंटीमैट्रोइड के प्रत्येक दो व्यावहारिक समुच्चयों में अद्वितीय कम से कम ऊपरी बाउंड (उनका संघ) और अद्वितीय सबसे बड़ा निचला बाउंड होता है (एंटीमैट्रोइड में समुच्चय का संघ जो दोनों में निहित होता है)। इसलिए, एंटीमैट्रोइड के व्यावहारिक समुच्चय, समुच्चय समावेशन द्वारा आंशिक क्रम, फिल्टर (आदेश) बनाते हैं। एंटीमैट्रोइड की विभिन्न महत्वपूर्ण विशेषताओं की व्याख्या फिल्टर-सैद्धांतिक शब्दों में की जा सकती है; उदाहरण के लिए एंटीमैट्रोइड के पथ फिल्टर (क्रम) #महत्वपूर्ण फिल्टर-सैद्धांतिक धारणाएं हैं। संबंधित फिल्टर के सम्मिलित-अप्रासंगिक तत्व हैं, और एंटीमैट्रोइड के मूल शब्द फिल्टर में [[अधिकतम श्रृंखला|अधिकतम श्रृंखलाओं]] के अनुरूप रहता हैं। इस प्रकार एंटीमैट्रोइड्स से उत्पन्न होने वाली फिल्टर, परिमित वितरण संबंधी फिल्टर को सामान्य करती है, और इसे कई अलग-अलग तरीकों से चित्रित किया जा सकता है।
-* विवरण मूल रूप से माना जाता है {{harvtxt|दिलवर्थ|1940}} चिंता जाली (आदेश)#महत्वपूर्ण जाली-सैद्धांतिक धारणा| प्रत्येक तत्व के लिए <math>x</math> एंटीमैट्रोइड का, अद्वितीय अधिकतम संभव समुच्चय सम्मिलित है <math>S_x</math> जिसमें सम्मिलित नहीं है <math>x</math>: <math>S_x</math> सम्‍मिलित नहीं सभी संभव समुच्चयों के संघ के रूप में निर्मित किया जा सकता है <math>x</math>. यह समुच्चय <math>S_x</math> स्वचालित रूप से मिलने-अपूरणीय है, जिसका अर्थ है कि यह किसी भी दो बड़े जाली तत्वों का मिलन नहीं है। यह सच है क्योंकि का हर संभव सुपरसमुच्चय <math>S_x</math> रोकना <math>x</math>, और इसलिए यह संभव सुपरसमुच्चय के हर चौराहे के बारे में भी सच है। मनमाना जाली के प्रत्येक तत्व को मीट-इरिड्यूसिबल समुच्चय के मिलन के रूप में विघटित किया जा सकता है, प्रायः कई तरीकों से, किन्तु जाली में प्रत्येक तत्व एंटीमैट्रोइड के अनुरूप होता है। <math>T</math> मीट-इरिड्यूसिबल समुच्चय का अनूठा न्यूनतम परिवार है जिसका मिलन है <math>T</math>; इस परिवार में समुच्चय सम्मिलित हैं <math>S_x</math> तत्वों के लिए <math>x</math> ऐसा है कि <math>T\cup\{x\}</math> व्यवहार्य है। अर्थात्, जाली में अद्वितीय मिल-इरेड्यूसबल अपघटन होते हैं।
+* विवरण मूल रूप से माना जाता है {{harvtxt|दिलवर्थ|1940}} चिंता फिल्टर (आदेश) महत्वपूर्ण फिल्टर-सैद्धांतिक धारणा पर निर्भर रहता हैं। इस प्रकार प्रत्येक तत्व के लिए <math>x</math> एंटीमैट्रोइड का, अद्वितीय अधिकतम संभव समुच्चय सम्मिलित है <math>S_x</math> जिसमें सम्मिलित नहीं है <math>x</math>: <math>S_x</math> सम्‍मिलित नहीं सभी संभव समुच्चयों के संघ के रूप में निर्मित किया जा सकता है <math>x</math>. यह समुच्चय <math>S_x</math> स्वचालित रूप से मिलने-अपूरणीय है, जिसका अर्थ है कि यह किसी भी दो बड़े फिल्टर तत्वों का मिलन नहीं है। यह सच है क्योंकि का हर संभव सुपरसमुच्चय <math>S_x</math> रोकना <math>x</math>, और इसलिए यह संभव सुपरसमुच्चय के हर अंतः खण्ड के बारे में भी सच है। मनमाना फिल्टर के प्रत्येक तत्व को मीट-इरिड्यूसिबल समुच्चय के मिलन के रूप में विघटित किया जा सकता है, प्रायः कई तरीकों से, किन्तु फिल्टर में प्रत्येक तत्व एंटीमैट्रोइड के अनुरूप होता है। <math>T</math> मीट-इरिड्यूसिबल समुच्चय का अनूठा न्यूनतम समूह है जिसका मिलन है <math>T</math>; इस समूह में समुच्चय सम्मिलित हैं <math>S_x</math> तत्वों के लिए <math>x</math> ऐसा है कि <math>T\cup\{x\}</math> व्यवहारिक रूप से निर्भर करता हैं। अर्थात्, फिल्टर में अद्वितीय मिल-इरेड्यूसबल अपघटन होते हैं।
-* एक दूसरा लक्षण वर्णन जाली में अंतरालों की चिंता करता है, जाली तत्वों की जोड़ी द्वारा परिभाषित उप-वर्ग <math>x\le y</math> सभी जाली तत्वों से मिलकर <math>z</math> साथ <math>x\le z\le y</math>. अंतराल [[परमाणु (आदेश सिद्धांत)]] है यदि इसमें प्रत्येक तत्व परमाणुओं का जुड़ाव है (नीचे के तत्व के ऊपर न्यूनतम तत्व <math>x</math>), और यह [[बूलियन बीजगणित (संरचना)]] है यदि यह परिमित समुच्चय के [[ सत्ता स्थापित |सत्ता स्थापित]] के जाली के लिए आइसोमोर्फिक है। एंटीमैट्रोइड के लिए, प्रत्येक अंतराल जो कि परमाणुवादी है, बूलियन भी है।
+* एक दूसरा लक्षण वर्णन फिल्टर में अंतरालों की चिंता करता है, फिल्टर तत्वों की जोड़ी द्वारा परिभाषित उप-वर्ग <math>x\le y</math> सभी फिल्टर तत्वों से मिलकर <math>z</math> साथ <math>x\le z\le y</math>. अंतराल [[परमाणु (आदेश सिद्धांत)]] है यदि इसमें प्रत्येक तत्व परमाणुओं का जुड़ाव है (नीचे के तत्व के ऊपर न्यूनतम तत्व <math>x</math>), और यह [[बूलियन बीजगणित (संरचना)]] है यदि यह परिमित समुच्चय के [[ सत्ता स्थापित |सत्ता स्थापित]] के फिल्टर के लिए आइसोमोर्फिक है। एंटीमैट्रोइड के लिए, प्रत्येक अंतराल जो कि परमाणुवादी है, बूलियन भी है।
-*तीसरे, एंटीमैट्रोइड्स से उत्पन्न होने वाली जाली अर्ध-मॉड्यूलर जाली हैं, जाली जो अर्ध-मॉड्यूलर जाली को संतुष्ट करती हैं जो हर दो तत्वों के लिए होती हैं <math>x</math> और <math>y</math>, यदि <math>y</math> कवर <math>x\wedge y</math> तब <math>x\vee y</math> कवर <math>x</math>. यदि संभव हो तो इस स्थिति को एंटीमैट्रोइड के व्यवहार्य समुच्चय में अनुवाद करना <math>Y</math> केवल तत्व है जो किसी अन्य व्यवहार्य समुच्चय से संबंधित नहीं है <math>X</math> तो उस तत्व को जोड़ा जा सकता है <math>X</math> एंटीमैट्रोइड में और समुच्चय बनाने के लिए। इसके अतिरिक्त, एंटीमैट्रोइड की जाली में मीट-सेमीडिस्ट्रीब्यूशन संपत्ति होती है: सभी जाली तत्वों के लिए <math>x</math>, <math>y</math>, और <math>z</math>, यदि <math>x\wedge y</math> और <math>x\wedge z</math> दूसरे के बराबर तो वे दोनों भी बराबर हैं <math>x\wedge (y\vee z)</math>. सेमीमॉड्यूलर और मीट-सेमीडिस्ट्रीब्यूशन लैटिस को जॉइन-डिस्ट्रीब्यूटिव लैटिस कहा जाता है।
+*तीसरे, एंटीमैट्रोइड्स से उत्पन्न होने वाली फिल्टर अर्ध-मॉड्यूलर फिल्टर हैं, फिल्टर जो अर्ध-मॉड्यूलर फिल्टर को संतुष्ट करती हैं जो हर दो तत्वों के लिए होती हैं <math>x</math> और <math>y</math>, यदि <math>y</math> कवर <math>x\wedge y</math> तब <math>x\vee y</math> कवर <math>x</math>. यदि संभव हो तो इस स्थिति को एंटीमैट्रोइड के व्यावहारिक समुच्चय में अनुवाद करना <math>Y</math> केवल तत्व है जो किसी अन्य व्यावहारिक समुच्चय से संबंधित नहीं है <math>X</math> तो उस तत्व को जोड़ा जा सकता है <math>X</math> एंटीमैट्रोइड में और समुच्चय बनाने के लिए। इसके अतिरिक्त, एंटीमैट्रोइड की फिल्टर में मीट-सेमीडिस्ट्रीब्यूशन संपत्ति होती है: सभी फिल्टर तत्वों के लिए <math>x</math>, <math>y</math>, और <math>z</math>, यदि <math>x\wedge y</math> और <math>x\wedge z</math> दूसरे के बराबर तो वे दोनों भी बराबर हैं <math>x\wedge (y\vee z)</math>. सेमीमॉड्यूलर और मीट-सेमीडिस्ट्रीब्यूशन लैटिस को जॉइन-डिस्ट्रीब्यूटिव लैटिस कहा जाता है।
-ये तीन विशेषताएँ समतुल्य हैं: अद्वितीय मिल-इरेड्यूसिबल अपघटन के साथ किसी भी जाली में बूलियन परमाणु अंतराल होता है और इसमें सम्मिलित-वितरण होता है, बूलियन परमाणु अंतराल के साथ किसी भी जाली में अद्वितीय मिल-इरेड्यूसिबल अपघटन होता है और यह वितरण-वितरण होता है, और किसी भी जोड़-वितरण जाली में अद्वितीय होता है मीट-इरेड्यूसिबल अपघटन और बूलियन परमाणु अंतराल।<ref>{{harvtxt|Adaricheva|Gorbunov|Tumanov|2003}}, Theorems 1.7 and 1.9; {{harvtxt|Armstrong|2009}}, Theorem 2.7.</ref> इस प्रकार, हम इन तीन गुणों में से किसी के साथ जाली को जोड़-वितरण के रूप में संदर्भित कर सकते हैं। कोई भी एंटीमैट्रोइड परिमित जॉइन-डिस्ट्रीब्यूटिव जाली को जन्म देता है, और कोई भी परिमित जॉइन-डिस्ट्रीब्यूटिव लैटिस इस तरह से एंटीमैट्रोइड से आता है।<ref>{{harvtxt|Edelman|1980}}, Theorem 3.3; {{harvtxt|Armstrong|2009}}, Theorem 2.8.</ref> परिमित ज्वाइन-डिस्ट्रीब्यूटिव लैटिस का और समकक्ष लक्षण वर्णन यह है कि वे [[ वर्गीकृत पोसेट |वर्गीकृत पोसमुच्चय]] हैं (किसी भी दो अधिकतम श्रृंखलाओं की लंबाई समान है), और अधिकतम श्रृंखला की लंबाई जाली के मिल-इरेड्यूसबल तत्वों की संख्या के बराबर होती है।<ref>{{harvtxt|Monjardet|1985}} credits a dual form of this characterization to several papers from the 1960s by S. P. Avann.</ref> परिमित जोड़-वितरण जाली का प्रतिनिधित्व करने वाले एंटीमैट्रोइड को जाली से पुनर्प्राप्त किया जा सकता है: एंटीमैट्रॉइड के तत्वों को जाली के मीट-इरिड्यूसिबल तत्वों और किसी भी तत्व के अनुरूप व्यवहार्य समुच्चय के रूप में लिया जा सकता है। <math>x</math> जाली में मिलने-इरेड्यूसबल तत्वों का समुच्चय होता है <math>y</math> ऐसा है कि <math>y</math> से अधिक या बराबर नहीं है <math>x</math> जाली में।
+ये तीन विशेषताएँ समतुल्य हैं: अद्वितीय मिल-इरेड्यूसिबल अपघटन के साथ किसी भी फिल्टर में बूलियन परमाणु अंतराल होता है और इसमें सम्मिलित-वितरण होता है, बूलियन परमाणु अंतराल के साथ किसी भी फिल्टर में अद्वितीय मिल-इरेड्यूसिबल अपघटन होता है और यह वितरण-वितरण होता है, किसी भी जोड़-वितरण फिल्टर में अद्वितीय होता है मीट-इरेड्यूसिबल अपघटन और बूलियन परमाणु अंतराल।<ref>{{harvtxt|Adaricheva|Gorbunov|Tumanov|2003}}, Theorems 1.7 and 1.9; {{harvtxt|Armstrong|2009}}, Theorem 2.7.</ref> इस प्रकार, हम इन तीन गुणों में से किसी के साथ फिल्टर को जोड़-वितरण के रूप में संदर्भित कर सकते हैं। कोई भी एंटीमैट्रोइड परिमित जॉइन-डिस्ट्रीब्यूटिव फिल्टर को जन्म देता है, और कोई भी परिमित जॉइन-डिस्ट्रीब्यूटिव लैटिस इस तरह से एंटीमैट्रोइड से आता है।<ref>{{harvtxt|Edelman|1980}}, Theorem 3.3; {{harvtxt|Armstrong|2009}}, Theorem 2.8.</ref> इस प्रकार परिमित ज्वाइन-डिस्ट्रीब्यूटिव लैटिस का और समकक्ष लक्षण वर्णन यह है कि वे [[ वर्गीकृत पोसेट |वर्गीकृत पोसमुच्चय]] हैं (किसी भी दो अधिकतम श्रृंखलाओं की लंबाई समान है), और अधिकतम श्रृंखला की लंबाई फिल्टर के मिल-इरेड्यूसबल तत्वों की संख्या के बराबर होती है।<ref>{{harvtxt|Monjardet|1985}} credits a dual form of this characterization to several papers from the 1960s by S. P. Avann.</ref> परिमित जोड़-वितरण फिल्टर का प्रतिनिधित्व करने वाले एंटीमैट्रोइड को फिल्टर से पुनर्प्राप्त किया जा सकता है: एंटीमैट्रॉइड के तत्वों को फिल्टर के मीट-इरिड्यूसिबल तत्वों और किसी भी तत्व के अनुरूप व्यावहारिक समुच्चय के रूप में लिया जा सकता है। <math>x</math> फिल्टर में मिलने-इरेड्यूसबल तत्वों का समुच्चय होता है <math>y</math> ऐसा है कि <math>y</math> से अधिक या बराबर नहीं है <math>x</math> फिल्टर में प्रयोग किया जाता हैं।
-यूनियनों के अनुसार बंद किए गए समुच्चयों के सुलभ परिवार के रूप में किसी भी परिमित ज्वाइन-डिस्ट्रीब्यूटिव जाली का प्रतिनिधित्व (जो कि एंटीमैट्रॉइड के रूप में है) को बिरखॉफ के प्रतिनिधित्व प्रमेय के एनालॉग के रूप में देखा जा सकता है, जिसके अनुसार किसी भी परिमित वितरण जाली का समुच्चय के परिवार के रूप में प्रतिनिधित्व होता है। यूनियनों और चौराहों के नीचे बंद।
+यूनियनों के अनुसार बंद किए गए समुच्चयों के सुलभ समूह के रूप में किसी भी परिमित ज्वाइन-डिस्ट्रीब्यूटिव फिल्टर का प्रतिनिधित्व (जो कि एंटीमैट्रॉइड के रूप में है) को बिरखॉफ के प्रतिनिधित्व प्रमेय के एनालॉग के रूप में देखा जा सकता है, जिसके अनुसार किसी भी परिमित वितरण फिल्टर का समुच्चय के समूह के रूप में प्रतिनिधित्व होता है। यूनियनों और अंतः खण्डों के नीचे बंद रहता हैं।
 == सुपरसॉल्वेबल एंटीमैट्रोइड्स ==
-[[कॉक्सेटर समूह|कॉक्समुच्चयर समूह]] के तत्वों पर आंशिक आदेशों को परिभाषित करने की समस्या से प्रेरित होकर, {{harvtxt|आर्मस्ट्रांग|2009}} ने एंटीमैट्रोइड्स का अध्ययन किया जो सुपरसॉल्वेबल लैटिस भी हैं। सुपरसॉल्वेबल एंटीमैट्रोइड को तत्वों के कुल ऑर्डर संग्रह और इन तत्वों के समुच्चय के परिवार द्वारा परिभाषित किया गया है। परिवार को खाली समुच्चय सम्मिलित करना चाहिए। इसके अतिरिक्त, इसमें संपत्ति होनी चाहिए कि यदि दो समुच्चय हो <math>A</math> और <math>B</math> परिवार से संबंधित हैं, यदि [[सेट-सैद्धांतिक अंतर|समुच्चय-सैद्धांतिक अंतर]] <math>B\setminus A</math> खाली नहीं है, और यदि <math>x</math> का सबसे छोटा तत्व है <math>B\setminus A</math>, तब <math>A\cup\{x\}</math> परिवार का भी है। जैसा कि आर्मस्ट्रांग ने देखा है, इस प्रकार के समुच्चयों का कोई भी परिवार एंटीमैट्रोइड बनाता है। आर्मस्ट्रांग एंटीमैट्रोइड्स का जाली-सैद्धांतिक लक्षण वर्णन भी प्रदान करता है जो यह निर्माण बना सकता है।{{sfnp|Armstrong|2009}}
+[[कॉक्सेटर समूह|कॉक्समुच्चयर समूह]] के तत्वों पर आंशिक आदेशों को परिभाषित करने की समस्या से प्रेरित होकर, {{harvtxt|आर्मस्ट्रांग|2009}} ने एंटीमैट्रोइड्स का अध्ययन किया जो सुपरसॉल्वेबल लैटिस भी हैं। सुपरसॉल्वेबल एंटीमैट्रोइड को तत्वों के कुल ऑर्डर संग्रह और इन तत्वों के समुच्चय के समूह द्वारा परिभाषित किया गया है। समूह को रिक्त समुच्चय सम्मिलित करना चाहिए। इसके अतिरिक्त, इसमें संपत्ति होनी चाहिए कि यदि दो समुच्चय हो <math>A</math> और <math>B</math> समूह से संबंधित हैं, यदि [[सेट-सैद्धांतिक अंतर|समुच्चय-सैद्धांतिक अंतर]] <math>B\setminus A</math> रिक्त नहीं है, और यदि <math>x</math> का सबसे छोटा तत्व है <math>B\setminus A</math>, तब <math>A\cup\{x\}</math> समूह का भी है। जैसा कि आर्मस्ट्रांग ने देखा है, इस प्रकार के समुच्चयों का कोई भी समूह एंटीमैट्रोइड बनाता है। आर्मस्ट्रांग एंटीमैट्रोइड्स का फिल्टर-सैद्धांतिक लक्षण वर्णन भी प्रदान करता है जो यह निर्माण बना सकता है।{{sfnp|Armstrong|2009}}
 == संचालन और उत्तल आयाम में सम्मिलित हों ==
-यदि <math>\mathcal{A}</math> और <math>\mathcal{B}</math> दो एंटीमैट्रोइड्स हैं, दोनों को तत्वों के ही ब्रह्मांड पर समुच्चय के परिवार के रूप में वर्णित किया गया है, फिर और एंटीमैट्रोइड, का जुड़ाव <math>\mathcal{A}</math> और <math>\mathcal{B}</math>, इस प्रकार बनाया जा सकता है:<math display=block>\mathcal{A}\vee\mathcal{B} = \{ S\cup T \mid S\in\mathcal{A}\wedge T\in\mathcal{B}\}.</math>यह एंटीमैट्रोइड्स के जाली-सैद्धांतिक लक्षण वर्णन में सम्मिलित होने की तुलना में अलग ऑपरेशन है: यह दो एंटीमैट्रोइड्स को और एंटीमैट्रोइड बनाने के लिए जोड़ता है, अतिरिक्त एंटीमैट्रोइड में दो समुच्चयों को मिलाकर और समुच्चय बनाने के लिए।
+यदि <math>\mathcal{A}</math> और <math>\mathcal{B}</math> दो एंटीमैट्रोइड्स हैं, दोनों को तत्वों के ही ब्रह्मांड पर समुच्चय के समूह के रूप में वर्णित किया गया है, फिर और एंटीमैट्रोइड, का जुड़ाव <math>\mathcal{A}</math> और <math>\mathcal{B}</math>, इस प्रकार बनाया जा सकता है:<math display=block>\mathcal{A}\vee\mathcal{B} = \{ S\cup T \mid S\in\mathcal{A}\wedge T\in\mathcal{B}\}.</math>यह एंटीमैट्रोइड्स के फिल्टर-सैद्धांतिक लक्षण वर्णन में सम्मिलित होने की तुलना में अलग ऑपरेशन है: यह दो एंटीमैट्रोइड्स को और एंटीमैट्रोइड बनाने के लिए जोड़ता है, अतिरिक्त एंटीमैट्रोइड में दो समुच्चयों को मिलाकर और समुच्चय बनाने के लिए किया जाता हैं।
-एक ही ब्रह्मांड पर सभी एंटीमैट्रोइड्स का परिवार इस सम्मिलित ऑपरेशन के साथ अर्धजाल बनाता है।<ref>{{harvtxt|Korte|Lovász|Schrader|1991}}, p. 42; {{harvtxt|Eppstein|2008}}, Section 7.2; {{harvtxt|Falmagne|Albert|Doble|Eppstein|2013}}, section 14.4.</ref>
+एक ही ब्रह्मांड पर सभी एंटीमैट्रोइड्स का समूह इस सम्मिलित ऑपरेशन के साथ अर्धफिल्टर बनाता है।<ref>{{harvtxt|Korte|Lovász|Schrader|1991}}, p. 42; {{harvtxt|Eppstein|2008}}, Section 7.2; {{harvtxt|Falmagne|Albert|Doble|Eppstein|2013}}, section 14.4.</ref>
-जॉइन क्लोजर ऑपरेशन से निकटता से संबंधित हैं जो औपचारिक भाषाओं को एंटीमैट्रोइड्स में मैप करता है, जहां भाषा को बंद किया जाता है <math>\mathcal{L}</math> युक्त सभी एंटीमैट्रोइड्स का प्रतिच्छेदन है <math>\mathcal{L}</math> उपभाषा के रूप में। इस क्लोजर ने अपनी व्यवहार्यता के रूप में स्ट्रिंग्स के उपसर्गों के संघों को समुच्चय किया है <math>\mathcal{L}</math>. इस क्लोजर ऑपरेशन के संदर्भ में, जॉइन की भाषाओं के मिलन का क्लोजर है <math>\mathcal{A}</math> और <math>\mathcal{B}</math>. प्रत्येक एंटीमैट्रोइड को चेन एंटीमैट्रोइड्स के परिवार में सम्मिलित होने के रूप में या मूल शब्दों के समुच्चय को बंद करने के रूप में प्रदर्शित किया जा सकता है; एंटीमैट्रोइड का उत्तल आयाम <math>\mathcal{A}</math> इस तरह के प्रतिनिधित्व में चेन एंटीमैट्रोइड्स की न्यूनतम संख्या (या समान रूप से मूल शब्दों की न्यूनतम संख्या) है। यदि <math>\mathfrak{F}</math> चेन एंटीमेट्रोइड्स का परिवार है जिसके मूल शब्द सभी से संबंधित हैं <math>\mathcal{A}</math>, तब <math>\mathfrak{F}</math> उत्पन्न करता है <math>\mathcal{A}</math> यदि और केवल यदि व्यवहार्य समुच्चय <math>\mathfrak{F}</math> के सभी पथ सम्मिलित करें <math>\mathcal{A}</math>. के रास्ते <math>\mathcal{A}</math> एकल श्रृंखला एंटीमैट्रोइड से संबंधित पथ पोसमुच्चय में [[श्रृंखला (आदेश सिद्धांत)]] बनाना चाहिए <math>\mathcal{A}</math>, इसलिए एंटीमैट्रोइड का उत्तल आयाम पथ पोसमुच्चय को कवर करने के लिए आवश्यक जंजीरों की न्यूनतम संख्या के बराबर होता है, जो दिलवर्थ के प्रमेय द्वारा पथ पोसमुच्चय की चौड़ाई के बराबर होता है।<ref>{{harvtxt|Edelman|Saks|1988}}; {{harvtxt|Korte|Lovász|Schrader|1991}}, Theorem 6.9.</ref>
-यदि किसी के पास समुच्चय के बंद होने के रूप में एंटीमेट्रोइड का प्रतिनिधित्व है <math>d</math> मूल शब्द, तो इस प्रतिनिधित्व का उपयोग एंटीमैट्रोइड के संभावित समुच्चयों को इंगित करने के लिए मैप करने के लिए किया जा सकता है <math>d</math>-डायमेंशनल यूक्लिडियन स्पेस: प्रति बेसिक शब्द के लिए कोऑर्डिनेट असाइन करें <math>W</math>, और व्यवहार्य समुच्चय का समन्वय मान बनाएं <math>S</math> के सबसे लंबे उपसर्ग की लंबाई हो <math>W</math> यह उपसमुच्चय है <math>S</math>. इस एम्बेडिंग के साथ, <math>S</math> अन्य व्यवहार्य समुच्चय का उपसमुच्चय है <math>T</math> यदि और केवल यदि के लिए निर्देशांक <math>S</math> सभी के संगत निर्देशांक से कम या उसके बराबर हैं <math>T</math>. इसलिए, व्यवहार्य समुच्चयों के समावेशन क्रम का क्रम आयाम एंटीमैट्रोइड के उत्तल आयाम के बराबर है।{{sfnp|Korte|Lovász|Schrader|1991|loc=Corollary 6.10}} चूंकि, सामान्य तौर पर ये दो आयाम बहुत भिन्न हो सकते हैं: आदेश आयाम तीन के साथ एंटीमैट्रोइड्स सम्मिलित हैं किन्तु मनमाने ढंग से बड़े उत्तल आयाम के साथ।{{sfnp|Eppstein|2008|loc=Figure 15}}
+जॉइन क्लोजर ऑपरेशन से निकटता से संबंधित हैं जो औपचारिक भाषाओं को एंटीमैट्रोइड्स में मैप करता है, जहां भाषा <math>\mathcal{L}</math> को बंद किया जाता है  युक्त सभी एंटीमैट्रोइड्स का प्रतिच्छेदन है <math>\mathcal{L}</math> उपभाषा के रूप में। इस क्लोजर ने अपनी व्यावहारिकता के रूप में स्ट्रिंग्स के उपसर्गों के संघों को समुच्चय किया है <math>\mathcal{L}</math>. इस क्लोजर ऑपरेशन के संदर्भ में, जॉइन की भाषाओं के मिलन का क्लोजर है <math>\mathcal{A}</math> और <math>\mathcal{B}</math>. प्रत्येक एंटीमैट्रोइड को चेन एंटीमैट्रोइड्स के समूह में सम्मिलित होने के रूप में या मूल शब्दों के समुच्चय को बंद करने के रूप में प्रदर्शित किया जा सकता है, एंटीमैट्रोइड का उत्तल आयाम <math>\mathcal{A}</math> इस तरह के प्रतिनिधित्व में चेन एंटीमैट्रोइड्स की न्यूनतम संख्या (या समान रूप से मूल शब्दों की न्यूनतम संख्या) है। यदि <math>\mathfrak{F}</math> चेन एंटीमेट्रोइड्स का समूह है जिसके मूल शब्द सभी से संबंधित हैं <math>\mathcal{A}</math>, तब <math>\mathfrak{F}</math> उत्पन्न करता है, <math>\mathcal{A}</math> यदि व्यावहारिक समुच्चय <math>\mathfrak{F}</math> के सभी पथ सम्मिलित करें <math>\mathcal{A}</math>. के रास्ते <math>\mathcal{A}</math> एकल श्रृंखला एंटीमैट्रोइड से संबंधित पथ पोसमुच्चय में [[श्रृंखला (आदेश सिद्धांत)]] बनाना चाहिए <math>\mathcal{A}</math>, इसलिए एंटीमैट्रोइड का उत्तल आयाम पथ पोसमुच्चय को कवर करने के लिए आवश्यक जंजीरों की न्यूनतम संख्या के बराबर होता है, जो दिलवर्थ के प्रमेय द्वारा पथ पोसमुच्चय की चौड़ाई के बराबर होता है।<ref>{{harvtxt|Edelman|Saks|1988}}; {{harvtxt|Korte|Lovász|Schrader|1991}}, Theorem 6.9.</ref>
+यदि किसी के पास समुच्चय के बंद होने के रूप में एंटीमेट्रोइड का प्रतिनिधित्व है <math>d</math> मूल शब्द, तो इस प्रतिनिधित्व का उपयोग एंटीमैट्रोइड के संभावित समुच्चयों को इंगित करने के लिए मैप करने के लिए किया जा सकता है <math>d</math>-डायमेंशनल यूक्लिडियन स्पेस: प्रति बेसिक शब्द के लिए कोऑर्डिनेट असाइन करें <math>W</math>, और व्यावहारिक समुच्चय का समन्वय मान बनाएं <math>S</math> के सबसे लंबे उपसर्ग की लंबाई हो <math>W</math> यह उपसमुच्चय <math>S</math> है। इस एम्बेडिंग के साथ, <math>S</math> अन्य व्यावहारिक समुच्चय का उपसमुच्चय है <math>T</math> यदि और केवल यदि के लिए निर्देशांक <math>S</math> सभी के संगत निर्देशांक से कम या उसके बराबर हैं <math>T</math>. इसलिए, व्यावहारिक समुच्चयों के समावेशन क्रम का क्रम आयाम एंटीमैट्रोइड के उत्तल आयाम के बराबर है।{{sfnp|Korte|Lovász|Schrader|1991|loc=Corollary 6.10}} चूंकि, सामान्यतः ये दो आयाम बहुत भिन्न हो सकते हैं: आदेश आयाम तीन के साथ एंटीमैट्रोइड्स सम्मिलित हैं किन्तु मनमाने ढंग से बड़े उत्तल आयाम के साथ उपलब्ध रहता हैं।{{sfnp|Eppstein|2008|loc=Figure 15}}
 == गणना ==
@@ Line 82: / Line 84: @@
 == अनुप्रयोग ==
-सैद्धांतिक शेड्यूलिंग समस्याओं के लिए मानक संकेतन में पूर्वता और रिलीज समय की कमी दोनों को एंटीमैट्रोइड्स द्वारा प्रतिरूपित किया जा सकता है। {{harvtxt|बॉयड|फैगल|1990}} [[यूजीन लॉलर]] के [[लालची एल्गोरिदम]] को सामान्यीकृत करने के लिए एंटीमैट्रोइड्स का उपयोग प्राथमिकता बाधाओं के साथ एकल-प्रोसेसर शेड्यूलिंग समस्याओं को उत्तम ढंग से हल करने के लिए करता है जिसमें लक्ष्य किसी कार्य के देर से शेड्यूलिंग द्वारा किए गए अधिकतम दंड को कम करना है।
+सैद्धांतिक शेड्यूलिंग समस्याओं के लिए मानक संकेतन में पूर्वता और रिलीज समय की कमी दोनों को एंटीमैट्रोइड्स द्वारा प्रतिरूपित किया जा सकता है। {{harvtxt|बॉयड|फैगल|1990}} [[यूजीन लॉलर]] के [[लालची एल्गोरिदम]] को सामान्यीकृत करने के लिए एंटीमैट्रोइड्स का उपयोग प्राथमिकता बाधाओं के साथ एकल-प्रोसेसर शेड्यूलिंग समस्याओं को उत्तम ढंग से हल करने के लिए करता है, जिसमें लक्ष्य किसी कार्य के देर से शेड्यूलिंग द्वारा किए गए अधिकतम दंड को कम करना है।
-{{harvtxt|ग्लासमैन|याओ|1994}} [[असतत घटना सिमुलेशन]] सिस्टम में घटनाओं के क्रम को मॉडल करने के लिए एंटीमैट्रोइड्स का उपयोग करें।
+{{harvtxt|ग्लासमैन|याओ|1994}} [[असतत घटना सिमुलेशन]] सिस्टम में घटनाओं के क्रम को मॉडल करने के लिए एंटीमैट्रोइड्स का उपयोग करते हैं।
 {{harvtxt|परमार|2003}} आर्टिफिशियल इंटेलिजेंस [[स्वचालित योजना और शेड्यूलिंग]] समस्याओं में लक्ष्य की दिशा में प्रगति को मॉडल करने के लिए एंटीमैट्रोइड्स का उपयोग करता है।
@@ Line 90: / Line 92: @@
 [[इष्टतमता सिद्धांत]] में, बाधाओं के अनुसार अनुकूलन के आधार पर [[प्राकृतिक भाषा]] के विकास के लिए गणितीय मॉडल, व्याकरण तार्किक रूप से एंटीमैट्रोइड्स के बराबर है।{{sfnp|Merchant|Riggle|2016}}
-[[गणितीय मनोविज्ञान]] में, मानव शिक्षार्थी के [[ज्ञान स्थान]] का वर्णन करने के लिए एंटीमैट्रोइड्स का उपयोग किया गया है। एंटीमैट्रोइड का प्रत्येक तत्व अवधारणा का प्रतिनिधित्व करता है जिसे शिक्षार्थी द्वारा समझा जाना है, या समस्याओं का वर्ग जिसे वह सही ढंग से हल करने में सक्षम हो सकता है, और एंटीमेट्रोइड बनाने वाले तत्वों के समुच्चय उन अवधारणाओं के संभावित समुच्चय का प्रतिनिधित्व करते हैं जो हो सकते हैं व्यक्ति द्वारा समझा गया। एंटीमेट्रोइड को परिभाषित करने वाले सिद्धांतों को अनौपचारिक रूप से कहा जा सकता है कि अवधारणा को सीखने से शिक्षार्थी को दूसरी अवधारणा को सीखने से रोका नहीं जा सकता है, और समय में ही अवधारणा को सीखकर ज्ञान की किसी भी व्यवहार्य स्थिति तक पहुंचा जा सकता है। ज्ञान मूल्यांकन प्रणाली का कार्य किसी दिए गए शिक्षार्थी द्वारा ज्ञात अवधारणाओं के समुच्चय का अनुमान लगाना है, जो समस्याओं के छोटे और अच्छी तरह से चुने गए समुच्चय पर उसकी प्रतिक्रियाओं का विश्लेषण करता है। इस संदर्भ में एंटीमैट्रोइड्स को सीखने के स्थान और अच्छी तरह से वर्गीकृत ज्ञान स्थान भी कहा जाता है।{{sfnp|Doignon|Falmagne|1999}}
+[[गणितीय मनोविज्ञान]] में, मानव शिक्षार्थी के [[ज्ञान स्थान]] का वर्णन करने के लिए एंटीमैट्रोइड्स का उपयोग किया गया है। एंटीमैट्रोइड का प्रत्येक तत्व अवधारणा का प्रतिनिधित्व करता है जिसे शिक्षार्थी द्वारा समझा जाना है, या समस्याओं का वर्ग जिसे वह सही ढंग से हल करने में सक्षम हो सकता है, और एंटीमेट्रोइड बनाने वाले तत्वों के समुच्चय उन अवधारणाओं के संभावित समुच्चय का प्रतिनिधित्व करते हैं जो हो सकते हैं व्यक्ति द्वारा समझा जाता हैं। एंटीमेट्रोइड को परिभाषित करने वाले सिद्धांतों को अनौपचारिक रूप से कहा जा सकता है कि अवधारणा को सीखने से शिक्षार्थी को दूसरी अवधारणा को सीखने से रोका नहीं जा सकता है, और समय में ही अवधारणा को सीखकर ज्ञान की किसी भी व्यावहारिक स्थिति तक पहुंचा जा सकता है। ज्ञान मूल्यांकन प्रणाली का कार्य किसी दिए गए शिक्षार्थी द्वारा ज्ञात अवधारणाओं के समुच्चय का अनुमान लगाना है, जो समस्याओं के छोटे और अच्छी तरह से चुने गए समुच्चय पर उसकी प्रतिक्रियाओं का विश्लेषण करता है। इस संदर्भ में एंटीमैट्रोइड्स को सीखने के स्थान और अच्छी तरह से वर्गीकृत ज्ञान स्थान भी कहा जाता है।{{sfnp|Doignon|Falmagne|1999}}
 ==टिप्पणियाँ==

Anonymous

Search

एंटीमैट्रोइड: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:02, 13 March 2023

Contents

परिभाषाएँ

उदाहरण

पथ और मूल शब्द

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

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

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

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

गणना

अनुप्रयोग

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

एंटीमैट्रोइड: Difference between revisions

Revision as of 23:02, 13 March 2023

परिभाषाएँ

उदाहरण

पथ और मूल शब्द

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

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

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

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

गणना

अनुप्रयोग

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories