Антиматроид

Математическая система упорядочений или множеств

Три представления антиматроида: включение порядка в его семейство допустимых множеств, формальный язык и соответствующий путь частично упорядоченного множества.

В математике антиматроид — это формальная система , описывающая процессы, в которых множество создается путем включения элементов по одному за раз, и в которых элемент, однажды доступный для включения, остается доступным до тех пор, пока он не будет включен. ^[1] Антиматроиды обычно аксиоматизируются двумя эквивалентными способами : либо как система множеств, моделирующая возможные состояния такого процесса, либо как формальный язык, моделирующий различные последовательности, в которые могут быть включены элементы. Дилворт (1940) был первым, кто изучал антиматроиды, используя еще одну аксиоматизацию, основанную на теории решеток , и они часто открывались заново в других контекстах. ^[2]

Аксиомы, определяющие антиматроиды как системы множеств, очень похожи на аксиомы матроидов , но в то время как матроиды определяются аксиомой обмена , антиматроиды определяются аксиомой антиобмена , от которой и происходит их название. Антиматроиды можно рассматривать как частный случай гридоидов и полумодулярных решеток , а также как обобщение частичных порядков и дистрибутивных решеток . Антиматроиды эквивалентны, по дополнению , выпуклым геометриям , комбинаторной абстракции выпуклых множеств в геометрии .

Антиматроиды применялись для моделирования ограничений предшествования в задачах планирования , потенциальных последовательностей событий в симуляциях, планирования задач в искусственном интеллекте и состояний знаний обучающихся людей.

Определения

Антиматроид можно определить как конечное семейство конечных множеств, называемых допустимыми множествами , со следующими двумя свойствами: ^[3] ${\displaystyle {\mathcal {F}}}$

• Объединение любых двух допустимых множеств также допустимо, то есть замкнуто относительно объединений . ${\displaystyle {\mathcal {F}}}$
• Если — непустое допустимое множество, то содержит элемент , для которого (множество, образованное удалением из ), также допустимо. То есть — доступная система множеств . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S\setminus \{x\}}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {F}}}$

Антиматроиды также имеют эквивалентное определение как формальный язык , то есть как набор строк , определенных из конечного алфавита символов . Строка, принадлежащая этому набору, называется словом языка. Язык, определяющий антиматроид, должен удовлетворять следующим свойствам: ^[4] ${\displaystyle {\mathcal {L}}}$

• Каждый символ алфавита встречается как минимум в одном слове . ${\displaystyle {\mathcal {L}}}$
• Каждое слово содержит не более одной копии каждого символа. Язык с таким свойством называется нормальным . ^[5] ${\displaystyle {\mathcal {L}}}$
• Каждый префикс слова в также есть в . Язык с этим свойством называется наследственным . ^[5] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$
• Если и являются словами из , и содержат хотя бы один символ, которого нет в , то существует символ из , такой что конкатенация является другим словом из . ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle Tx}$ ${\displaystyle {\mathcal {L}}}$

Эквивалентность этих двух форм определения можно увидеть следующим образом. Если — антиматроид, определенный как формальный язык, то наборы символов в словах образуют доступную систему множеств, замкнутую на объединение. Она доступна по наследственному свойству строк, и можно показать, что она замкнута на объединение повторным применением свойства конкатенации строк. В другом направлении, от доступной системы множеств, замкнутой на объединение , язык нормальных строк, все префиксы которого имеют наборы символов, принадлежащие , удовлетворяет требованиям, чтобы формальный язык был антиматроидом. Эти два преобразования являются обратными друг другу: преобразование формального языка в семейство множеств и обратно или наоборот производит одну и ту же систему. Таким образом, эти два определения приводят к математически эквивалентным классам объектов. ^[6] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

Примеры

Последовательность оболочек плоского набора точек. Отрезки линий показывают края выпуклых оболочек после удаления некоторых точек.

Примерами антиматроидов являются следующие системы:

Цепные антиматроиды

