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

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

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

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

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

परिभाषाएँ

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

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

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

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

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

उदाहरण

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

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

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

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

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

(कहाँ $\varepsilon$ खाली स्ट्रिंग को दर्शाता है) और जैसा कि संभव है इसका परिवार परिवार को सेट करता है

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

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

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

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

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

सही निष्कासन

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

चिप फायरिंग का खेल

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

पथ और मूल शब्द

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

हर संभव सेट के लिए $S$ एंटीमैट्रोइड में, और हर तत्व $x$ का $S$, किसी का पथ उपसमुच्चय मिल सकता है $S$ जिसके लिए $x$ एक समापन बिंदु है: ऐसा करने के लिए, के अलावा अन्य तत्वों को एक समय में हटा दें