Введение

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

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

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

В теории множеств аксиоматизации антиматроида существуют определенные специальные множества, называемые путями, которые определяют весь антиматроид, в том смысле, что множества антиматроида являются точно союзами путей. Если – любое допустимое множество антиматроида, элемент, который можно удалить из , чтобы получить другое допустимое множество, называется концом (endpoint) множества , а допустимое множество, имеющее только один конец, называется путем антиматроида. Семейство путей можно частично упорядочить по включению множеств, образуя посет путей антиматроида. Для каждого допустимого множества в антиматроиде и каждого элемента из , можно найти путь, являющийся подмножеством , для которого является концом: для этого удаляйте по одному элементы, отличные от , пока такое удаление не оставит допустимое подмножество. Следовательно, каждое допустимое множество в антиматроиде является объединением его путевых подмножеств. Если не является путем, каждое подмножество в этом объединении является собственным подмножеством . Но если является путем с концом , каждое собственное подмножество , принадлежащее антиматроиду, не содержит . Поэтому пути антиматроида – это именно допустимые множества, которые не равны объединениям их собственных допустимых подмножеств. Эквивалентно, данное семейство множеств образует семейство путей антиматроида тогда и только тогда, когда для каждого из , объединение подмножеств из содержит на один элемент меньше, чем само . Если это так, то само является семейством объединений подмножеств . В формальной языковой формализации антиматроида самые длинные строки называются базисными словами. Каждое базисное слово образует перестановку всего алфавита. Если – множество базисных слов, то можно определить как множество префиксов слов из .

Стройные решетки

Каждый из двух допустимых множеств антиматроида имеет уникальную наименьшую верхнюю границу (их объединение) и уникальную наибольшую нижнюю границу (объединение множеств в антиматроиде, содержащихся в обоих из них). Следовательно, допустимые множества антиматроида, частично упорядоченные по включению, образуют решетку. Различные важные свойства антиматроида можно интерпретировать в терминах теории решеток; например, пути антиматроида являются элементами, неразложимыми при соединении, соответствующей решетки, а базисные слова антиматроида соответствуют максимальным цепям в решетке. Решетки, возникающие из антиматроидов таким образом, обобщают конечные дистрибутивные решетки и могут быть охарактеризованы несколькими различными способами. Описание, первоначально предложенное, касается элементов, неразложимых при пересечении, решетки. Для каждого элемента антиматроида существует уникальное максимально допустимое множество, не содержащее : его можно построить как объединение всех допустимых множеств, не содержащих . Это множество автоматически неразложимо при пересечении, то есть не является пересечением любых двух больших элементов решетки. Это верно, потому что каждое допустимое надмножество содержит , и то же самое, следовательно, верно для каждого пересечения допустимых надмножеств. Каждый элемент произвольной решетки можно разложить как пересечение элементов, неразложимых при пересечении, часто несколькими способами, но в решетке, соответствующей антиматроиду, каждый элемент имеет уникальное минимальное семейство элементов, неразложимых при пересечении, пересечение которых равно ; это семейство состоит из множеств для элементов , которые являются допустимыми. То есть решетка имеет уникальные разложения на элементы, неразложимые при пересечении. Вторая характеристика касается интервалов в решетке, подрешеток, определяемых парой элементов решетки, состоящих из всех элементов решетки с . Интервал является атомистическим, если каждый элемент в нем является соединением атомов (минимальных элементов выше нижнего элемента), и он является булевым, если он изоморфен решетке всех подмножеств конечного множества. Для антиматроида каждый атомистический интервал также является булевым. В-третьих, решетки, возникающие из антиматроидов, являются полумодульными решетками, решетками, удовлетворяющими верхнему полумодульному закону: для любых двух элементов и , если покрывает , то покрывает . Переводя это условие в допустимые множества антиматроида, если допустимое множество имеет только один элемент, не принадлежащий другому допустимому множеству , то этот один элемент можно добавить к , чтобы сформировать другое множество в антиматроиде. Кроме того, решетка антиматроида обладает свойством полудистрибутивности по пересечению: для всех элементов решетки , , и , если и равны друг другу, то они также равны . Полумодульная и полудистрибутивная решетка называется решеткой с дистрибутивным соединением. Эти три характеристики эквивалентны: любая решетка с уникальными разложениями на элементы, неразложимые при пересечении, имеет булевы атомистические интервалы и является решеткой с дистрибутивным соединением, любая решетка с булевыми атомистическими интервалами имеет уникальные разложения на элементы, неразложимые при пересечении, и является решеткой с дистрибутивным соединением, и любая решетка с дистрибутивным соединением имеет уникальные разложения на элементы, неразложимые при пересечении, и булевы атомистические интервалы. Таким образом, мы можем относить решетку с любым из этих трех свойств к решеткам с дистрибутивным соединением. Любой антиматроид порождает конечную решетку с дистрибутивным соединением, и любая конечная решетка с дистрибутивным соединением возникает из антиматроида таким образом. Другая эквивалентная характеристика конечных решеток с дистрибутивным соединением состоит в том, что они градуированы (любые две максимальные цепи имеют одинаковую длину), а длина максимальной цепи равна числу элементов, неразложимых при пересечении, решетки. Антиматроид, представляющий конечную решетку с дистрибутивным соединением, может быть восстановлен из решетки: элементы антиматроида можно принять за элементы, неразложимые при пересечении, решетки, а допустимое множество, соответствующее любому элементу решетки, состоит из множества элементов, неразложимых при пересечении, таких, что не больше или равно в решетке. Это представление любой конечной решетки с дистрибутивным соединением как доступного семейства множеств, замкнутых относительно объединений (то есть как антиматроида), можно рассматривать как аналог теоремы представления Биркгофа, согласно которой любая конечная дистрибутивная решетка имеет представление в виде семейства множеств, замкнутых относительно объединений и пересечений.

Суперрастворимые антиматроиды

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

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

Количество возможных антиматроидов на множестве элементов быстро растет с увеличением числа элементов в множестве. Для множеств из одного, двух, трех и так далее элементов, число различных антиматроидов равно

Приложения

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