Префиксы одной строки и наборы символов в этих префиксах образуют антиматроид. Например, цепной антиматроид, определяемый строкой, имеет в качестве своего формального языка набор строк (где обозначает пустую строку ), а в качестве своего семейства допустимых множеств — семейство ^[7] ${\displaystyle abcd}$ $${\displaystyle \{\varepsilon ,a,ab,abc,abcd\}}$$ ${\displaystyle \varepsilon }$ $${\displaystyle {\bigl \{}\emptyset ,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}{\bigr \}}.}$$

Посет антиматроиды

Нижние множества конечного частично упорядоченного множества образуют антиматроид, при этом полные слова антиматроида образуют линейные расширения частичного порядка. ^[8] По теореме Биркгофа о представлении для дистрибутивных решеток допустимые множества в антиматроиде частично упорядоченного множества (упорядоченном по включению множеств) образуют дистрибутивную решетку, и все дистрибутивные решетки могут быть образованы таким образом. Таким образом, антиматроиды можно рассматривать как обобщения дистрибутивных решеток. Цепной антиматроид является частным случаем антиматроида частично упорядоченного множества для полного порядка . ^[7]

Обстрел антиматроидов

Последовательность оболочек конечного множества точек на евклидовой плоскости или многомерном евклидовом пространстве формируется путем многократного удаления вершин выпуклой оболочки . Допустимые множества антиматроида, образованные этими последовательностями, являются пересечениями с дополнением выпуклого множества . [ ^7] ${\displaystyle U}$ ${\displaystyle U}$

Идеальное устранение

Совершенный порядок исключения хордового графа — это упорядочение его вершин, при котором для каждой вершины соседи той, которая встречается позже, чем в упорядочении, образуют клику . Префиксы совершенных порядков исключения хордового графа образуют антиматроид. ^[9] ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$

Игры с запуском чипов

Игры со стрельбой фишками, такие как модель абелевой песочной кучи, определяются направленным графом вместе с системой «фишек», размещенных на его вершинах. Всякий раз, когда количество фишек на вершине по крайней мере так же велико, как количество ребер из , можно стрелять , перемещая одну фишку в каждую соседнюю вершину. Событие, которое срабатывает в th-й раз, может произойти только в том случае, если оно уже срабатывало раз и накопило общее количество фишек. Эти условия не зависят от порядка предыдущих срабатываний и остаются верными до тех пор, пока не сработает, поэтому любой заданный граф и начальное размещение фишек, для которых система завершается, определяют антиматроид на парах . Следствием свойства антиматроида этих систем является то, что для заданного начального состояния количество срабатываний каждой вершины и конечное устойчивое состояние системы не зависят от порядка срабатывания. ^[10] ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle i\cdot \deg(v)}$ ${\displaystyle v}$ ${\displaystyle (v,i)}$

Пути и основные слова

В теоретико-множественной аксиоматизации антиматроида существуют определенные специальные множества, называемые путями , которые определяют весь антиматроид, в том смысле, что множества антиматроида являются в точности объединениями путей. ^[11] Если — любое допустимое множество антиматроида, элемент , который можно удалить из , чтобы сформировать другое допустимое множество, называется конечной точкой , а допустимое множество, имеющее только одну конечную точку, называется путем антиматроида. ^[12] Семейство путей может быть частично упорядочено включением множеств, образуя частично упорядоченный набор путей антиматроида. ^[13] ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$

Для каждого допустимого множества в антиматроиде и каждого элемента из можно найти подмножество путей из , для которого является конечной точкой: чтобы сделать это, удаляйте по одному элементу за раз, кроме , пока ни одно такое удаление не оставит допустимого подмножества. Следовательно, каждое допустимое множество в антиматроиде является объединением своих подмножеств путей. ^[11] Если не является путем, каждое подмножество в этом объединении является собственным подмножеством . Но если само является путем с конечной точкой , каждое собственное подмножество , принадлежащее антиматроиду, исключает . Следовательно, пути антиматроида — это в точности возможные множества, которые не равны объединениям своих собственных возможных подмножеств. Эквивалентно, заданное семейство множеств образует семейство путей антиматроида тогда и только тогда, когда для каждого в объединение подмножеств из в имеет на один элемент меньше, чем оно само. ^[14] Если так, то само является семейством объединений подмножеств из . ^[11] ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {P}}}$

