.
Στα μαθηματικά, αντιματροειδές είναι ένα φορμαλιστικό σύστημα το οποίο περιγράφει διαδικασίες κατά τις οποίες ένα σύνολο κατασκευάζεται τοποθετώντας τα στοιχεία ένα τη φορά, και ένα στοιχείο, το οποίο έχει καταστεί διαθέσιμο ώστε να συμπεριληφθεί, παραμένει διαθέσιμο μέχρι να συμπεριληφθεί. Τα αντιματροειδή συνήθως ορίζονται αξιωματικά με δύο ισοδύναμους τρόπους, είτε σαν ένα σύστημα συνόλων το οποίο μοντελοποιεί τις πιθανές καταστάσεις μιας τέτοιας διαδικασίας, είτε σαν μια φορμαλιστική γλώσσα η οποία μοντελοποιεί τις διαφορετικές ακολουθίες στις οποίες τα στοιχεία μπορεί να συμπεριλαμβάνονται. Ο Dilworth (1940) ήταν ο πρώτος που μελέτησε τα αντιματροειδή, εφαρμόζοντας μία διαφορετική αξιωματική προσέγγιση βασισμένη στη θεωρία μερικώς διατεταγμένων συνόλων, και έχουν ανακαλυφθεί και σε άλλα πλαίσια:[1] βλέπε Korte et al. (1991) για μια εκτενή έρευνα της θεωρίας αντιματροειδών με πλήθος πρόσθετων πηγών.
Τα αξιώματα που ορίζουν τα αντιματροειδή ως σύστημα συνόλων είναι παραπλήσια με τα αξιώματα των ματροειδών, αλλά ενώ τα ματροειδή ορίζονται μέσω ενός αξιώματος ανταλλαγής, τα αντιματροειδή ορίζονται μέσω ενός αξιώματος αντι-ανταλλαγής, από το οποίο πηγάζει και η ονομασία τους. Τα αντιματροειδή μπορούν να θεωρηθούν ως ειδική περίπτωση των greedoids και των ημισυναρμολογούμενων μερικώς διατεταγμένων συνόλων, και ως γενίκευση των μερικώς διατεταγμένων συνόλων και των επιμεριστικών μερικώς διατατεγμένων συνόλων. Τα αντιματροειδή είναι ισοδύναμα, μέσω της συμπλήρωσης, με τις κυρτές γεωμετρίες, μια αφηρημένη συνδυαστική θεώρηση των κυρτών συνόλων στη Γεωμετρία.
Τα αντιματροειδή έχουν χρησιμοποιηθεί για να μοντελοποιήσουν φραγμούς προτεραιότητας σε προβλήματα προγραμματισμού, πιθανές ακολουθίες γεγονότων σε προσομοιώσεις, σχεδιασμό εργασιών στην τεχνητή νοημοσύνη, και τις καταστάσεις της ανθρώπινης γνώσης.
Ορισμοί
Ένα αντιματροειδές μπορεί να ορισθεί ως μία πεπερασμένη οικογένεια F συνόλων, που αποκαλούνται εφικτά σύνολα, με τις δύο ακόλουθες ιδιότητες:
Η ένωση δύο οποιωνδήποτε εφικτών συνόλων είναι επίσης εφικτό σύνολο. Δηλαδή, η F είναι κλειστή ως προς την ένωση.
Αν S ένα μη κενό εφικτό σύνολο, τότε υπάρχει κάποιο x στο S έτσι ώστε το \( S \ {x} να είναι επίσης εφικτό. Δηλαδή, η F είναι ένα προσβάσιμο σύστημα συνόλων.
Τα αντιματροειδή έχουν επίσης έναν ισοδύναμο ορισμό ως φορμαλιστική γλώσσα, δηλαδή ως ένα σύνολο συμβολοσειρών ορισμένων από ένα πεπερασμένο αλφάβητο συμβόλων. Μια γλώσσα L, η οποία ορίζει ένα αντιματροειδές, πρέπει να ικανοποιεί τις ακόλουθες ιδιότητες:
Κάθε σύμβολο του αλφάβητου εμφανίζεται σε τουλάχιστον μία λέξη της L.
Κάθε λέξη της L περιέχει το πολύ μία φορά κάθε σύμβολο.
Κάθε πρόθεμα μιας συμβολοσειράς της L ανήκει επίσης στην L.
Αν s και t συμβολοσειρές της L, και η s περιέχει τουλάχιστον ένα σύμβολο το οποίο δεν περιέχεται στην t, τότε υπάρχει σύμβολο x στην s τέτοιο ώστε η tx να είναι άλλη συμβολοσειρά του L.
Αν L είναι ένα αντιματροειδές ορισμένο ως φορμαλιστική γλώσσα, τότε τα σύνολα των συμβόλων των συμβολοσειρών της L αποτελούν ένα προσβάσιμο σύστημα συνόλων, κλειστό ως προς την ένωση. Στην άλλη περίπτωση, αν F είναι ένα προσβάσιμο σύστημα συνόλων, κλειστό ως προς την ένωση, και L είναι η γλώσσα των συμβολοσειρών s με την ιδιότητα ότι το σύνολο των συμβόλων σε κάθε πρόθεμα του s είναι εφικτό, τότε η L ορίζει ένα αντιματροειδές. Επομένως, οι δύο ορισμοί οδηγούν σε μαθηματικά ισοδύναμες κλάσεις αντικειμένων.[2]
Παραδείγματα
Μια κελυφωτή ακολουθία ενός συνόλου σημείων του επιπέδου. Τα ευθύγραμμα τμήματα δείχνουν τις άκρες των κυρτών περιβλημάτων μετά την αφαίρεση κάποιων σημείων.
Μία αντιματροειδής αλυσίδα έχει ως φορμαλιστική γλώσσα του τα προθέματα μιας λέξης, και ως εφικτά σύνολα τα σύνολα των συμβόλων σε αυτά τα προθέματα. Για παράδειγμα η αντιματροειδής αλυσίδα ορισμένη από τη λέξη "abcd" έχει ως φορμαλιστική της γλώσσα τις συμβολοσειρές {ε,"a","ab","abc","abcd"} και ως εφικτά σύνολα τα σύνολα Ø ,{a}, {a,b}, {a,b,c}, και {a,b,c,d}.[3]
Ένα μερικώς διατεταγμένο αντιματροειδές έχει ως εφικτά σύνολα τα χαμηλά σύνολα ενός πεπερασμένου μερικώς διατεταγμένου συνόλου. Σύμφωνα με το θεώρημα αναπαράστασης του Birkhoff για τα επιμεριστικά πλέγματα, τα εφικτά σύνολα σε ένα μερικώς διατεταγμένο αντιματροειδές (κατά σειρά ένταξης) σχηματίζουν ένα επιμεριστικά πλέγμα και κάθε επιμεριστικό πλέγμα μπορεί να σχηματιστεί με αυτόν τον τρόπο. Έτσι τα αντιματροειδή μπορούν να ειδωθούν ως γενικεύσεις των επιμεριστικών πλεγμάτων. Μία αντιματροειδής αλυσίδα είναι μια ειδική περίπτωση ενός μερικώς διατεταγμένου αντιματροειδούς για μια ολική διάταξη.[3]
Μια κελυφωτή ακολουθία από πεπερασμένα σύνολα U σημείων του Ευκλείδειου επίπεδου ή ενός μεγαλύτερης διάστασης Ευκλείδειου χώρου είναι μια διάταξη των σημείων έτσι ώστε, για κάθε σημείο p, να υπάρχει μια ευθεία(στο Ευκλείδειο επίπεδο ή ένα υπερεπίπεδο στον ευκλείδειο χώρο) η οποία διαχωρίζει το p από όλα τα επόμενα σημεία της ακολουθίας. Ισοδύναμα, το p πρέπει να είναι μια κορυφή του κυρτού περιβλήματος αυτού και όλων των επόμενων σημείων. Οι μερικές κελυφωτές ακολουθίες ενός συνόλου σημείων σχηματίζουν ένα αντιματροειδές, το οποίο ονομάζεται κελυφωτό αντιματροειδές. Τα εφικτά σύνολα του κελυφωτού αντιματροειδούς είναι οι τομές του U με το συμπλήρωμα ενός κυρτού συνόλου.[3]
Μία διάταξη τέλειας εξάλειψης ενός διαγράμματος χορδών είναι μια διάταξη των κορυφών του έτσι ώστε, για κάθε κορυφή v, οι γείτονες του v πού εμφανίζονται στη διάταξη μετά από το v σχηματίζουν μία κλίκα. Τα προθέματα των διατάξεων τέλειας εξάλειψης ενός διαγράμματος χορδών σχηματίζουν ένα αντιματροειδές.[3]
Διαδρομές και βασικές λέξεις
Στη θεωρητική αξιωματικοποίηση ενός αντιματροειδούς μέσω συνόλων υπάρχουν συγκεκριμένα ειδικά σύνολα που ονομάζονται διαδρομές, τα οποία καθορίζουν όλο το αντιματροειδές, υπό την έννοια ότι τα σύνολα του αντιματροειδούς είναι οι ενώσεις των διαδρομών. Αν S είναι οποιοδήποτε εφικτό σύνολο του αντιματροειδούς, ένα στοιχείο x το οποίο μπορεί να μετακινηθεί από το S για να σχηματίσει ένα άλλο εφικτό σύνολο ονομάζεται καταληκτικό σημείο του S, και ένα εφικτό σύνολο το οποίο έχει ένα μόνο καταληκτικό σημείο ονομάζεται διαδρομή του αντιματροειδούς. Η οικογένεια των διαδρομών μπορεί να είναι μερικώς διατεταγμένη κατά σειρά ένταξης, σχηματίζοντας τη μερικώς διατεταγμένη διαδρομή του αντιματροειδούς.
Για κάθε εφικτό σύνολο S του αντιματροειδούς, και κάθε στοιχείο x του S, ένα μπορεί να βρεθεί μια διαδρομή υποσύνολο του S για την οποία το x είναι καταληκτικό σημείο: για να γίνει αυτό, μετακινήστε ένα τη φορά σημεία εκτός του x μέχρι καμία τέτοια μετακίνηση να αφήσει ένα εφικτό υποσύνολο. Ως εκ τούτου, κάθε εφικτό σύνολο σε ένα αντιματροειδές είναι η ένωση των διαδρομών υποσυνόλων του. Αν S δεν είναι διαδρομή, κάθε υποσύνολο σε αυτήν την ένωση είναι αυστηρό υποσύνολο του S. Αλλά, αν το S είναι το ίδιο μια διαδρομή με καταληκτικό σημείο x, κάθε αυστηρό υποσύνολο του S το οποίο ανήκει στο αντιματροειδές εξαιρεί το x. Ως εκ τούτου, οι διαδρομές ενός αντιματροειδούς είναι ακριβώς τα σύνολα τα οποία δεν είναι ίσα με τις ενώσεις των αυστηρών τους υποσυνόλων στο αντιματροειδές. Ισοδύναμα, μια δοθείσα οικογένεια συνόλων P σχηματίζει το σύνολο των διαδρομών ενός αντιματροειδούς αν και μόνον αν, για κάθε S που ανήκει στο P, η ένωση των υποσυνόλων των S του P έχει ένα λιγότερο στοιχείο από το ίδιο το S. Αν συμβαίνει αυτό, το ίδιο το F είναι η οικογένεια των ενώσεων των υποσυνόλων των P.
Στην φορμαλιστική γλώσσα φορμαλισμό ενός αντιμαστροειδούς μπορούμε επίσης να προσδιορίσουμε ένα υποσύνολο λέξεων που καθορίζουν όλη τη γλώσσα, τις βασικές λέξεις. Οι μεγαλύτερες συμβολοσειρές της L ονομάζονται βασικές λέξεις, κάθε βασική λέξη σχηματίζει μια μετάθεση ολόκληρου του αλφαβήτου. Για παράδειγμα οι βασικές λέξεις ενός μερικώς διατεταγμένου αντιματροειδούς είναι οι γραμμικές επεκτάσεις της δοθείσας μερικής διάταξης. Αν B είναι ένα σύνολο βασικών λέξεων, η L μπορεί να οριστεί από το B ως το σύνολο των προθεμάτων των λέξεων του B. Είναι συχνά βολικό να ορίζουμε αντιματροειδή από βασικές λέξεις με αυτόν τον τρόπο, αλλά δεν είναι απλό να γράψουμε έναν αξιωματικό ορισμό των αντιματροειδών σε όρους των βασικών λέξεων.
Κυρτές γεωμετρίες
Αν F το σύστημα συνόλων το οποίο ορίζει ένα αντιματροειδές, με U να είναι η ένωση των συνόλων του F, τότε η οικογένεια συνόλων \( G = \{U\setminus S\mid S\in F\} \) είναι το συμπλήρωμα των συνόλων του F και συνήθως ονομάζεται κυρτή γεωμετρία, και τα σύνολα του G ονομάζονται κυρτά σύνολα. Για παράδειγμα, σε ένα κελυφωτό αντιματροειδές, τα κυρτά σύνολα είναι οι τομές του U με τα κυρτά υποσύνολα του Ευκλείδειο χώρου μέσα στον οποίον είναι ενσωματωμένο το U.
Συμπληρωματικά στις ιδιότητες των συστημάτων συνόλων τα οποία ορίζουν αντιματροειδή, το σύστημα συνόλων που ορίζει μια κυρτή γεωμετρία πρέπει να είναι κλειστό μέσω των τομών, και για οποιοδήποτε σύνολο S του G το οποίο δεν είναι ίσο με το U πρέπει να υπάρχει ένα στοιχείο x, που δεν ανήκει στο S, το οποίο μπορεί να προστεθεί στο S ώστε να δημιουργηθεί άλλο σύνολο του G.
Μια κυρτή γεωμετρία μπορεί επίσης να ορισθεί σε όρους μια απεικόνισης κλειστότητας τ η οποία απεικονίζει οποιοδήποτε υποσύνολο του U στο ελάχιστο κλειστό του υπερσύνολο. Για να είναι μια απεικόνιση κλειστότητας, η τ πρέπει να έχει τις ακόλουθες ιδιότητες:
τ(Ø) = Ø: η κλειστότητα του κενού συνόλου είναι κενή.
Κάθε σύνολο S είναι υποσύνολο του τ(S).
Αν S υποσύνολο του T, τότε το τ(S) πρέπει να είναι υποσύνολο του τ(T).
Για κάθε σύνολο S, τ(S) = τ(τ(S)).
Η οικογένεια των κλειστών συνόλων που προκύπτουν από μια απεικόνιση κλειστότητας είναι αναγκαστικά κλειστή μέσω των τομών. Οι απεικονίσεις κλειστότητας οι οποίες ορίζουν κυρτές γεωμετρίες ικανοποιούν επίσης ένα πρόσθετο αξίωμα αντι-ανταλλαγής:
Αν κανένα από τα y και z δεν ανήκουν στο τ(S), αλλά το z ανήκει στο τ(S ∪ {y}), τότε το y δεν ανήκει στο τ(S ∪ {z}).
Μία απεικόνιση κλειστότητας που ικανοποιεί αυτό το αξίωμα ονομάζεται κλειστότητα αντι-ανταλλαγής. Αν S είναι ένα κλειστό σύνολο σε μία κλειστότητα αντι-ανταλλαγής, τότε το αξίωμα αντι-ανταλλαγής καθορίζει μια μερική διάταξη των στοιχείων που δεν ανήκουν στο S, όπου x ≤ y στην μερική διάταξη όταν το x ανήκει στο τ(S ∪ {y}). Αν x είναι ένα ελάχιστο στοιχείο αυτής της μερικής διάταξης, τότε το S ∪ {x} είναι κλειστό. Δηλαδή, η οικογένεια των κλειστών συνόλων μιας κλειστότητας αντι-ανταλλαγής έχει την ιδιότητα ότι για κάθε σύνολο εκτός του καθολικού συνόλου υπάρχει ένα στοιχείο x το οποίο μπορεί να προστεθεί σε αυτό ώστε να δημιουργηθεί ένα άλλο κλειστό σύνολο. Αυτή η ιδιότητα είναι συμπληρωματική της ιδιότητας της προσβασιμότητας των αντιματροειδών, και η ιδιότητα ότι οι τομές κλειστών συνόλων είναι κλειστές είναι συμπληρωματική της ιδιότητας ότι οι ενώσεις εφικτών συνόλων σε ένα αντιματροειδές είναι επίσης εφικτές. Συνεπώς, τα συμπληρώματα των κλειστών συνόλων οποιασδήποτε κλειστότητας αντι-ανταλλαγής δημιουργούν ένα αντιματροειδές.[4]
Συνδετικά-επιμεριστικά πλέγματα
Δύο οποιαδήποτε σύνολα σε ένα αντιματροειδές έχουν ένα μοναδικό ελάχιστο άνω φράγμα (την ένωσή τους) και ένα μοναδικό μέγιστο κάτω φράγμα (την ένωση των συνόλων του αντιματροειδούς που περιέχονται και στα δύο). Ως εκ τούτου, τα σύνολα ενός αντιματροειδούς, μερικώς διατεταγμένα κατά σειρά ένταξης, σχηματίζουν ένα πλέγμα. Ποικίλα σημαντικά χαρακτηριστικά ενός αντιματροειδούς μπορούν να ερμηνευτούν σε όρους της θεωρίας πλεγμάτων, για παράδειγμα οι διαδρομές ενός αντιματροειδούς είναι τα συνδετικά-ανάγωγα στοιχεία των αντίστοιχων πλεγμάτων, και οι βασικές λέξεις του αντιματροειδούς αντιστοιχούν στις μέγιστες αλυσίδες στο πλέγμα. Τα πλέγματα τα οποία προκύπτουν από τα αντιματροειδή με αυτόν τον τρόπο γενικεύουν τα επιμεριστικά πλέγματα, και μπορούν να χαρακτηριστούν με ποικίλους διαφορετικούς τρόπους.
Η περιγραφή αρχικά θεωρήθηκε από τον Dilworth (1940), αφορά τεμνώμενα-ανάγωγα στοιχεία του πλέγματος. Για κάθε στοιχείο x ενός αντιματροειδούς, υπάρχει ένα μοναδικό μέγιστο εφικτό σύνολο Sx το οποίο δεν περιέχει το x (Sx είναι το σύνολο όλων των εφικτών συνόλων τα οποία δεν περιέχουν το x). Το Sx είναι τεμνόμενο-ανάγωγο, το οποίο σημαίνει ότι δεν είναι η τομή δύο οποιωνδήποτε μεγαλύτερων στοιχείων του πλέγματος: κάθε μεγαλύτερο εφικτό σύνολο, και κάθε τομή μεγαλύτερων εφικτών συνόλων, περιέχει το x και έτσι δεν ισούται με το Sx. Κάθε στοιχείο κάθε πλέγματος μπορεί να αποσυντεθεί ως μια τομή των τεμνόμενα-ανάγωγων συνόλων, συχνά με διαφορετικούς τρόπους, αλλά στο πλέγμα το οποίο αντιστοιχεί σε ένα αντιματροειδές κάθε στοιχείο T έχει μια μοναδική ελάχιστη οικογένεια από τεμνόμενα-ανάγωγα σύνολα Sx των οποίων η τομή είναι το T, αυτή η οικογένεια αποτελείται από σύνολα Sx όπως το T ∪ {x} το οποίο ανήκει στο αντιματροειδές. Συνεπάγεται ότι, το πλέγμα έχει μοναδικά τεμνόμενα-ανάγωγες αποσυνθέσεις.
Ένας δεύτερος χαρακτηρισμός αφορά τα διαστήματα στο πλέγμα, τα υποπλέγματα ορίζονται από ένα ζευγάρι στοιχείων του πλέγματος x ≤ y και αποτελούνται από όλα τα στοιχεία z του πλέγματος με x ≤ z ≤ y. Ένα διάστημα είναι ατομιστικό αν κάθε στοιχείο σε αυτό είναι ένωση από άτομα (το ελάχιστο στοιχείο πάνω από το κάτω στοιχείο x), και είναι Boolean αν είναι ισομορφικό με το πλέγμα όλων των υποσυνόλων ενός πεπερασμένου συνόλου. Για ένα αντιματροειδές, κάθε διάστημα το οποίο είναι ατομιστικό είναι επίσης boolean.
Τρίτον, τα πλέγματα τα οποία προκύπτουν από τα αντιματροειδή είναι τα ημί-modular πλέγματα, πλέγματα τα οποία ικανοποιούν τον άνω ημί-modular νόμο ότι για κάθε δύο στοιχεία x και y, αν το y καλύπτει το x ∧ y τότε το x ∨ y καλύπτει το x. Μεταφράζοντας αυτή την υπόθεση στα σύνολα ενός αντιματροειδούς, αν ένα σύνολο Y έχει μόνο ένα στοιχείο το οποίο δεν ανήκει στο X τότε αυτό το ένα στοιχείο μπορεί να προστεθεί στο X για να σχηματίσει ένα άλλο σύνολο στο αντιματροειδές. Επιπροσθέτως, το πλέγμα ενός αντιματροειδούς έχει μια τεμνώμενα-ημιεπιμεριστική ιδιότητα: για όλα τα στοιχεία του πλέγματος x,y και z, αν x ∧ y και x ∧ z είναι και τα δύο ίσα τότε είναι επίσης ίσα με x ∧ (y ∨ z). ένα ημί-modular και τεμνώμενα-ημίεπιμεριστικό πλέγμα ονομάζεται συνδετικό-επιμεριστικό πλέγμα.
Αυτοί οι τρεις χαρακτηρισμοί είναι ισοδύναμα: κάθε πλέγμα με μοναδικές τεμνόμενες-επιμεριστικές αποσυνθέσεις έχει boolean ατομιστικά διαστήματα και είναι συνδετικά επιμεριστικό, κάθε πλέγμα με boolean ατομιστικά διαστήματα έχει μοναδικές τεμνώμενα-επιμεριστικές αποσυνθέσεις και είναι συνδετικό-επιμεριστικό, και κάθε συνδετικό-επιμεριστικό πλέγμα έχει μοναδικά τεμνώμενα-επιμεριστικές αποσυνθέσεις και boolean ατομιστικά διαστήματα.[5] Έτσι, μπορούμε να αναφερθούμε σε ένα πλέγμα με καθεμία από αυτές τις τρεις ιδιότητες σαν συνδετικό-επιμεριστικό. Κάθε αντιματροειδές δημιουργεί ένα πεπερασμένο συνδετικό-επιμεριστικό πλέγμα, και κάθε πεπερασμένο συνδετικό-επιμεριστικό πλέγμα παράγεται από ένα αντιματροειδές με αυτόν τον τρόπο.[6] Άλλο ισοδύναμο χαρακτηριστικό τών πεπερασμένων συνδετικών-επιμεριστικών πλεγμάτων είναι ότι είναι βαθμωτά (κάθε δυο μέγιστες αλυσίδες έχουν το ίδιο μήκος), και το μήκος μίας μέγιστης αλυσίδας είναι ίσο με τον αριθμό των τεμνόμενα-ανάγωγων στοιχείων του πλέγματος.[7] Το αντιματροειδές το οποίο αντιπροσωπεύει ένα πεπερασμένο συνδετικό-επιμεριστικό πλέγμα μπορεί να ανακτηθεί από το πλέγμα: τα στοιχεία του αντιματροειδούς μπορούν να παρθούν σαν τεμνώμενα-ανάγωγα στοιχεία του πλέγματος, και το εφικτό σύνολο αντιστοιχεί σε κάθε στοιχείο x του πλέγματος που το οποίο αποτελείται από το σύνολο των τεμνώμενα-ανάγωγων στοιχείων y, όπως y δεν είναι μεγαλύτερο ή ίσο του x στο πλέγμα.
Αυτή η αναπαράσταση του πεπερασμένου συνδετικού-επιμεριστικού πλέγματος προσιτή οικογένεια συνόλων των οποία είναι κλειστά ως προς την ένωση(συνεπάγεται, σαν ένα αντιματροειδές) μπορεί να ειδωθεί ως μία αναλογία του θεωρήματος αναπαράστασης του Birchoff κάτω από το οποίο κάθε πεπερασμένο επιμεριστικό πλέγμα έχει μια αναπαράσταση σαν μια οικογένεια συνόλων κλειστά ως προς την ένωση και την τομή.
Υπερεπιλύσιμα αντιματροειδή
Ωθούμενος από ένα πρόβλημα ορισμού μερικής διάταξης στα στοιχεία μίας ομάδας Coxeter, ο Armstrong (2007) μελέτησε αντιματροειδή τα οποία είναι επίσης υπερεπιλύσιμα πλέγματα. Ένα υπερεπιλύσιμο αντιματροειδές προσδιορίζεται από μία ολικά διατεταγμένη συλλογή από στοιχεία, και μία οικογένεια συνόλων από αυτά τα στοιχεία. Η οικογένεια πρέπει να περιέχει το κενό σύνολο. Επιπρόσθετα, πρέπει να έχει την ιδιότητα ότι αν δύο σύνολα A και B ανήκουν στην οικογένεια, η συνολο-θεωρητική διαφορά B \ A είναι μη κενό, και το x είναι το μικρότερο στοιχείο του B \ A, τότε το A ∪ {x} επίσης ανήκει στην οικογένεια. Όπως παρατήρησε ο Armstrong, κάθε οικογένεια συνόλων διαμορφώνει ένα αντιματροειδές. Ο Armstrong επίσης παρέχει ένα πλέγμα-θεωρητικό χαρακτηρισμό των αντιματροειδών τον οποίο αυτή η δομή μπορεί να δημιουργήσει.
Συνδετική πράξη και κυρτή διάσταση
Αν A και B είναι δύο αντιματροειδή, τα οποία περιγράφονται ως οικογένεια συνόλων, και αν τα μέγιστα σύνολα των A και B είναι ίσα, μπορούμε να σχηματίσουμε ένα άλλο αντιματροειδές, τη σύνδεση των A και B, ως εξής: \( A\vee B = \{ S\cup T \mid S\in A \wedge T\in B \}. \)
Αυτή είναι μια διαφορετική πράξη από τη σύνδεση που θεωρείται στον πλεγματο-θεωρητικό χαρακτηρισμό των αντιματροειδών: συνδυάζει δύο αντιματροειδή για να δημιουργήσει ένα άλλο αντιματροειδές και όχι δύο σύνολα ενός αντιματροειδούς για να δημιουργήσει ένα άλλο σύνολο. Η οικογένεια όλων των αντιματροειδών τα οποία έχουν ένα δοθέν μέγιστο σύνολο δημιουργεί ένα ημιπλέγμα με αυτή τη συνδετική πράξη.
Οι συνδέσεις συσχετίζονται άμεσα με μια απεικόνιση κλειστότητας η οποία απεικονίζει φορμαλιστικές γλώσσες σε αντιματροειδή, όπου η κλειστότητα μιας γλώσσας L είναι η τομή όλων των αντιματροειδών που περιέχουν την L ως υπογλώσσα. Αυτή η κλειστότητα έχει ως τα εφικτά της σύνολα τις ενώσεις των προθεμάτων των συμβολοσειρών της L. Σε όρους αυτής της απεικόνισης κλειστότητας, η σύνδεση είναι η κλειστότητα της ένωσης των γλωσσών A και B.
Κάθε αντιματροειδές μπορεί να αναπαρασταθεί ως η σύνδεση μιας οικογένειας αντιματροειδών αλυσίδες, ή ισοδύναμα ως η κλειστότητα ενός συνόλου βασικών λέξεων: η κυρτή διάσταση ενός αντιματροειδούς A είναι ο ελάχιστος αριθμός των αντιματροειδών αλυσίδες (ή ισοδύναμα ο ελάχιστος αριθμός βασικών λέξεων) σε μια τέτοια αναπαράσταση. Αν F είναι μια οικογένεια αντιματροειδών αλυσίδες των οποίων όλες οι βασικές λέξεις ανήκουν στο A, τότε η F παράγει το A αν και μόνον αν τα εφικτά σύνολα της F περιέχουν όλες τις διαδρομές του A. Οι διαδρομές του Α που ανήκουν σε ένα αντιματροειδές αλυσίδα πρέπει να σχηματίζουν μια αλυσίδα στη διαδρομή μερικώς διατεταγμένων συνόλων του Α, έτσι η κυρτή διάσταση ενός αντιματροειδούς ισούται με τον ελάχιστο αριθμό των αλυσίδων που χρειάζονται για να καλύψουν τη διαδρομή μερικώς διατεταγμένων συνόλων, ο οποίος από το Θεώρημα Dilworth ισούται με το εύρος των διαδρομών μερικώς διατεταγμένων συνόλων.[8]
Αν κάποιος έχει μία αναπαράσταση ενός αντιματροειδούς ως την κλειστότητα ενός συνόλου από d βασικές λέξεις, τότε αυτή η αναπαράσταση μπορεί να χρησιμοποιηθεί για να απεικονίσει τα εφικτά σύνολα του αντιματροειδούς σε έναν d-διάστατο Ευκλείδειο χώρο: ορίζει μια συντεταγμένη για κάθε βασική λέξη w, και ορίζει την τιμή της συντεταγμένης ενός εφικτού συνόλου S να είναι το μήκος του μεγαλύτερου προθέματος της w που είναι υποσύνολο του S. Με αυτή την ενσωμάτωση, το S είναι υποσύνολο του Τ αν και μόνον αν οι συντεταγμένες για το S είναι όλες μικρότερες ή ίσες των αντίστοιχων συντεταγμένων του T. Επομένως, η διάσταση διάταξης της διάταξης ένταξης των εφικτών συνόλων είναι το πολύ ίση με τη κυρτή διάσταση του αντιματροειδούς.[9] Ωστόσο, γενικά αυτές οι δύο διαστάσεις ενδέχεται να διαφέρουν: υπάρχουν αντιματροειδή με διάσταση διάταξης τρία αλλά αυθαίρετα μεγάλη κυρτή διάσταση.
Απαρίθμηση
Ο αριθμός των δυνατών αντιματροειδών πάνω σε ένα σύνολο στοιχείων μεγαλώνει ταχέως όσο αυξάνεται ο αριθμός των στοιχείων του συνόλου. Για σύνολα του ενός, των δύο, τριών, κλπ. στοιχείων, ο αριθμός των διακεκριμένων αντιματροειδών είναι:
1, 3, 22, 485, 59386, 133059751, ...(ακολουθία A119770 στην OESIS)
Εφαρμογές
Οι περιορισμοί προτεραιότητας και χρόνου αποδέσμευσης στον βασικό συμβολισμό για θεωρητικά προβλήματα προγραμματισμού μπορούν να μοντελοποιηθούν από αντιματροειδή. Οι Boyd & Faigle (1990) χρησιμοποιούν αντιματροειδή για να δημιουργήσουν τον άπληστο αλγόριθμο του Eugene Lawler για την βέλτιστη επίλυση προγραμματιστικών προβλημάτων μονού επεξεργαστή με περιορισμούς προτεραιότητας όπου ο στόχος είναι να ελαχιστοποιηθεί η μέγιστη ποινή που επιβάλλεται από τον αργό προγραμματισμό μιας εργασίας.
Οι Glasserman & Yao (1994) χρησιμοποιούν αντιματροειδή για να μοντελοποιήσουν την διάταξη των γεγονότων σε συστήματα διακριτής προσομοίωσης γεγονότων.
Ο Parmar (2003) χρησιμοποιεί αντιματροειδή για να μοντελοποιήσει την πρόοδο ενός στόχου σε προβλήματα σχεδίασης στην τεχνητή νοημοσύνη.
Στη μαθηματική ψυχολογία, τα αντιματροειδή έχουν χρησιμοποιηθεί για να περιγράψουν τις εφικτές καταστάσεις της γνώσης ενός ανθρώπινου όντος. Κάθε στοιχείο του αντιματροειδούς αναπαριστά μία έννοια η οποία είναι να κατανοηθεί από τον μαθητή, ή μια κλάση προβλημάτων την οποία ενδέχεται να μπορεί να λύσει αυτός/αυτή, και τα σύνολα των στοιχείων τα οποία σχηματίζουν το αντιματροειδές αναπαριστούν πιθανά σύνολα εννοιών οι οποίες μπορούν να γίνουν αντιληπτές από έναν άνθρωπο. Τα αξιώματα που ορίζουν ένα αντιματροειδές μπορούν να εκφραστούν ανεπίσημα θέτοντας ότι η εκμάθηση μιας έννοιας δεν εμποδίζει ποτέ τον μαθητή από την εκμάθηση μιας άλλης, και ότι οποιαδήποτε εφικτή κατάσταση γνώσης μπορεί να επιτευχθεί μαθαίνοντας μια έννοια την φορά. Ο στόχος του συστήματος εκτίμησης γνώσης είναι να συμπεράνει το σύνολο των γνωστών εννοιών για έναν μαθητή με το να αναλύει τις αντιδράσεις του/της σε ένα μικρό και καλώς διαλεγμένο σύνολο προβλημάτων. Σε αυτό το πλαίσιο τα α
ντιματροειδή έχουν επίσης ονομαστεί "κενά μάθησης" και "καλώς διαβαθμισμένα κενά γνώσης".[10]
Σημειώσεις
Δύο πρώιμες αναφορές είναι οι Edelman (1980) και Jamison (1980): Ο Jamison ήταν ο πρώτος που χρησιμοποίησε τον όρο "αντιματροειδές". Ο Monjardet (1985) ερευνά την ιστορία της επανακάλυψης των αντιματροειδών.
Korte et al., Θεώρημα 1.4.
O Gordon (1997) περιγράφει αρκετά αποτελέσματα για τα αντιματροειδή αυτού του τύπου, αλλά αυτά τα αντιματροειδή αναφέρθηκαν νωρίτερα π.χ. από τον Korte et al. Ο Chandran et al. (2003) χρησιμοποιεί τη σύνδεση με τα αντιματροειδή ως ένα μέρος ενός αλγορίθμου για την αποτελεσματική λιστοποίηση όλων των διατάξεων τέλειας απόρριψης ενός χορδικού γραφήματος.
Korte et al., Θεώρημα 1.1.
Adaricheva, Gorbunov & Tumanov (2003), Theorems 1.7 and 1.9; Armstrong (2007), Theorem 2.7.
Edelman (1980), Theorem 3.3; Armstrong (2007), Theorem 2.8.
Ο Monjardet (1985) αποδίδει την διπλή μορφή αυτού του χαρακτηρισμού σε διάφορες εργασίες του S. P. Avann από την δεκαετία του '60 .
Edelman & Saks (1988); Korte et al., Θεώρημα 6.9.
Korte et al., Πόρισμα 6.10.
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 (2007), The sorting order on a Coxeter group.
Birkhoff, Garrett; Bennett, M. K. (1985), «The convexity lattice of a poset», Order 2 (3): 223–242, doi:10.1007/BF00333128.
Björner, Anders; Ziegler, Günter M. (1992), «8 Introduction to greedoids», στο: White, Neil, Matroid Applications, Encyclopedia of Mathematics and its Applications, 40, Cambridge: Cambridge University Press, σελ. 284–357, doi:10.1017/CBO9780511662041.009, ISBN 0-521-38165-7
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.
Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003), «Generating and characterizing the perfect elimination orderings of a chordal graph», 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.
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.
Edelman, Paul H.; Saks, Michael E. (1988), «Combinatorial representation and convex dimension of convex geometries», Order 5 (1): 23–32, doi:10.1007/BF00143895.
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.
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, 29, σελ. 535–544.
Korte, Bernhard; Lovász, László; Schrader, Rainer (1991), Greedoids, Springer-Verlag, σελ. 19–43, ISBN 3-540-18190-3.
Monjardet, Bernard (1985), «A use for frequently rediscovering a concept», Order 1 (4): 415–417, doi:10.1007/BF00582748.
Parmar, Aarati (2003), «Some Mathematical Structures Underlying Efficient Planning», AAAI Spring Symposium on Logical Formalization of Commonsense Reasoning.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
