En matemáticas , un antimatroide es un sistema formal que describe procesos en los que se construye un conjunto mediante la inclusión de elementos de uno en uno, y en los que un elemento, una vez disponible para su inclusión, permanece disponible hasta que se incluye. [1] Los antimatroides se axiomatizan comúnmente de dos maneras equivalentes , ya sea como un sistema de conjuntos que modela los posibles estados de dicho proceso, o como un lenguaje formal que modela las diferentes secuencias en las que se pueden incluir elementos. Dilworth (1940) fue el primero en estudiar los antimatroides, utilizando otra axiomatización basada en la teoría de la red., y han sido redescubiertos con frecuencia en otros contextos. [2]
Los axiomas que definen a los antimatroides como sistemas de conjuntos son muy similares a los de los matroides , pero mientras que los matroides se definen por un axioma de intercambio , los antimatroides se definen en cambio por un axioma anti-intercambio , del que deriva su nombre. Los antimatroides pueden verse como un caso especial de greedoides y de celosías semimodulares , y como una generalización de órdenes parciales y de celosías distributivas . Los antimatroides son equivalentes, por complementación , a las geometrías convexas , una abstracción combinatoria de conjuntos convexos en geometría .
Los antimatroides se han aplicado para modelar restricciones de precedencia en problemas de programación , posibles secuencias de eventos en simulaciones, planificación de tareas en inteligencia artificial y los estados de conocimiento de los aprendices humanos.
Definiciones
Un antimatroide se puede definir como una familia finita de conjuntos, llamados conjuntos factibles , con las dos propiedades siguientes: [3]
- La unión de dos conjuntos factibles cualesquiera también es factible. Es decir,está cerrado bajo sindicatos.
- Si es un conjunto factible no vacío, entonces contiene un elemento para cual (el conjunto formado quitando de ) también es factible. Es decir,es un sistema de set accesible .
Los antimatroides también tienen una definición equivalente a un lenguaje formal , es decir, como un conjunto de cadenas definidas a partir de un alfabeto finito de símbolos . Una cadena que pertenece a este conjunto se llama palabra del idioma. Un idiomadefinir un antimatroide debe satisfacer las siguientes propiedades: [4]
- Cada símbolo del alfabeto aparece en al menos una palabra de .
- Cada palabra de contiene como máximo una copia de cada símbolo. Un idioma con esta propiedad se llama normal . [5]
- Cada prefijo de una palabra en también está en . Un idioma con esta propiedad se llama hereditario . [5]
- Si y son palabras en , y contiene al menos un símbolo que no está en , entonces hay un símbolo en tal que la concatenación es otra palabra en .
La equivalencia de estas dos formas de definición se puede ver de la siguiente manera. Si es un antimatroide definido como un lenguaje formal, entonces los conjuntos de símbolos en palabras de Formar un sistema de conjunto cerrado de unión accesible. Es accesible por la propiedad hereditaria de las cadenas, y se puede demostrar que está cerrada por unión mediante la aplicación repetida de la propiedad de concatenación de las cadenas. En la otra dirección, desde un sistema de conjunto cerrado de unión accesible, el lenguaje de cadenas normales cuyos prefijos tienen todos conjuntos de símbolos pertenecientes a cumple con los requisitos para que un lenguaje formal sea un antimatroide. Estas dos transformaciones son inversas entre sí: la transformación de un lenguaje formal en un conjunto de familias y viceversa, produce el mismo sistema. Por tanto, estas dos definiciones conducen a clases de objetos matemáticamente equivalentes. [6]
Ejemplos de
Los siguientes sistemas proporcionan ejemplos de antimatroides:
- Antimatroides de cadena
- Los prefijos de una sola cadena y los conjuntos de símbolos en estos prefijos forman un antimatroide. Por ejemplo, la cadena antimatroide definida por la cadena tiene como lenguaje formal el conjunto de cuerdas (dónde denota la cadena vacía ) y como su familia de conjuntos factibles la familia [7]
- Poset antimatroides
- Los conjuntos inferiores de un conjunto finito parcialmente ordenado forman un antimatroide, y las palabras completas del antimatroide forman las extensiones lineales del orden parcial. [8] Según el teorema de representación de Birkhoff para retículas distributivas, los conjuntos factibles en un antimatroide poset (ordenados por inclusión de conjuntos) forman una retícula distributiva, y todas las retículas distributivas pueden formarse de esta manera. Por lo tanto, los antimatroides pueden verse como generalizaciones de redes distributivas. Un antimatroide de cadena es el caso especial de un antimatroide poset para un pedido total . [7]
- Bombardeo de antimatroides
- Una secuencia de bombardeo de un conjunto finito de puntos en el plano euclidiano o un espacio euclidiano de dimensiones superiores se forma eliminando repetidamente los vértices del casco convexo . Los conjuntos factibles del antimatroide formado por estas secuencias son las intersecciones de con el complemento de un conjunto convexo. [7] Todo antimatroide es isomórfico a un antimatroide de bombardeo de puntos en un espacio de dimensiones suficientemente altas. [9]
- Eliminación perfecta
- Una ordenación de eliminación perfecta de un grafo cordal es una ordenación de sus vértices tal que, para cada vértice , los vecinos de que ocurren después de en el orden forman una camarilla . Los prefijos de los ordenamientos de eliminación perfecta de un gráfico de cuerdas forman un antimatroide. [10]
- Juegos de disparar chips
- Los juegos de disparar chips como el modelo abelian sandpile se definen mediante un gráfico dirigido junto con un sistema de "chips" colocados en sus vértices. Siempre que el número de fichas en un vértice es al menos tan grande como el número de aristas de , es posible disparar, moviendo una ficha a cada vértice vecino. El evento que incendios para el El tiempo solo puede pasar si ya ha disparado. tiempos y acumulados fichas totales. Estas condiciones no dependen del orden de los disparos anteriores y siguen siendo verdaderas hasta se dispara, por lo que cualquier gráfico y colocación inicial de chips para los que termina el sistema define un antimatroide en los pares . Una consecuencia de la propiedad antimatroide de estos sistemas es que, para un estado inicial dado, el número de veces que se dispara cada vértice y el eventual estado estable del sistema no dependen del orden de disparo. [11]
Caminos y palabras básicas
En la axiomatización teórica de conjuntos de un antimatroide hay ciertos conjuntos especiales llamados caminos que determinan el antimatroide completo, en el sentido de que los conjuntos del antimatroide son exactamente las uniones de caminos. [12] Si es cualquier conjunto factible del antimatroide, un elemento que se puede quitar de para formar otro conjunto factible se llama un punto final de, y un conjunto factible que tiene solo un punto final se denomina ruta del antimatroide. [13] La familia de caminos se puede ordenar parcialmente por inclusión de conjuntos, formando el conjunto de caminos del antimatroide. [14]
Para cada conjunto factible en el antimatroide, y cada elemento de , uno puede encontrar un subconjunto de ruta de para cual es un punto final: para hacerlo, elimine uno a la vez los elementos que no sean hasta que ninguna eliminación deje un subconjunto factible. Por lo tanto, cada conjunto factible en un antimatroide es la unión de sus subconjuntos de caminos. [12] Sino es una ruta, cada subconjunto en esta unión es un subconjunto adecuado de. Pero si es en sí mismo un camino con punto final , cada subconjunto adecuado de que pertenece al antimatroide excluye . Por lo tanto, las trayectorias de un antimatroide son exactamente los conjuntos factibles que no igualan las uniones de sus propios subconjuntos factibles. De manera equivalente, una familia dada de conjuntos forma la familia de caminos de un antimatroide si y solo si, para cada en , la unión de subconjuntos de en tiene un elemento menos que sí mismo. [15] Si es así, en sí misma es la familia de uniones de subconjuntos de . [12]
En la formalización del lenguaje formal de un antimatroide, las cadenas más largas se denominan palabras básicas . Cada palabra básica forma una permutación de todo el alfabeto. [16] Si es el conjunto de palabras básicas, se puede definir desde como el conjunto de prefijos de palabras en . [17]
Geometrías convexas
Si es el sistema establecido que define un antimatroide, con igual a la unión de los conjuntos en , luego la familia de conjuntos
Una geometría convexa también se puede definir en términos de un operador de cierre. que mapea cualquier subconjunto de a su superconjunto cerrado mínimo. Para ser un operador de cierre,debe tener las siguientes propiedades: [19]
- : el cierre del conjunto vacío está vacío.
- Para cada subconjunto de , es un subconjunto de y .
- Cuando sea , es un subconjunto de .
La familia de conjuntos cerrados que resulta de una operación de cierre de este tipo está necesariamente cerrada bajo intersecciones, pero podría no ser una geometría convexa. Los operadores de cierre que definen geometrías convexas también satisfacen un axioma anti-intercambio adicional :
- Si es un subconjunto de , y y son elementos distintos de que no pertenecen a , pero pertenece a , luego no pertenece al . [19]
Una operación de cierre que satisface este axioma se denomina cierre antiintercambio . Si es un conjunto cerrado en un cierre anti-intercambio, entonces el axioma anti-intercambio determina un orden parcial en los elementos que no pertenecen a , dónde en el orden parcial cuando pertenece a . Si es un elemento mínimo de este orden parcial, entonces está cerrado. Es decir, la familia de conjuntos cerrados de un cierre anti-intercambio tiene la propiedad de que para cualquier conjunto distinto al conjunto universal existe un elementoque se pueden agregar para producir otro conjunto cerrado. Esta propiedad es complementaria a la propiedad de accesibilidad de los antimatroides, y el hecho de que las intersecciones de conjuntos cerrados sean cerrados es complementario a la propiedad de que las uniones de conjuntos factibles en un antimatroide son factibles. Por tanto, los complementos de los conjuntos cerrados de cualquier cierre anti-intercambio forman un antimatroide. [18]
Los gráficos no dirigidos en los que los conjuntos convexos (subconjuntos de vértices que contienen todos los caminos más cortos entre los vértices del subconjunto) forman una geometría convexa son exactamente los gráficos ptolemaicos . [20]
Rejillas unidas-distributivas
Cada dos conjuntos factibles de un antimatroide tienen un límite superior mínimo único (su unión) y un límite inferior máximo único (la unión de los conjuntos en el antimatroide que están contenidos en ambos). Por lo tanto, los conjuntos factibles de un antimatroide, parcialmente ordenados por inclusión de conjuntos, forman una red . Varias características importantes de un antimatroide se pueden interpretar en términos teóricos de celosía; por ejemplo, las trayectorias de un antimatroide son los elementos irreductibles de unión del enrejado correspondiente, y las palabras básicas del antimatroide corresponden a cadenas máximas en el enrejado. Las celosías que surgen de los antimatroides de esta manera generalizan las celosías distributivas finitas y se pueden caracterizar de varias formas diferentes.
- La descripción considerada originalmente por Dilworth (1940) se refiere a elementos irreductibles de la rejilla. Para cada elemento de un antimatroide, existe un conjunto factible máximo único que no contiene : puede construirse como la unión de todos los conjuntos factibles que no contienen . Este conjuntoes automáticamente meet-irreducible, lo que significa que no es el encuentro de dos elementos de celosía más grandes. Esto es cierto porque cada superconjunto factible de contiene , y lo mismo es, por lo tanto, también cierto para cada intersección de superconjuntos factibles. Cada elemento de una celosía arbitraria puede descomponerse como una reunión de conjuntos irreducibles de encuentro, a menudo de múltiples formas, pero en la celosía correspondiente a un antimatroide cada elemento. tiene una familia mínima única de conjuntos irreductibles de encuentro cuyo encuentro es ; esta familia consta de los conjuntos para los elementos tal que Es factible. Es decir, la celosía tiene descomposiciones únicas irreductibles .
- Una segunda caracterización se refiere a los intervalos en la celosía, las subredes definidas por un par de elementos de celosía. que consta de todos los elementos de celosía con . Un intervalo es atomístico si cada elemento en él es la unión de átomos (los elementos mínimos sobre el elemento inferior), y es booleano si es isomorfo a la red de todos los subconjuntos de un conjunto finito. Para un antimatroide, cada intervalo atomístico también es booleano.
- En tercer lugar, las celosías que surgen de los antimatroides son celosías semimodulares , celosías que satisfacen la ley semimodular superior que por cada dos elementos y , Si cubre luego cubre . Traducir esta condición en los conjuntos factibles de un antimatroide, si es un conjunto factible tiene solo un elemento que no pertenece a otro conjunto factible entonces ese elemento puede agregarse a para formar otro conjunto en el antimatroide. Además, la celosía de un antimatroide tiene la propiedad de encuentro semidistributiva : para todos los elementos de la celosía, , y , Si y iguales entre sí, entonces también ambos son iguales . Un retículo semimodular y semidistributivo de encuentro se denomina retículo distributivo de unión .
Estas tres caracterizaciones son equivalentes: cualquier retículo con descomposiciones irreductibles de encuentro únicas tiene intervalos atomísticos booleanos y es distributivo de unión, cualquier retículo con intervalos atomísticos booleanos tiene descomposiciones irreductibles de encuentro únicas y es distributivo de unión, y cualquier retículo distributivo de unión tiene un valor único. descomposiciones irreducibles e intervalos atomísticos booleanos. [21] Por lo tanto, podemos referirnos a un retículo con cualquiera de estas tres propiedades como unir-distributivo. Cualquier antimatroide da lugar a un retículo distributivo de unión finito, y cualquier retículo distributivo de unión finito proviene de un antimatroide de esta manera. [22] Otra caracterización equivalente de las celosías distributivas de unión finitas es que están graduadas (dos cadenas máximas cualesquiera tienen la misma longitud), y la longitud de una cadena máxima es igual al número de elementos irreducibles de la celosía. [23] El antimatroide que representa una celosía distributiva de unión finita se puede recuperar de la celosía: los elementos del antimatroide se pueden tomar como los elementos irreductibles de la reunión de la celosía, y el conjunto factible corresponde a cualquier elemento de la celosía consiste en el conjunto de elementos irreductibles que se encuentran tal que no es mayor o igual a en la celosía.
Esta representación de cualquier retículo distributivo de unión finito como una familia accesible de conjuntos cerrados bajo uniones (es decir, como un antimatroide) puede verse como un análogo del teorema de representación de Birkhoff bajo el cual cualquier retículo distributivo finito tiene una representación como una familia de conjuntos. cerrado bajo sindicatos e intersecciones.
Antimatroides supersolubles
Motivado por el problema de definir órdenes parciales en los elementos de un grupo Coxeter , Armstrong (2009) estudió los antimatroides que también son rejillas supersolubles. Un antimatroide supersoluble se define por una colección de elementos totalmente ordenada y una familia de conjuntos de estos elementos. La familia debe incluir el conjunto vacío. Además, debe tener la propiedad de que si dos conjuntos y pertenecen a la familia, la diferencia de la teoría de conjuntos no está vacío, y es el elemento más pequeño de , luego también pertenece a la familia. Como observa Armstrong, cualquier familia de conjuntos de este tipo forma un antimatroide. Armstrong también proporciona una caracterización teórica en celosía de los antimatroides que puede formar esta construcción. [24]
Unir operación y dimensión convexa
Si y son dos antimatroides, ambos descritos como una familia de conjuntos sobre el mismo universo de elementos, podemos formar otro antimatroide, la unión de y , como sigue:
Las uniones están estrechamente relacionadas con una operación de cierre que asigna lenguajes formales a antimatroides, donde el cierre de un lenguaje es la intersección de todos los antimatroides que contienen como un sublenguaje. Este cierre tiene como conjuntos factibles las uniones de prefijos de cadenas en. En términos de esta operación de cierre, la unión es el cierre de la unión de las lenguas de y . Cada antimatroide puede representarse como una unión de una familia de antimatroides en cadena, o lo que es lo mismo, como el cierre de un conjunto de palabras básicas; la dimensión convexa de un antimatroidees el número mínimo de antimatroides en cadena (o equivalentemente, el número mínimo de palabras básicas) en dicha representación. Si es una familia de antimatroides en cadena cuyas palabras básicas pertenecen todas a , luego genera si y solo si los conjuntos factibles de incluir todos los caminos de . Los caminos depertenecientes a un antimatroide monocatenario debe formar una cadena en el camino poset de, por lo que la dimensión convexa de un antimatroide es igual al número mínimo de cadenas necesarias para cubrir la ruta poset, que según el teorema de Dilworth es igual al ancho de la ruta poset. [26]
Si uno tiene una representación de un antimatroide como el cierre de un conjunto de palabras básicas, entonces esta representación se puede utilizar para mapear los conjuntos factibles del antimatroide a puntos en -espacio euclidiano dimensional: asigna una coordenada por palabra básica y hacer que el valor de las coordenadas de un conjunto factible ser la longitud del prefijo más largo de que es un subconjunto de . Con esta incrustación, es un subconjunto de otro conjunto factible si y solo si las coordenadas para son todos menores o iguales a las coordenadas correspondientes de . Por lo tanto, la dimensión de orden de la ordenación de inclusión de los conjuntos factibles es como máximo igual a la dimensión convexa del antimatroide. [27] Sin embargo, en general estas dos dimensiones pueden ser muy diferentes: existen antimatroides con una dimensión de orden tres pero con una dimensión convexa arbitrariamente grande. [28]
Enumeración
El número de posibles antimatroides en un conjunto de elementos crece rápidamente con el número de elementos del conjunto. Para conjuntos de uno, dos, tres, etc. elementos, el número de antimatroides distintos es [29]
Aplicaciones
Tanto las restricciones de tiempo de precedencia como de liberación en la notación estándar para problemas de programación teóricos pueden ser modeladas por antimatroides. Boyd y Faigle (1990) usan antimatroides para generalizar un algoritmo codicioso de Eugene Lawler para resolver de manera óptima problemas de programación de un solo procesador con restricciones de precedencia en las que el objetivo es minimizar la penalización máxima incurrida por la programación tardía de una tarea.
Glasserman y Yao (1994) utilizan antimatroides para modelar el orden de los eventos en sistemas de simulación de eventos discretos .
Parmar (2003) utiliza antimatroides para modelar el progreso hacia una meta en problemas de planificación de inteligencia artificial .
En la teoría de la optimización , un modelo matemático para el desarrollo del lenguaje natural basado en la optimización bajo restricciones, las gramáticas son lógicamente equivalentes a los antimatroides. [30]
En psicología matemática , los antimatroides se han utilizado para describir estados factibles de conocimiento de un aprendiz humano. Cada elemento del antimatroide representa un concepto que debe ser entendido por el alumno, o una clase de problemas que él o ella podría resolver correctamente, y los conjuntos de elementos que forman el antimatroide representan posibles conjuntos de conceptos que podrían ser entendido por una sola persona. Los axiomas que definen un antimatroide pueden expresarse informalmente como afirmar que el aprendizaje de un concepto nunca puede impedir que el alumno aprenda otro concepto, y que se puede alcanzar cualquier estado de conocimiento factible aprendiendo un solo concepto a la vez. La tarea de un sistema de evaluación del conocimiento es inferir el conjunto de conceptos conocidos por un alumno determinado mediante el análisis de sus respuestas a un conjunto de problemas pequeños y bien elegidos. En este contexto, los antimatroides también se han denominado "espacios de aprendizaje" y "espacios de conocimiento bien graduados". [31]
Notas
- ^ Ver Korte, Lovász & Schrader (1991) para una revisión completa de la teoría antimatroide con muchas referencias adicionales.
- ↑ Dos referencias tempranas son Edelman (1980) y Jamison (1980) ; Jamison fue el primero en utilizar el término "antimatroide". Monjardet (1985) examina la historia del redescubrimiento de los antimatroides.
- ^ Véase, por ejemplo, Kempner y Levit (2003) , Definición 2.1 y Proposición 2.3, p. 2.
- ^ Korte, Lovász y Schrader (1991) , p. 22.
- ↑ a b Korte, Lovász y Schrader (1991) , p. 5.
- ^ Korte, Lovász y Schrader (1991) , Teorema 1.4, p. 24.
- ↑ a b c Gordon (1997) .
- ^ Korte, Lovász y Schrader (1991) , págs. 24-25.
- ^ Kashiwabara, Nakamura y Okamoto (2005) .
- ↑ Gordon (1997) describe varios resultados relacionados con los antimatroides de este tipo, pero estos antimatroides fueron mencionados anteriormente, por ejemplo, por Korte, Lovász & Schrader (1991) . Chandran y col. (2003) utilizan la conexión con los antimatroides como parte de un algoritmo para enumerar de manera eficiente todos los ordenamientos de eliminación perfectos de un gráfico de cuerdas dado.
- ^ Björner, Lovász y Shor (1991) ; Knauer (2009) .
- ↑ a b c Korte, Lovász y Schrader (1991) , Lema 3.12, p. 31.
- ^ Korte, Lovász y Schrader (1991) , p. 31.
- ^ Korte, Lovász y Schrader (1991) , págs. 39–43.
- ^ Véase Korte, Lovász y Schrader (1991) , Teorema 3.13, p. 32, que define los caminos como conjuntos arraigados , conjuntos con un elemento distinguido y establece una caracterización equivalente de las familias de conjuntos arraigados que forman los caminos de los antimatroides.
- ^ Korte, Lovász y Schrader (1991) , págs.6, 22.
- ^ Véase Korte, Lovász y Schrader (1991) , p. 22: "cualquier palabra en un antimatroide puede extenderse a una palabra básica".
- ↑ a b Korte, Lovász y Schrader (1991) , Teorema 1.1, p. 21.
- ↑ a b Korte, Lovász y Schrader (1991) , p. 20.
- ^ Farber y Jamison (1986) .
- ^ Adaricheva, Gorbunov y Tumanov (2003) , Teoremas 1.7 y 1.9; Armstrong (2009) , Teorema 2.7.
- ^ Edelman (1980) , Teorema 3.3; Armstrong (2009) , Teorema 2.8.
- ↑ Monjardet (1985) atribuye una forma dual de esta caracterización a varios artículos de la década de 1960 de SP Avann.
- ^ Armstrong (2009) .
- ^ Korte, Lovász y Schrader (1991) , p. 42; Eppstein (2008) , sección 7.2; Falmagne y col. (2013) , sección 14.4.
- ^ Edelman y Saks (1988) ; Korte, Lovász y Schrader (1991) , Teorema 6.9.
- ^ Korte, Lovász y Schrader (1991) , Corolario 6.10.
- ^ Eppstein (2008) , figura 15.
- ^ Sloane, N. J. A. (ed.), "Secuencia A119770" , La enciclopedia en línea de secuencias de enteros , Fundación OEIS
- ↑ Merchant & Riggle (2016) .
- ^ Doignon y Falmagne (1999) .
Referencias
- Adaricheva, KV; Gorbunov, VA; Tumanov, VI (2003), "Juntas-celosías semidistributivas y geometrías convexas", Advances in Mathematics , 173 (1): 1-49, doi : 10.1016 / S0001-8708 (02) 00011-7.
- Armstrong, Drew (2009), "El orden de clasificación en un grupo Coxeter", Journal of Combinatorial Theory, Serie A , 116 (8): 1285–1305, arXiv : 0712.1047 , doi : 10.1016 / j.jcta.2009.03.009 , Señor 2568800 , S2CID 15474840.
- Birkhoff, Garrett ; Bennett, MK (1985), "La celosía de convexidad de un poset" , Orden , 2 (3): 223–242, doi : 10.1007 / BF00333128 (inactivo 31 de mayo de 2021)Mantenimiento de CS1: DOI inactivo a partir de mayo de 2021 ( enlace )
- Björner, Anders ; Lovász, László ; Shor, Peter W. (1991), "Juegos de disparar fichas en gráficos", European Journal of Combinatorics , 12 (4): 283-291, doi : 10.1016 / S0195-6698 (13) 80111-4 , MR 1120415
- Björner, Anders ; Ziegler, Günter M. (1992), "Introduction to greedoids" , en White, Neil (ed.), Matroid Applications , Encyclopedia of Mathematics and its Applications, 40 , Cambridge: Cambridge University Press, págs. 284–357 , doi : 10.1017 / CBO9780511662041.009 , ISBN 0-521-38165-7, MR 1165537
- Boyd, E. Andrew; Faigle, Ulrich (1990), "Una caracterización algorítmica de antimatroides", Matemáticas aplicadas discretas , 28 (3): 197-205, doi : 10.1016 / 0166-218X (90) 90002-T , hdl : 1911/101636.
- Chandran, LS; Ibarra, L .; Ruskey, F .; Sawada, J. (2003), "Generación y caracterización de los ordenamientos de eliminación perfectos de un grafo cordal" (PDF) , Informática teórica , 307 (2): 303–317, doi : 10.1016 / S0304-3975 (03) 00221- 4
- Dilworth, Robert P. (1940), "Celosías con descomposiciones irreductibles únicas", Annals of Mathematics , 41 (4): 771–777, doi : 10.2307 / 1968857 , JSTOR 1968857.
- Doignon, Jean-Paul; Falmagne, Jean-Claude (1999), Espacios de conocimiento , Springer-Verlag, ISBN 3-540-64501-2.
- Edelman, Paul H. (1980), "Meet-distributive lattices y el cierre anti-exchange", Algebra Universalis , 10 (1): 290–299, doi : 10.1007 / BF02482912 , S2CID 120403229.
- Edelman, Paul H .; Saks, Michael E. (1988), "Representación combinatoria y dimensión convexa de geometrías convexas", Orden , 5 (1): 23–32, doi : 10.1007 / BF00143895 , S2CID 119826035.
- Eppstein, David (2008), Secuencias de aprendizaje , arXiv : 0803.4030. Parcialmente adaptado como capítulos 13 y 14 de Falmagne, Jean-Claude ; Albert, Dietrich; Doble, Chris; Eppstein, David ; Hu, Xiangen, eds. (2013), Espacios de conocimiento: aplicaciones en educación , Springer-Verlag, doi : 10.1007 / 978-3-642-35329-1 , ISBN 978-3-642-35328-4.
- Farber, Martin; Jamison, Robert E. (1986), "Convexidad en gráficos e hipergráficos", SIAM Journal on Algebraic and Discrete Methods , 7 (3): 433–444, doi : 10.1137 / 0607049 , hdl : 10338.dmlcz / 127659 , MR 0844046.
- Glasserman, Paul; Yao, David D. (1994), Estructura monótona en sistemas de eventos discretos , Serie Wiley en Probabilidad y estadística, Wiley Interscience, ISBN 978-0-471-58041-6.
- Gordon, Gary (1997), "Un invariante β para greedoides y antimatroides", Electronic Journal of Combinatorics , 4 (1): artículo de investigación 13, doi : 10.37236 / 1298 , MR 1445628.
- Jamison, Robert (1980), "Copoints en antimatroides", Actas de la undécima Conferencia del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Florida Atlantic Univ., Boca Raton, Fla., 1980), vol. II , Congressus Numerantium, 29 , págs. 535–544, MR 0608454.
- Kashiwabara, Kenji; Nakamura, Masataka; Okamoto, Yoshio (2005), "El teorema de representación afín para geometrías convexas abstractas", Geometría computacional , 30 (2): 129-144, CiteSeerX 10.1.1.14.4965 , doi : 10.1016 / j.comgeo.2004.05.001 , MR 2107032.
- Kempner, Yulia; Levit, Vadim E. (2003), "Correspondencia entre dos caracterizaciones algorítmicas antimatroides" , Electronic Journal of Combinatorics , 10 : Research Paper 44, arXiv : math / 0307013 , Bibcode : 2003math ...... 7013K , doi : 10.37236 / 1737 , MR 2.014.531 , S2CID 11015967
- Knauer, Kolja (2009), "Disparo de chips, antimatroides y poliedros", Conferencia europea sobre combinatoria, teoría de grafos y aplicaciones (EuroComb 2009) , Electronic Notes in Discrete Mathematics, 34 , págs. 9-13, doi : 10.1016 / j.endm.2009.07.002 , MR 2591410
- Korte, Bernhard ; Lovász, László ; Schrader, Rainer (1991), Greedoids , Springer-Verlag, págs. 19–43, ISBN 3-540-18190-3.
- Comerciante, Nazarré; Riggle, Jason (2016), "Gramáticas OT, más allá de los órdenes parciales: conjuntos ERC y antimatroides" , Natural Language & Linguistic Theory , 34 : 241–269, doi : 10.1007 / s11049-015-9297-5 , S2CID 170567540.
- Monjardet, Bernard (1985), "Un uso para redescubrir un concepto con frecuencia", Orden , 1 (4): 415–417, doi : 10.1007 / BF00582748 , S2CID 119378521.
- Parmar, Aarati (2003), "Algunas estructuras matemáticas subyacentes a la planificación eficiente", Simposio de primavera de AAAI sobre formalización lógica del razonamiento con sentido común (PDF).