В формальной языковой формализации антиматроида самые длинные строки называются базовыми словами . Каждое базовое слово образует перестановку всего алфавита. ^[15] Если — набор базовых слов, то можно определить из как набор префиксов слов в . ^[16] ${\displaystyle B}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle B}$ ${\displaystyle B}$

Выпуклые геометрии

Если — это система множеств, определяющая антиматроид, с равным объединению множеств в , то семейство множеств, дополнительных к множествам в , иногда называют выпуклой геометрией , а множества в называются выпуклыми множествами . Например, в антиматроиде шеллинга выпуклые множества являются пересечениями заданного множества точек с выпуклыми подмножествами евклидова пространства. Система множеств, определяющая выпуклую геометрию, должна быть замкнута относительно пересечений. Для любого множества в , которое не равно , должен быть элемент, не в , к которому можно прибавить , чтобы сформировать другое множество в . ^[17] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle U}$ ${\displaystyle {\mathcal {F}}}$ $${\displaystyle {\mathcal {G}}=\{U\setminus S\mid S\in {\mathcal {F}}\}}$$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle U}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {G}}}$

Выпуклая геометрия может быть также определена в терминах оператора замыкания , который отображает любое подмножество в его минимальное замкнутое супермножество. Чтобы быть оператором замыкания, должен иметь следующие свойства: ^[18] ${\displaystyle \tau }$ ${\displaystyle U}$ ${\displaystyle \tau }$

• ${\displaystyle \tau (\emptyset )=\emptyset }$: замыкание пустого множества пусто.
• Для каждого подмножества , есть подмножество и . ${\displaystyle S}$ ${\displaystyle U}$ ${\displaystyle S}$ ${\displaystyle \tau (S)}$ ${\displaystyle \tau (S)=\tau {\bigl (}\tau (S){\bigr )}}$
• Всякий раз , когда , является подмножеством . ${\displaystyle S\subset T\subset U}$ ${\displaystyle \tau (S)}$ ${\displaystyle \tau (T)}$

Семейство замкнутых множеств, полученное в результате операции замыкания этого типа, обязательно замкнуто относительно пересечений, но может не быть выпуклой геометрией. Операторы замыкания, определяющие выпуклые геометрии, также удовлетворяют дополнительной аксиоме антиобмена :

• Если является подмножеством , а и являются различными элементами , которые не принадлежат , но принадлежат , то не принадлежит . ^[18] ${\displaystyle S}$ ${\displaystyle U}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle U}$ ${\displaystyle \tau (S)}$ ${\displaystyle z}$ ${\displaystyle \tau (S\cup \{y\})}$ ${\displaystyle y}$ ${\displaystyle \tau (S\cup \{z\})}$

Операция замыкания, удовлетворяющая этой аксиоме, называется замыканием антиобмена . Если — замкнутое множество в замыкании антиобмена, то аксиома антиобмена определяет частичный порядок на элементах, не принадлежащих , где в частичном порядке, когда принадлежит . Если — минимальный элемент этого частичного порядка, то замкнуто. То есть семейство замкнутых множеств замыкания антиобмена обладает тем свойством, что для любого множества, отличного от универсального множества, существует элемент , который может быть добавлен к нему для получения другого замкнутого множества. Это свойство является дополнительным к свойству доступности антиматроидов, а тот факт, что пересечения замкнутых множеств являются замкнутыми, является дополнительным к свойству, что объединения допустимых множеств в антиматроиде являются допустимыми. Следовательно, дополнения замкнутых множеств любого замыкания антиобмена образуют антиматроид. ^[17] ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x\leq y}$ ${\displaystyle x}$ ${\displaystyle \tau (S\cup \{y\})}$ ${\displaystyle x}$ ${\displaystyle S\cup \{x\}}$ ${\displaystyle x}$

