В математике , antimatroid является формальной системой , которая описывает процессы , в которых множество застроено , включая элементы по одному, и в котором элемент, один раз для включения, по- прежнему доступен , пока не будет включен. Антиматроиды обычно аксиоматизируются двумя эквивалентными способами : либо как система множеств, моделирующая возможные состояния такого процесса, либо как формальный язык, моделирующий различные последовательности, в которые могут быть включены элементы. Дилворт (1940) был первым, кто изучил антиматроидов, используя еще одну аксиоматизацию, основанную на теории решетки., и они часто открывались заново в других контекстах; [1] см. Korte, Lovász & Schrader (1991) для всестороннего обзора теории антиматроидов со многими дополнительными ссылками.
Аксиомы, определяющие антиматроидов как системы множеств, очень похожи на аксиомы матроидов , но в то время как матроиды определяются аксиомой обмена (например, базисным обменом или аксиомами независимого обмена множеством ), антиматроиды вместо этого определяются аксиомой антиобмена , начиная с откуда и произошло их название. Антиматроиды можно рассматривать как частный случай гридоидов и полумодулярных решеток , а также как обобщение частичных порядков и дистрибутивных решеток . Antimatroids эквивалентны, по комплементации , чтобы выпуклые геометрии , комбинаторная абстракция выпуклых множеств в геометрии .
Антиматроиды применялись для моделирования ограничений приоритета в задачах планирования , потенциальных последовательностей событий в симуляциях, планирования задач в искусственном интеллекте и состояний знаний учащихся-людей.
Определения
Антиматроид можно определить как конечное семейство наборов, называемых допустимыми наборами , со следующими двумя свойствами: [2]
- Также возможно объединение любых двух допустимых множеств. Это,будет закрыто под союзами.
- Если непустое допустимое множество, то содержит элемент для которого (множество, образованное удалением из ) также возможно. Это,является доступным набор системы .
Антиматроиды также имеют эквивалентное определение как формальный язык , то есть как набор строк, определенных из конечного алфавита символов . Строка, принадлежащая этому набору, называется словом языка. Языкопределение антиматроида должно удовлетворять следующим свойствам: [3]
- Каждый символ алфавита встречается хотя бы в одном слове .
- Каждое слово содержит не более одной копии каждого символа. Язык с этим свойством называется нормальным . [4]
- Каждый префикс слова в также в . Язык с этим свойством называется наследственным . [4]
- Если а также слова в , а также содержит хотя бы один символ, которого нет в , то есть символ в так что конкатенация другое слово в .
Эквивалентность этих двух форм определения можно увидеть следующим образом. Если является антиматроидом, определенным как формальный язык, то наборы символов в словах образуют доступную систему замкнутых множеств. Он доступен благодаря наследственному свойству строк, и можно показать, что он закрывается по объединению путем повторного применения свойства конкатенации строк. В обратном направлении, еслиявляется доступной системой замкнутых множеств, элементы которых можно интерпретировать как символы в алфавите. Для этого алфавита можно определить язык состоящий из всех строк которые имеют не более одной копии каждого символа и подчиняются свойству, что каждый префикс имеет набор символов, принадлежащих . Этот язык автоматически подчиняется всем свойствам формального языка, которые требуются для антиматроидов. Эти два преобразования противоположны друг другу: преобразование формального языка в заданное семейство и обратно, или наоборот, дает одну и ту же систему. Таким образом, эти два определения приводят к математически эквивалентным классам объектов. [5]
Примеры
- Цепь antimatroid имеет в качестве официального языка префиксы одной строки, и как ее допустимых множеств множества символов в этих префиксов. Например, цепной антиматроид, определяемый строкой имеет в качестве формального языка набор строк (где обозначает пустую строку ), а в качестве ее семейства допустимых множеств семейство [6]
- Ч.у.м. antimatroid имеет в качестве своих возможных устанавливает нижние наборы из конечного частично упорядоченного множества . По теореме Биркгофа о представлении для дистрибутивных решеток допустимые множества в антиматроиде poset (упорядоченные по включению множеств) образуют дистрибутивную решетку, и любая дистрибутивная решетка может быть сформирована таким образом. Таким образом, антиматроиды можно рассматривать как обобщения распределительных решеток. Цепной антиматроид - это частный случай антиматроида poset для полного порядка . [6]
- Последовательность обстрелов конечного множестваточек на евклидовой плоскости или в многомерном евклидовом пространстве - это такой порядок точек, что для каждой точкисуществует линия (в евклидовой плоскости или гиперплоскость в евклидовом пространстве), разделяющаясо всех последующих точек в последовательности. Эквивалентно,должен быть вершиной его выпуклой оболочки и всех последующих точек. Последовательности частичного обстрела набора точек образуют антиматроид, называемый обстреливающим антиматроидом . Посильную наборы Обстрел antimatroid являются пересечениями изс дополнением к выпуклому множеству. [6] Каждый антиматроид изоморфен антиматроиду-оболочке из точек в достаточно многомерном пространстве. [7]
- Идеальный порядок ликвидации из хорд графы является упорядочением его вершин, что для каждой вершины, соседи которые происходят позже, чем при заказе формируйте клику . Префиксы порядков идеального исключения хордального графа образуют антиматроид. [8]
Пути и основные слова
В теоретико-множественной аксиоматизации антиматроида есть определенные специальные множества, называемые путями, которые определяют весь антиматроид в том смысле, что множества антиматроида являются в точности объединениями путей. [9] Если любой возможный набор антиматроида, элемент что может быть удалено из чтобы сформировать другое допустимое множество называется конечной точкой из, а возможный набор, имеющий только одну конечную точку, называется путем антиматроида. [10] Семейство путей может быть частично упорядочено включением множества, формируя poset пути антиматроида. [11]
Для каждого возможного набора в антиматроиде, и каждый элемент из , можно найти подмножество путей для которого является конечной точкой: для этого удаляйте по одному элементы, кроме до тех пор, пока такое удаление не останется возможным Следовательно, каждое допустимое множество в антиматроиде является объединением его подмножеств путей. [9] Еслиэто не путь, каждое подмножество в этом союзе является собственным подмножеством из. Но если сам по себе путь с конечной точкой , каждое собственное подмножество то, что принадлежит антиматроиду, исключает . Следовательно, пути антиматроида - это в точности возможные множества, которые не равны объединениям их собственных допустимых подмножеств. Эквивалентно данное семейство наборов образует семейство путей антиматроида тогда и только тогда, когда для каждого в , объединение подмножеств в имеет на один элемент меньше, чем сам. [12] Если да, сам по себе является семейством объединений подмножеств . [9]
В формальной языковой формализации антиматроида мы также можем идентифицировать подмножество слов, которые определяют весь язык, основные слова . Если это формальный язык антиматроидов, самые длинные строки в называются основными словами . Каждое базовое слово образует перестановку всего алфавита. [13] Например, основные слова антиматроида poset - это линейные расширения данного частичного порядка. [14] Если это набор основных слов, можно определить из как набор префиксов слов в . [15]
Выпуклая геометрия
Если это заданная система, определяющая антиматроида, с равняется объединению множеств в , то семейство множеств
В дополнение к свойствам систем множеств, которые определяют антиматроидов, система множеств, определяющая выпуклую геометрию, должна быть замкнута относительно пересечений, и для любого множества в это не равно должен быть элемент не в что можно добавить к сформировать еще один набор в .
Выпуклая геометрия также может быть определена в терминах оператора замыкания который отображает любое подмножество к его минимальному закрытому надмножеству. Чтобы быть оператором закрытия, должен иметь следующие свойства:
- : закрытие пустого множества пусто.
- Для каждого подмножества из , это подмножество а также .
- В любое время , это подмножество .
Семейство замкнутых множеств, возникающих в результате операции замыкания этого типа, обязательно замкнуто относительно пересечений. Операторы замыкания, определяющие выпуклые геометрии, также удовлетворяют дополнительной аксиоме антиобмена :
- Если это подмножество , а также а также являются отдельными элементами которые не принадлежат , но принадлежит , тогда не принадлежит .
Операция закрытия, удовлетворяющая этой аксиоме, называется закрытием антиобмена . Если является замкнутым множеством в замыкании антиобмена, то аксиома антиобмена определяет частичный порядок на элементах, не принадлежащих , где в частичном порядке, когда принадлежит . Если является минимальным элементом этого частичного порядка, то закрыто. То есть семейство замкнутых множеств антиобменного замыкания обладает тем свойством, что для любого множества, отличного от универсального, существует элементкоторые можно добавить к нему, чтобы получить еще один закрытый набор. Это свойство дополняет свойство доступности антиматроидов, а тот факт, что пересечения замкнутых множеств замкнуты, дополняет свойство, что объединение допустимых множеств в антиматроиде возможно. Следовательно, дополнения замкнутых множеств любого антиобменного замыкания образуют антиматроид. [16]
В неориентированных графах , в которых выпуклые множествах (подмножества вершин , которые содержат все кратчайшие пути между вершинами в подмножестве) образует выпуклые геометрии в точности графа Птолемеев . [17]
Дистрибутивные решетки
Каждые два возможных набора антиматроида имеют уникальную наименьшую верхнюю границу (их объединение) и уникальную наибольшую нижнюю границу (объединение наборов антиматроида, содержащихся в обоих из них). Следовательно, возможные множества антиматроида, частично упорядоченные включением множеств, образуют решетку . Различные важные особенности антиматроида можно интерпретировать в терминах теории решетки; например, пути антиматроида являются неразложимыми соединением элементами соответствующей решетки, а основные слова антиматроида соответствуют максимальным цепям в решетке. Решетки, которые возникают из антиматроидов таким образом, обобщают конечные распределительные решетки и могут быть охарактеризованы несколькими различными способами.
- Описание, первоначально рассмотренное Дилвортом (1940), касается встречно-неприводимых элементов решетки. Для каждого элемента антиматроида существует единственное максимально допустимое множество что не содержит : можно построить как объединение всех допустимых множеств, не содержащих . Этот наборавтоматически пересекается-неприводимым, что означает, что это не пересечение любых двух больших элементов решетки. Это верно, потому что каждая возможная надмножество содержит , и, следовательно, то же самое верно и для каждого пересечения допустимых надмножеств. Каждый элемент произвольной решетки может быть разложен как пересечение встречающихся неприводимых множеств, часто несколькими способами, но в решетке, соответствующей антиматроиду, каждый элемент имеет единственное минимальное семейство встречно неприводимых множеств, пересечение которых ; это семейство состоит из множеств для элементов такой, что возможно. То есть решетка имеет единственные неразложимые по встрече разложения .
- Вторая характеристика касается интервалов в решетке, подрешеток, определяемых парой элементов решетки состоящий из всех элементов решетки с участием . Интервал является атомистическим, если каждый элемент в нем представляет собой соединение атомов (минимальные элементы над нижним элементом), и он булева, если он изоморфен решетке всех подмножеств конечного множества. Для антиматроида каждый атомистический интервал также является логическим.
- В-третьих, решетки, возникающие из антиматроидов, являются полумодулярными решетками , решетками, которые удовлетворяют верхнему полумодулярному закону, согласно которому для любых двух элементов а также , если охватывает тогда охватывает . Перевод этого условия в допустимые наборы антиматроида, если допустимый набор имеет только один элемент, не принадлежащий другому допустимому набору тогда этот один элемент может быть добавлен к чтобы сформировать еще один набор в антиматроиде. Кроме того, решетка антиматроида обладает встречно-полудистрибутивным свойством : для всех элементов решетки, , а также , если а также равны друг другу, тогда они оба равны . Полумодулярная и встречно-полудистрибутивная решетка называется джойн -дистрибутивной решеткой .
Эти три характеристики эквивалентны: любая решетка с уникальными встречно-неприводимыми разложениями имеет булевы атомистические интервалы и является объединенно-дистрибутивной, любая решетка с булевыми атомистическими интервалами имеет уникальные встречно-неприводимые разложения и является объединенно-дистрибутивной, а любая объединенно-дистрибутивная решетка имеет уникальные встречающиеся неприводимые разложения и булевы атомистические интервалы. [18] Таким образом, мы можем называть решетку с любым из этих трех свойств дистрибутивной по объединению. Любой антиматроид порождает конечную объединенно-распределительную решетку, и любая конечная объединенно-распределительная решетка происходит от антиматроида таким образом. [19] Другой эквивалентной характеристикой конечных объединенно-дистрибутивных решеток является то, что они градуированы (любые две максимальные цепи имеют одинаковую длину), а длина максимальной цепи равна количеству встречно-неприводимых элементов решетки. [20] Антиматроид, представляющий конечную объединенно-дистрибутивную решетку, может быть восстановлен из решетки: элементы антиматроида могут быть взяты как встречно-неприводимые элементы решетки, а допустимое множество, соответствующее любому элементу решетки состоит из множества встречно неприводимых элементов такой, что не больше или равно в решетке.
Это представление любой конечной дистрибутивной решетки в виде доступного семейства множеств, замкнутых относительно объединений (т. Е. Как антиматроид), можно рассматривать как аналог теоремы Биркгофа о представлении, согласно которой любая конечная дистрибутивная решетка имеет представление в виде семейства множеств закрыто под союзами и пересечениями.
Сверхрешаемые антиматроиды
Мотивированный проблемой определения частичных порядков на элементах группы Кокстера , Армстронг (2009) изучил антиматроиды, которые также являются сверхразрешимыми решетками. Сверхразрешимый антиматроид определяется полностью упорядоченным набором элементов и семейством наборов этих элементов. В семье обязательно должен быть пустой набор. Кроме того, он должен иметь свойство, что если два набора а также принадлежат семье, теоретико-множественная разность непусто, и это наименьший элемент , тогда тоже принадлежит семье. Как отмечает Армстронг, любое семейство наборов этого типа образует антиматроида. Армстронг также дает теоретико-решеточную характеристику антиматроидов, которые может образовывать эта конструкция. [21]
Операция соединения и выпуклый размер
Если а также два antimatroids, как описано как семейство множеств над одной и той же вселенной элементов, мы можем сформировать другой antimatroid, то присоединиться в а также , следующим образом:
Соединения тесно связаны с операцией закрытия, которая сопоставляет формальные языки с антиматроидами, где закрытие языка является пересечением всех антиматроидов, содержащих как подъязык. Это замыкание, по возможности, устанавливает объединения префиксов строк в. В терминах этой операции замыкания соединение - это закрытие объединения языков а также . Каждый антиматроид может быть представлен как соединение семейства цепных антиматроидов или, что эквивалентно, как замыкание набора основных слов; выпуклая размерность из antimatroid- минимальное количество цепных антиматроидов (или, что эквивалентно, минимальное количество основных слов) в таком представлении. Если семейство цепных антиматроидов, все основные слова которого принадлежат , тогда генерирует тогда и только тогда, когда допустимые наборы включить все пути . Путипринадлежащий антиматроиду с одной цепью, должен образовывать цепочку на пути poset, поэтому выпуклая размерность антиматроида равна минимальному количеству цепей, необходимых для покрытия poset пути, что по теореме Дилворта равно ширине poset пути. [23]
Если у кого-то есть представление об антиматроиде как о замыкании набора базовые слова, то это представление можно использовать для сопоставления возможных наборов антиматроида с точками в -мерное евклидово пространство: назначьте одну координату для каждого основного слова , и сделаем значение координаты допустимого набора быть длиной самого длинного префикса это подмножество . С этим вложением, является подмножеством другого допустимого множества тогда и только тогда, когда координаты для все меньше или равны соответствующим координатам . Следовательно, размерность порядка включения допустимых множеств не более чем равна выпуклой размерности антиматроида. [24] Однако в целом эти два измерения могут сильно отличаться: существуют антиматроиды с размерностью третьего порядка, но со сколь угодно большой выпуклой размерностью. [25]
Перечисление
Число возможных антиматроидов в наборе элементов быстро растет вместе с количеством элементов в наборе. Для наборов из одного, двух, трех и т.д. элементов количество различных антиматроидов равно [26]
Приложения
Как приоритетность, так и ограничения по времени выпуска в стандартных обозначениях для теоретических задач планирования могут быть смоделированы антиматроидами. Boyd & Faigle (1990) используют antimatroids обобщить жадный алгоритм из Eugene Лоулера для оптимального решения задач однопроцессорных планирований с очередностью , в которой цель состоит в том, чтобы минимизировать максимальное наказание , понесенное в конце календарного планированием задачи.
Глассерман и Яо (1994) используют антиматроиды для моделирования порядка событий в системах моделирования дискретных событий .
Пармар (2003) использует антиматроидов для моделирования прогресса в достижении цели в задачах планирования искусственного интеллекта .
В теории оптимальности , математической модели для развития естественного языка, основанной на оптимизации при ограничениях, грамматики логически эквивалентны антиматроидам. [27]
В математической психологии антиматроиды использовались для описания возможных состояний знания человека, обучающегося. Каждый элемент антиматроида представляет собой концепцию, которую должен понять учащийся, или класс задач, которые он или она может правильно решить, а наборы элементов, которые образуют антиматроид, представляют возможные наборы концепций, которые могут быть решены. понимает один человек. Аксиомы, определяющие антиматроид, можно неформально сформулировать как утверждение, что изучение одной концепции никогда не может помешать учащемуся изучить другую концепцию, и что любое достижимое состояние знаний может быть достигнуто путем изучения одной концепции за раз. Задача системы оценки знаний состоит в том, чтобы вывести набор понятий, известных данному учащемуся, путем анализа его или ее ответов на небольшой и хорошо подобранный набор проблем. В этом контексте антиматроидов также называют «пространствами обучения» и «пространствами хорошо оцененных знаний». [28]
Заметки
- ^ Две ранние ссылки: Эдельман (1980) и Джеймисон (1980) ; Джемисон был первым, кто использовал термин «антиматроид». Монжарде (1985) рассматривает историю повторного открытия антиматроидов.
- ^ См., Например, Kempner & Levit (2003) , определение 2.1 и предложение 2.3, с. 2.
- ^ Корте, Lovász & Schrader (1991) , стр. 22.
- ^ a b Korte, Lovász & Schrader (1991) , стр. 5.
- ↑ Korte, Lovász & Schrader (1991) , теорема 1.4, стр. 24.
- ^ а б в Гордон (1997) .
- ^ Kashiwabara, Nakamura & Okamoto (2005) .
- ^ Гордон (1997) описывает несколько результатов, относящихся к антиматроидам этого типа, но эти антиматроиды упоминались ранее, например, Корте, Ловасом и Шрадером (1991) . Chandran et al. (2003) используют связь с антиматроидами как часть алгоритма для эффективного перечисления всех порядков идеального исключения данного хордального графа.
- ^ a b c Korte, Lovász & Schrader (1991) , лемма 3.12, с. 31.
- ^ Корте, Lovász & Schrader (1991) , стр. 31.
- ↑ Korte, Lovász & Schrader (1991) , стр. 39–43.
- ^ См. Korte, Lovász & Schrader (1991) , теорема 3.13, стр. 32, который определяет пути как корневые множества , наборы с выделенным элементом и устанавливает эквивалентную характеристику семейств корневых множеств, которые образуют пути антиматроидов.
- ↑ Korte, Lovász & Schrader (1991) , стр. 6, 22.
- ↑ Korte, Lovász & Schrader (1991) , стр. 24–25.
- ↑ См. Korte, Lovász & Schrader (1991) , стр. 22: «любое слово в антиматроиде может быть расширено до основного слова».
- ↑ Korte, Lovász & Schrader (1991) , теорема 1.1, стр. 10.
- ^ Фарбер и Джеймисон (1986) .
- ^ Адаричева, Горбунов и Туманов (2003) , теоремы 1.7 и 1.9; Армстронг (2009) , теорема 2.7.
- ^ Эдельман (1980) , теорема 3.3; Армстронг (2009) , теорема 2.8.
- ^ Монжарде (1985) приписывает двойственную форму этой характеристики нескольким работам С.П. Аванна 1960-х годов.
- ^ Армстронг (2009) .
- ^ Корте, Lovász & Schrader (1991) , стр. 42; Эппштейн (2008) , раздел 7.2; Falmagne et al. (2013) , раздел 14.4.
- ^ Эдельман и Сакс (1988) ; Корте, Ловас и Шредер (1991) , теорема 6.9.
- ^ Корте, Lovász & Schrader (1991) , следствие 6.10.
- ^ Эпштайна (2008) , Рисунок 15.
- ^ Слоан, Н. Дж. А. (редактор), «Последовательность A119770» , Он -лайн энциклопедия целочисленных последовательностей , Фонд OEIS
- ^ Merchant & Riggle (2016) .
- ^ Doignon & Falmagne (1999) .
Рекомендации
- Адаричева, К.В. Горбунов В.А.; Туманов, В. (2003), "Join-Полудистрибутивные решетки и выпуклые геометрии", Advances по математике , 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 , Руководство по ремонту 2568800 , S2CID 15474840.
- Биркгоф, Гарретт ; Bennett, MK (1985), "Выпуклость решетка посета" , Order , 2 (3): 223-242, DOI : 10.1007 / BF00333128 (неактивный 2021-01-16)CS1 maint: DOI неактивен с января 2021 г. ( ссылка ).
- Бьёрнер, Андерс ; Зиглер, Гюнтер М. (1992), «Введение в гридоиды» , в Уайт, Нил (ред.), Приложения Matroid , Энциклопедия математики и ее приложений, 40 , Кембридж: Cambridge University Press, стр. 284–357 , doi : 10.1017 / CBO9780511662041.009 , ISBN 0-521-38165-7, Руководство по ремонту 1165537 CS1 maint: обескураженный параметр ( ссылка )
- Бойд, Э. Эндрю; Faigle, Ульрих (1990), "Алгоритмический характеристика antimatroids", Дискретная прикладная математика , 28 (3): 197-205, DOI : 10.1016 / 0166-218X (90) 90002-Т , ЛВП : 1911/101636.
- Чандран, LS; Ibarra, L .; Раски, Ф .; Sawada, J. (2003), "Создание и характеризующее идеальные отборочные упорядочения в хорде графы" (PDF) , теоретическая информатика , 307 (2): 303-317, DOI : 10.1016 / S0304-3975 (03) 00221- 4
- Dilworth, Роберт П. (1940), "Решетка с уникальными неприводимыми разложениями", Анналы математики , 41 (4): 771-777, да : 10,2307 / 1968857 , JSTOR 1968857.
- Дуаньон, Жан-Поль; Фальмань, Жан-Клод (1999), Пространства знаний , Springer-Verlag, ISBN 3-540-64501-2 CS1 maint: обескураженный параметр ( ссылка ).
- Edelman, Пол Х. (1980), "Meet-дистрибутивные решетки и закрытие анти-обмена", Алгебра Universalis , 10 (1): 290-299, DOI : 10.1007 / BF02482912 , S2CID 120403229.
- Эдельман, Пол Х .; Сакс, Michael E. (1988), "Комбинаторное представление и выпуклая размерность выпуклых геометрий", заказ , 5 (1): 23-32, DOI : 10.1007 / BF00143895 , S2CID 119826035.
- Эпштейн, Дэвид (2008), Учебные последовательности , arXiv : 0803.4030. Частично адаптировано как главы 13 и 14 Руководства. Фальмань, Жан-Клод ; Альберт, Дитрих; Добл, Крис; Эпштейн, Дэвид ; Ху, Сяньген, ред. (2013), Пространства знаний: приложения в образовании , 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 , ЛВП : 10338.dmlcz / 127659 , MR 0844046.
- Глассерман, Пол; Яо, Дэвид Д. (1994), Монотонная структура в системах с дискретными событиями , Серия Wiley по вероятности и статистике, Wiley Interscience, ISBN 978-0-471-58041-6.
- Гордон, Гэри (1997), "A & beta инвариантное для greedoids и antimatroids", Электронный журнал комбинаторики , 4 (1): Исследования бумага 13, DOI : 10,37236 / 1298 , MR 1445628.
- Джеймисон, Роберт (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, MR 0608454.
- Кашивабара, Кендзи; Накамура, Масатака; Окамото, Иошио (2005), "аффинная теорема представления для абстрактных выпуклых геометрий", Вычислительная геометрия , 30 (2): 129-144, CiteSeerX 10.1.1.14.4965 , DOI : 10.1016 / j.comgeo.2004.05.001 , М.Р. 2107032.
- Кемпнер, Юлия; Левита, Вадим Евгеньевич (2003), "Переписка между двумя antimatroid алгоритмических характеризации" , Электронный журнал комбинаторике , 10 : Исследование бумаги 44, DOI : 10,37236 / 1737 , MR 2014531 , S2CID 11015967
- Корте, Бернхард ; Ловас, Ласло ; Шредер, Райнер (1991), Greedoids , Springer-Verlag, стр. 19–43, ISBN 3-540-18190-3.
- Торговец, Назарре; Riggle, Джейсон (2016), "OT грамматик, вне частичных порядков: наборы ERC и antimatroids" , естественного языка и теории лингвистический , 34 : 241-269, DOI : 10.1007 / s11049-015-9297-5 , S2CID 170567540.
- Monjardet, Bernard (1985), "Применение для часто заново понятие", заказ , 1 (4): 415-417, DOI : 10.1007 / BF00582748 , S2CID 119378521.
- Пармар, Аарати (2003), "Некоторые математические структуры, лежащие в основе эффективного планирования", Весенний симпозиум AAAI по логической формализации здравого смысла (PDF).