Неориентированные графы, в которых выпуклые множества (подмножества вершин, содержащие все кратчайшие пути между вершинами в подмножестве) образуют выпуклую геометрию, являются в точности птолемеевыми графами . ^[19]

Решетки с присоединением и дистрибутивностью

Каждые два допустимых множества антиматроида имеют уникальную наименьшую верхнюю границу (их объединение) и уникальную наибольшую нижнюю границу (объединение множеств в антиматроиде, которые содержатся в них обоих). Таким образом, допустимые множества антиматроида, частично упорядоченные включением множеств, образуют решетку . Различные важные особенности антиматроида можно интерпретировать в терминах теории решеток; например, пути антиматроида являются неприводимыми относительно соединения элементами соответствующей решетки, а основные слова антиматроида соответствуют максимальным цепям в решетке. Решетки, которые возникают из антиматроидов таким образом, обобщают конечные дистрибутивные решетки и могут быть охарактеризованы несколькими различными способами.

• Описание, первоначально рассмотренное Дилвортом (1940), касается meet-неприводимых элементов решетки. Для каждого элемента антиматроида существует единственное максимальное допустимое множество , которое не содержит : может быть построено как объединение всех допустимых множеств, не содержащих . Это множество автоматически является meet-неприводимым, что означает, что оно не является пересечением любых двух больших элементов решетки. Это верно, потому что каждое допустимое надмножество содержит , и то же самое, следовательно, также верно для каждого пересечения допустимых надмножеств. Каждый элемент произвольной решетки может быть разложен как meet meet-неприводимых множеств, часто несколькими способами, но в решетке, соответствующей антиматроиду, каждый элемент имеет уникальное минимальное семейство meet-неприводимых множеств, meet которых равен ; это семейство состоит из множеств для элементов, таких что является допустимым. То есть решетка имеет уникальные meet-неприводимые разложения . ${\displaystyle x}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle S_{x}}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle T\cup \{x\}}$
• Вторая характеристика касается интервалов в решетке, подрешеток, определяемых парой элементов решетки, состоящих из всех элементов решетки с . Интервал является атомистическим, если каждый элемент в нем является объединением атомов (минимальных элементов выше нижнего элемента ), и он является булевым, если он изоморфен решетке всех подмножеств конечного множества. Для антиматроида каждый интервал, который является атомистическим, также является булевым. ${\displaystyle x\leq y}$ ${\displaystyle z}$ ${\displaystyle x\leq z\leq y}$ ${\displaystyle x}$
• В-третьих, решетки, возникающие из антиматроидов, являются полумодулярными решетками , решетками, которые удовлетворяют верхнему полумодулярному закону, что для любых двух элементов и , если покрывает , то покрывает . Переводя это условие в допустимые множества антиматроида, если допустимое множество имеет только один элемент, не принадлежащий другому допустимому множеству , то этот один элемент может быть добавлен к , чтобы сформировать другое множество в антиматроиде. Кроме того, решетка антиматроида обладает свойством meet-semidistributive : для всех элементов решетки , , и , если и равны друг другу, то они также оба равны . Полумодулярная и meet-semidistributive решетка называется join-distributive решеткой . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x\wedge y}$ ${\displaystyle x\vee y}$ ${\displaystyle x}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x\wedge y}$ ${\displaystyle x\wedge z}$ ${\displaystyle x\wedge (y\vee z)}$

Эти три характеристики эквивалентны: любая решетка с уникальными meet-неприводимыми разложениями имеет булевы атомистические интервалы и является join-дистрибутивной, любая решетка с булевыми атомистическими интервалами имеет уникальные meet-неприводимые разложения и является join-дистрибутивной, и любая join-дистрибутивная решетка имеет уникальные meet-неприводимые разложения и булевы атомистические интервалы. ^[20] Таким образом, мы можем назвать решетку с любым из этих трех свойств join-дистрибутивной. Любой антиматроид порождает конечную join-дистрибутивную решетку, и любая конечная join-дистрибутивная решетка происходит из антиматроида таким образом. ^[21] Другая эквивалентная характеристика конечных join-дистрибутивных решеток заключается в том, что они градуированы (любые две максимальные цепи имеют одинаковую длину), а длина максимальной цепи равна количеству meet-неприводимых элементов решетки. ^[22] Антиматроид, представляющий конечную решетку с дистрибутивным соединением, может быть восстановлен из решетки: элементы антиматроида могут быть взяты в качестве неприводимых к пересечению элементов решетки, а допустимое множество, соответствующее любому элементу решетки, состоит из множества неприводимых к пересечению элементов, таких, что не больше или равно в решетке. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$

Это представление любой конечной джойн-дистрибутивной решетки как доступного семейства множеств, замкнутых относительно объединений (то есть как антиматроида), можно рассматривать как аналог теоремы Биркгофа о представлении , согласно которой любая конечная дистрибутивная решетка имеет представление как семейство множеств, замкнутых относительно объединений и пересечений.

Сверхразрешимые антиматроиды

Мотивированный проблемой определения частичных порядков на элементах группы Коксетера , Армстронг (2009) изучал антиматроиды, которые также являются сверхразрешимыми решетками . Сверхразрешимый антиматроид определяется полностью упорядоченным набором элементов и семейством множеств этих элементов. Семейство должно включать пустое множество. Кроме того, оно должно обладать свойством, что если два множества и принадлежат семейству, если теоретико-множественная разность непуста, и если — наименьший элемент , то также принадлежит семейству. Как замечает Армстронг, любое семейство множеств этого типа образует антиматроид. Армстронг также дает теоретико-решеточную характеристику антиматроидов, которые может образовать эта конструкция. ^[23] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B\setminus A}$ ${\displaystyle x}$ ${\displaystyle B\setminus A}$ ${\displaystyle A\cup \{x\}}$

Операция соединения и выпуклое измерение

Если и являются двумя антиматроидами, оба описанными как семейство множеств над одной и той же вселенной элементов, то другой антиматроид, соединение и , может быть сформирован следующим образом: Это другая операция, чем соединение , рассматриваемое в решеточно-теоретических характеристиках антиматроидов: она объединяет два антиматроида, чтобы сформировать другой антиматроид, а не объединяет два множества в антиматроиде, чтобы сформировать другой набор. Семейство всех антиматроидов над одной и той же вселенной образует полурешетку с этой операцией соединения. ^[24] ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ $${\displaystyle {\mathcal {A}}\vee {\mathcal {B}}=\{S\cup T\mid S\in {\mathcal {A}}\wedge T\in {\mathcal {B}}\}.}$$

Объединения тесно связаны с операцией замыкания, которая отображает формальные языки в антиматроиды, где замыкание языка является пересечением всех антиматроидов, содержащих в качестве подъязыка. Это замыкание имеет в качестве своих допустимых множеств объединения префиксов строк в . В терминах этой операции замыкания объединение является замыканием объединения языков и . Каждый антиматроид может быть представлен как объединение семейства цепных антиматроидов или, что эквивалентно, как замыкание множества основных слов; выпуклая размерность антиматроида является минимальным числом цепных антиматроидов (или, что эквивалентно, минимальным числом основных слов) в таком представлении. Если — семейство цепных антиматроидов, все основные слова которого принадлежат , то генерирует тогда и только тогда, когда допустимые множества включают все пути . Пути, принадлежащие одному цепочечному антиматроиду, должны образовывать цепь в частично упорядоченном множестве путей , поэтому выпуклая размерность антиматроида равна минимальному числу цепей, необходимых для покрытия частично упорядоченного множества путей, которое по теореме Дилворта равно ширине частично упорядоченного множества путей. ^[25] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathfrak {F}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathfrak {F}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathfrak {F}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$

Если имеется представление антиматроида как замыкания множества базовых слов, то это представление можно использовать для отображения допустимых множеств антиматроида в точки в -мерном евклидовом пространстве: назначить одну координату на базовое слово и сделать значение координат допустимого множества равным длине самого длинного префикса , который является подмножеством . При таком вложении является подмножеством другого допустимого множества тогда и только тогда, когда координаты для все меньше или равны соответствующим координатам . Следовательно, размерность порядка включения упорядочения допустимых множеств не превышает выпуклой размерности антиматроида. ^[26] Однако в общем случае эти два измерения могут сильно различаться: существуют антиматроиды с размерностью порядка три, но с произвольно большой выпуклой размерностью. ^[27] ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle W}$ ${\displaystyle S}$ ${\displaystyle W}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$

Перечисление

Число возможных антиматроидов на множестве элементов быстро растет с числом элементов в множестве. Для множеств из одного, двух, трех и т. д. элементов число различных антиматроидов равно ^[28] $${\displaystyle 1,3,22,485,59386,133059751,\dots \,.}$$

Приложения

Как ограничения по времени предшествования, так и ограничения по времени освобождения в стандартной нотации для теоретических задач планирования могут быть смоделированы антиматроидами. Бойд и Фейгл (1990) используют антиматроиды для обобщения жадного алгоритма Юджина Лоулера для оптимального решения задач планирования с одним процессором с ограничениями по предшествованию, в которых цель состоит в минимизации максимального штрафа, вызванного поздним планированием задачи.

Глассерман и Яо (1994) используют антиматроиды для моделирования порядка событий в системах моделирования дискретных событий .

Пармар (2003) использует антиматроиды для моделирования прогресса в достижении цели в задачах планирования искусственного интеллекта .

В теории оптимальности , математической модели развития естественного языка , основанной на оптимизации при ограничениях, грамматики логически эквивалентны антиматроидам. ^[29]

В математической психологии антиматроиды использовались для описания возможных состояний знаний обучающегося человека. Каждый элемент антиматроида представляет собой концепцию, которую должен понять обучающийся, или класс задач, которые он или она могли бы решить правильно, а наборы элементов, которые образуют антиматроид, представляют собой возможные наборы концепций, которые мог бы понять один человек. Аксиомы, определяющие антиматроид, можно неформально сформулировать так: изучение одной концепции никогда не может помешать обучающемуся изучить другую концепцию, и что любое возможное состояние знаний может быть достигнуто путем изучения одной концепции за раз. Задача системы оценки знаний состоит в том, чтобы вывести набор концепций, известных данному обучающемуся, путем анализа его или ее ответов на небольшой и хорошо подобранный набор задач. В этом контексте антиматроиды также называются «пространствами обучения» и «пространствами хорошо оцененных знаний». ^[30]

Примечания

1. См. Korte, Lovász & Schrader (1991) для всестороннего обзора теории антиматроидов со множеством дополнительных ссылок.
2. Две ранние ссылки — Эдельман (1980) и Джеймисон (1980); Джеймисон был первым, кто использовал термин «антиматроид». Монжарде (1985) рассматривает историю повторного открытия антиматроидов.
3. См., например, Kempner & Levit (2003), Определение 2.1 и Предложение 2.3, стр. 2.
4. Корте, Ловас и Шрадер (1991), стр. 22.
5. Korte, Lovász & Schrader (1991), стр. 5.
6. Корте, Ловаш и Шрадер (1991), теорема 1.4, с. 24.
7. Гордон (1997).
8. Корте, Ловаш и Шрадер (1991), стр. 24–25.
9. Гордон (1997) описывает несколько результатов, связанных с антиматроидами этого типа, но эти антиматроиды упоминались ранее, например, Корте, Ловасом и Шрадером (1991). Чандра и др. (2003) используют связь с антиматроидами как часть алгоритма для эффективного перечисления всех совершенных упорядочений исключения заданного хордового графа.
10. Бьёрнер, Ловас и Шор (1991); Кнауэр (2009).
11. Korte, Lovász & Schrader (1991), Лемма 3.12, с. 31.
12. Корте, Ловас и Шрадер (1991), стр. 31.
13. Корте, Ловас и Шрадер (1991), стр. 39–43.
14. См. Korte, Lovász & Schrader (1991), теорема 3.13, стр. 32, где пути определяются как корневые множества , множества с выделенным элементом, и приводится эквивалентная характеристика семейств корневых множеств, которые образуют пути антиматроидов.
15. Корте, Ловас и Шрадер (1991), стр. 6, 22.
16. См. Korte, Lovász & Schrader (1991), стр. 22: «любое слово в антиматроиде может быть расширено до базового слова».
17. Korte, Lovász & Schrader (1991), теорема 1.1, с. 21.
18. Korte, Lovász & Schrader (1991), стр. 20.
19. Фарбер и Джеймисон (1986).
20. Адаричева, Горбунов и Туманов (2003), Теоремы 1.7 и 1.9; Армстронг (2009), Теорема 2.7.
21. Эдельман (1980), Теорема 3.3; Армстронг (2009), Теорема 2.8.
22. Монжарде (1985) приписывает двойную форму этой характеристики нескольким работам С. П. Аванна 1960-х годов.
23. Армстронг (2009).
24. Корте, Ловас и Шрадер (1991), стр. 42; Эппштейн (2008), раздел 7.2; Фальмань и др. (2013), раздел 14.4.
25. Эдельман и Сакс (1988); Корте, Ловас и Шрадер (1991), Теорема 6.9.
26. Корте, Ловаш и Шредер (1991), следствие 6.10.
27. Эппштейн (2008), Рисунок 15.
28. Слоан, Н. Дж. А. (ред.), «Последовательность A119770», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
29. Мерчант и Риггл (2016).
30. Дуаньон и Фальмань (1999).

Ссылки

• Адаричева, КВ; Горбунов, ВА; Туманов, ВИ (2003), "Join-полудистрибутивные решетки и выпуклые геометрии", Успехи математики , 173 (1): 1–49, doi : 10.1016/S0001-8708(02)00011-7.
• Армстронг, Дрю (2009), «Порядок сортировки в группе Коксетера», Журнал комбинаторной теории , Серия A, 116 (8): 1285–1305, arXiv : 0712.1047 , doi : 10.1016/j.jcta.2009.03.009 , MR  2568800, S2CID  15474840.
• Биркгофф, Гарретт ; Беннетт, MK (1985), «Решетка выпуклости частично упорядоченного множества», Order , 2 (3): 223–242, doi :10.1007/BF00333128, S2CID  118907732
• Бьорнер, Андерс ; Ловас, Ласло ; Шор, Питер В. (1991), «Игры с запуском чипов на графах», European Journal of Combinatorics , 12 (4): 283–291, doi : 10.1016/S0195-6698(13)80111-4, MR  1120415
• Бьёрнер, Андерс ; Циглер, Гюнтер М. (1992), «Введение в гридоиды», в Уайт, Нил (ред.), Приложения матроидов , Энциклопедия математики и ее приложений, т. 40, Кембридж: Cambridge University Press, стр. 284–357, doi : 10.1017/CBO9780511662041.009, ISBN 0-521-38165-7, МР  1165537
• Бойд, Э. Эндрю; Фейгл, Ульрих (1990), «Алгоритмическая характеристика антиматроидов», Дискретная прикладная математика , 28 (3): 197–205, doi : 10.1016/0166-218X(90)90002-T, hdl : 1911/101636.
• Чандран, Л.С.; Ибарра, Л.; Раскей, Ф .; Савада, Дж. (2003), «Создание и характеристика совершенных упорядочений исключения хордового графа» (PDF) , Теоретическая информатика , 307 (2): 303–317, doi :10.1016/S0304-3975(03)00221-4
• Дилворт, Роберт П. (1940), «Решетки с уникальными неприводимыми разложениями», Annals of Mathematics , 41 (4): 771–777, doi :10.2307/1968857, JSTOR  1968857.
• Дуаньон, Жан-Поль; Фальмань, Жан-Клод (1999), Knowledge Spaces , Springer-Verlag, ISBN 3-540-64501-2.
• Эдельман, Пол Х. (1980), «Meet-distributive sets and the anti-exchange closure», Algebra Universalis , 10 (1): 290–299, doi :10.1007/BF02482912, S2CID  120403229.
• Эдельман, Пол Х.; Сакс, Майкл Э. (1988), «Комбинаторное представление и выпуклая размерность выпуклых геометрий», Order , 5 (1): 23–32, doi :10.1007/BF00143895, S2CID  119826035.
• Эппштейн, Дэвид (2008), Изучение последовательностей , arXiv : 0803.4030. Частично адаптировано как главы 13 и 14 из Falmagne, Jean-Claude ; Albert, Dietrich ; Doble, Chris ; Eppstein, David ; Hu, Xiangen, ред. (2013), Knowledge Spaces: Applications in Education , Springer-Verlag, doi :10.1007/978-3-642-35329-1, ISBN 978-3-642-35328-4.
• Фарбер, Мартин; Джеймисон, Роберт Э. (1986), «Выпуклость в графах и гиперграфах», Журнал SIAM по алгебраическим и дискретным методам , 7 (3): 433–444, doi : 10.1137/0607049, hdl : 10338.dmlcz/127659, MR  0844046.
• Глассерман, Пол; Яо, Дэвид Д. (1994), Монотонная структура в дискретных системах событий , Wiley Series in Probability and Statistics, Wiley Interscience, ISBN 978-0-471-58041-6.
• Гордон, Гэри (1997), «β-инвариант для гридоидов и антиматроидов», Electronic Journal of Combinatorics , 4 (1): Research Paper 13, doi : 10.37236/1298 , MR  1445628.
• Джеймисон, Роберт (1980), «Copoints in antimatroids», Труды Одиннадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Флоридский атлантический университет, Бока-Ратон, Флорида, 1980), т. II , Congressus Numerantium, т. 29, стр. 535–544, MR  0608454.
• Кемпнер, Юлия; Левит, Вадим Э. (2003), "Соответствие между двумя антиматроидными алгоритмическими характеристиками", Electronic Journal of Combinatorics , 10 : Research Paper 44, arXiv : math/0307013 , Bibcode : 2003math......7013K, doi : 10.37236/1737, MR  2014531, S2CID  11015967
• Кнауэр, Коля (2009), «Chip-firing, antimatroids, and polyhedras», Европейская конференция по комбинаторике, теории графов и приложениям (EuroComb 2009) , Электронные заметки по дискретной математике, т. 34, стр. 9–13, doi :10.1016/j.endm.2009.07.002, MR  2591410
• Корте, Бернхард ; Ловас, Ласло ; Шредер, Райнер (1991), «Глава III: Абстрактная выпуклость – антиматроиды», Greedoids , Springer-Verlag, стр. 19–43, doi : 10.1007/978-3-642-58191-5_3, ISBN 3-540-18190-3.
• Мерчант, Назарре; Риггл, Джейсон (2016), «Грамматики ОТ, за пределами частичных порядков: множества ERC и антиматроиды», Natural Language & Linguistic Theory , 34 : 241–269, doi :10.1007/s11049-015-9297-5, S2CID  170567540.
• Монжарде, Бернар (1985), «Использование для частого повторного открытия концепции», Заказ , 1 (4): 415–417, doi :10.1007/BF00582748, S2CID  119378521.
• Пармар, Аарати (2003), «Некоторые математические структуры, лежащие в основе эффективного планирования», Весенний симпозиум AAAI по логической формализации здравого смысла (PDF).