Antimatroide

En matemáticas , un antimatroide es un sistema formal que describe procesos en los que se construye un conjunto incluyendo elementos de uno en uno, y en el que un elemento, una vez disponible para su inclusión, permanece disponible hasta que se lo 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 retículos , y se han redescubierto 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 de antiintercambio , de donde deriva su nombre. Los antimatroides pueden considerarse un caso especial de los greedoides y de los retículos semimodulares , y como una generalización de los órdenes parciales y de los retículos distributivos . Los antimatroides son equivalentes, por complementación , a las geometrías convexas , una abstracción combinatoria de los conjuntos convexos en geometría .

Los antimatroides se han aplicado para modelar restricciones de precedencia en problemas de programación , secuencias de eventos potenciales en simulaciones, planificación de tareas en inteligencia artificial y los estados de conocimiento de los estudiantes humanos.

Definiciones

Un antimatroide puede definirse como una familia finita de conjuntos finitos, llamados conjuntos factibles , con las dos propiedades siguientes: ^[3] ${\mathcal {F}}$

La unión de dos conjuntos factibles cualesquiera también es factible, es decir, es cerrada bajo uniones. ${\mathcal {F}}$
Si es un conjunto factible no vacío, entonces contiene un elemento para el cual (el conjunto formado al eliminar de ) también es factible. Es decir, es un sistema de conjuntos accesible . ${\estilo de visualización S}$ ${\estilo de visualización S}$ ${\estilo de visualización x}$ $S\setminus \{x\}$ ${\estilo de visualización x}$ ${\estilo de visualización S}$ ${\mathcal {F}}$

Los antimatroides también tienen una definición equivalente como 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 denomina palabra del lenguaje. Un lenguaje que define un antimatroide debe satisfacer las siguientes propiedades: ^[4] ${\mathcal {L}}$

Cada símbolo del alfabeto aparece en al menos una palabra de . ${\mathcal {L}}$
Cada palabra de contiene como máximo una copia de cada símbolo. Un lenguaje con esta propiedad se denomina normal . ^[5] ${\mathcal {L}}$
Cada prefijo de una palabra en también está en . Una lengua con esta propiedad se llama hereditaria . ^[5] ${\mathcal {L}}$ ${\mathcal {L}}$
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 . ${\estilo de visualización S}$ ${\estilo de visualización T}$ ${\mathcal {L}}$ ${\estilo de visualización S}$ ${\estilo de visualización T}$ ${\estilo de visualización x}$ ${\estilo de visualización S}$ ${\estilo de visualización Tx}$ ${\mathcal {L}}$

La equivalencia de estas dos formas de definición se puede ver de la siguiente manera. Si se define un antimatroide como un lenguaje formal, entonces los conjuntos de símbolos en palabras de forman un sistema de conjuntos accesible de unión cerrada. Es accesible por la propiedad hereditaria de las cadenas, y se puede demostrar que es de unión cerrada mediante la aplicación repetida de la propiedad de concatenación de las cadenas. En la otra dirección, desde un sistema de conjuntos accesible de unión cerrada , el lenguaje de cadenas normales cuyos prefijos tienen todos conjuntos de símbolos que pertenecen a cumple los requisitos para que un lenguaje formal sea un antimatroide. Estas dos transformaciones son inversas entre sí: transformar un lenguaje formal en una familia de conjuntos y viceversa, o viceversa, produce el mismo sistema. Por lo tanto, estas dos definiciones conducen a clases de objetos matemáticamente equivalentes. ^[6] ${\mathcal {L}}$ ${\mathcal {L}}$ ${\mathcal {F}}$ ${\mathcal {F}}$

Ejemplos

Los siguientes sistemas proporcionan ejemplos de antimatroides:

Antimatroides en cadena: Los prefijos de una sola cadena y los conjuntos de símbolos en estos prefijos forman un antimatroide. Por ejemplo, el antimatroide de cadena definido por la cadena tiene como lenguaje formal el conjunto de cadenas (donde denota la cadena vacía ) y como su familia de conjuntos factibles la familia ^[7] ${\estilo de visualización abcd}$ $\{\varepsilon ,a,ab,abc,abcd\}$ ${\estilo de visualización \varepsilon}$ ${\bigl \{}\conjunto vacío,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}{\bigr \}}.$
Antimatroides Poset: Los conjuntos inferiores de un conjunto finito parcialmente ordenado forman un antimatroide, con las palabras de longitud completa del antimatroide formando las extensiones lineales del orden parcial. ^[8] Por el teorema de representación de Birkhoff para redes distributivas, los conjuntos factibles en un antimatroide de conjunto parcial (ordenado por inclusión de conjuntos) forman una red distributiva, y todas las redes 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 de conjunto parcial para un orden total . ^[7]
Bombardeo de antimatroides: Una secuencia de capas de un conjunto finito de puntos en el plano euclidiano o en un espacio euclidiano de dimensiones superiores se forma eliminando repetidamente vértices de la envoltura convexa . Los conjuntos factibles del antimatroide formado por estas secuencias son las intersecciones de con el complemento de un conjunto convexo. ^[7] ${\estilo de visualización U}$ ${\estilo de visualización U}$
Eliminación perfecta: Un ordenamiento de eliminación perfecto de un grafo cordal es un ordenamiento de sus vértices tal que, para cada vértice , los vecinos de que aparecen más tarde que en el ordenamiento forman una camarilla . Los prefijos de los ordenamientos de eliminación perfectos de un grafo cordal forman un antimatroide. ^[9] ${\estilo de visualización v}$ ${\estilo de visualización v}$ ${\estilo de visualización v}$
Juegos de disparos de chips: Los juegos de disparo de fichas, como el modelo de pila de arena abeliano, se definen mediante un grafo dirigido junto con un sistema de "fichas" colocadas en sus vértices. Siempre que el número de fichas en un vértice sea al menos tan grande como el número de aristas que salen de , es posible disparar , moviendo una ficha a cada vértice vecino. El evento que dispara por ésima vez solo puede ocurrir si ya ha disparado veces y ha acumulado fichas totales. Estas condiciones no dependen del orden de disparos anteriores y siguen siendo verdaderas hasta que se dispara, por lo que cualquier grafo dado y ubicación inicial de fichas para las que el sistema termina 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 estado estable final del sistema no dependen del orden de disparo. ^[10] ${\estilo de visualización v}$ ${\estilo de visualización v}$ ${\estilo de visualización v}$ ${\estilo de visualización v}$ ${\estilo de visualización i}$ ${\estilo de visualización i-1}$ $i\cdot \deg(v)$ ${\estilo de visualización v}$ ${\estilo de visualización (v,i)}$

Caminos y palabras básicas

En la axiomatización de la teoría de conjuntos de un antimatroide hay ciertos conjuntos especiales llamados caminos que determinan todo el antimatroide, en el sentido de que los conjuntos del antimatroide son exactamente las uniones de caminos. ^[11] Si es cualquier conjunto factible del antimatroide, un elemento que puede eliminarse de para formar otro conjunto factible se llama punto final de , y un conjunto factible que tiene solo un punto final se llama camino del antimatroide. ^[12] La familia de caminos se puede ordenar parcialmente por inclusión de conjuntos, formando el conjunto de caminos del antimatroide. ^[13] ${\estilo de visualización S}$ ${\estilo de visualización x}$ ${\estilo de visualización S}$ ${\estilo de visualización S}$

Para cada conjunto factible en el antimatroide, y cada elemento de , se puede encontrar un subconjunto de caminos de para el cual es un punto final: para ello, se eliminan de a uno por vez los elementos distintos de 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. ^[11] Si no es un camino, cada subconjunto en esta unión es un subconjunto propio de . Pero, si es en sí mismo un camino con punto final , cada subconjunto propio de que pertenece al antimatroide excluye a . Por lo tanto, los caminos de un antimatroide son exactamente los conjuntos factibles que no son iguales a las uniones de sus subconjuntos factibles propios. 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 ella misma. ^[14] Si es así, ella misma es la familia de uniones de subconjuntos de . ^[11] ${\estilo de visualización S}$ ${\estilo de visualización x}$ ${\estilo de visualización S}$ ${\estilo de visualización S}$ ${\estilo de visualización x}$ ${\estilo de visualización x}$ ${\estilo de visualización S}$ ${\estilo de visualización S}$ ${\estilo de visualización S}$ ${\estilo de visualización x}$ ${\estilo de visualización S}$ ${\estilo de visualización x}$ ${\mathcal {P}}$ ${\estilo de visualización S}$ ${\mathcal {P}}$ ${\estilo de visualización S}$ ${\mathcal {P}}$ ${\estilo de visualización S}$ ${\mathcal {F}}$ ${\mathcal {P}}$

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. ^[15] Si es el conjunto de palabras básicas, se puede definir a partir de como el conjunto de prefijos de palabras en . ^[16] ${\estilo de visualización B}$ ${\mathcal {L}}$ ${\estilo de visualización B}$ ${\estilo de visualización B}$

Geometrías convexas

Si es el sistema de conjuntos que define un antimatroide, con igual a la unión de los conjuntos en , entonces la familia de conjuntos complementarios a los conjuntos en a veces se denomina geometría convexa y los conjuntos en se denominan conjuntos convexos . Por ejemplo, en un antimatroide de descascarado, los conjuntos convexos son intersecciones del conjunto de puntos dado con subconjuntos convexos del espacio euclidiano. El sistema de conjuntos que define una geometría convexa debe estar cerrado bajo intersecciones. Para cualquier conjunto en que no sea igual a debe haber un elemento que no esté en que pueda sumarse a para formar otro conjunto en . ^[17] ${\mathcal {F}}$ ${\estilo de visualización U}$ ${\mathcal {F}}$ ${\mathcal {G}}=\{U\setminus S\mid S\in {\mathcal {F}}\}$ ${\mathcal {F}}$ ${\mathcal {G}}$ ${\estilo de visualización S}$ ${\mathcal {G}}$ ${\estilo de visualización U}$ ${\estilo de visualización x}$ ${\estilo de visualización S}$ ${\estilo de visualización S}$ ${\mathcal {G}}$

Una geometría convexa también se puede definir en términos de un operador de cierre que asigna cualquier subconjunto de a su superconjunto cerrado mínimo. Para ser un operador de cierre, debe tener las siguientes propiedades: ^[18] ${\estilo de visualización \tau}$ ${\estilo de visualización U}$ ${\estilo de visualización \tau}$

$\tau (\conjunto vacío )=\conjunto vacío$ :el cierre del conjunto vacío es vacío.
Para cada subconjunto de , es un subconjunto de y . ${\estilo de visualización S}$ ${\estilo de visualización U}$ ${\estilo de visualización S}$ $\tau (S)$ $\tau (S)=\tau {\bigl (}\tau (S){\bigr )}$
Siempre que , es un subconjunto de . $S\subset T\subset U$ $\tau (S)$ $\tau (T)$

La familia de conjuntos cerrados resultante de una operación de clausura de este tipo es necesariamente cerrada bajo intersecciones, pero podría no ser una geometría convexa. Los operadores de clausura que definen geometrías convexas también satisfacen un axioma antiintercambio adicional :

Si es un subconjunto de , y y son elementos distintos de que no pertenecen a , pero sí pertenecen a , entonces no pertenece a . ^[18] $S$ $U$ $y$ $z$ $U$ $\tau (S)$ $z$ $\tau (S\cup \{y\})$ $y$ $\tau (S\cup \{z\})$

Una operación de clausura que satisface este axioma se denomina clausura antiintercambio . Si es un conjunto cerrado en una clausura antiintercambio, entonces el axioma antiintercambio determina un orden parcial sobre los elementos que no pertenecen a , donde en el orden parcial cuando pertenece a . Si es un elemento mínimo de este orden parcial, entonces es cerrada. Es decir, la familia de conjuntos cerrados de una clausura antiintercambio tiene la propiedad de que para cualquier conjunto distinto del conjunto universal hay un elemento que se le puede añadir 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 cerradas es complementario a la propiedad de que las uniones de conjuntos factibles en un antimatroide son factibles. Por lo tanto, los complementos de los conjuntos cerrados de cualquier clausura antiintercambio forman un antimatroide. ^[17] $S$ $S$ $x\leq y$ $x$ $\tau (S\cup \{y\})$ $x$ $S\cup \{x\}$ $x$

Los grafos 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 grafos ptolemaicos . ^[19]

Redes de unión-distributivas

Cada dos conjuntos factibles de un antimatroide tienen un único límite superior mínimo (su unión) y un único límite inferior máximo (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 pueden interpretarse en términos de teoría de redes; por ejemplo, los caminos de un antimatroide son los elementos irreducibles de unión de la red correspondiente, y las palabras básicas del antimatroide corresponden a cadenas máximas en la red. Las redes que surgen de los antimatroides de esta manera generalizan las redes distributivas finitas , y pueden caracterizarse de varias formas diferentes.

La descripción considerada originalmente por Dilworth (1940) se refiere a los elementos irreducibles de encuentro de la red. Para cada elemento de un antimatroide, existe un único conjunto factible máximo que no contiene : puede construirse como la unión de todos los conjuntos factibles que no contienen . Este conjunto es automáticamente irreducible de encuentro, lo que significa que no es el encuentro de dos elementos mayores de la red. Esto es cierto porque cada superconjunto factible de contiene , y lo mismo es, por tanto, cierto también para cada intersección de superconjuntos factibles. Cada elemento de una red arbitraria puede descomponerse como un encuentro de conjuntos irreducibles de encuentro, a menudo de múltiples maneras, pero en la red correspondiente a un antimatroide cada elemento tiene una familia mínima única de conjuntos irreducibles de encuentro cuyo encuentro es ; esta familia consta de los conjuntos para los elementos tales que es factible. Es decir, la red tiene descomposiciones irreducibles de encuentro únicas . $x$ $S_{x}$ $x$ $S_{x}$ $x$ $S_{x}$ $S_{x}$ $x$ $T$ $T$ $S_{x}$ $x$ $T\cup \{x\}$
Una segunda caracterización se refiere a los intervalos en la red, las subredes definidas por un par de elementos de la red que consisten en todos los elementos de la red con . Un intervalo es atomístico si cada elemento en él es la unión de átomos (los elementos mínimos por encima del elemento inferior ), y es booleano si es isomorfo a la red de todos los subconjuntos de un conjunto finito. Para un antimatroide, cada intervalo que es atomístico también es booleano. $x\leq y$ $z$ $x\leq z\leq y$ $x$
En tercer lugar, las redes que surgen de los antimatroides son redes semimodulares , redes que satisfacen la ley semimodular superior que para cada dos elementos y , si cubre entonces cubre . Traduciendo esta condición a los conjuntos factibles de un antimatroide, si 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 red de un antimatroide tiene la propiedad semidistributiva de encuentro : para todos los elementos de la red , , y , si y son iguales entre sí, entonces también son iguales a . Una red semimodular y semidistributiva de encuentro se llama red distributiva de unión . $x$ $y$ $y$ $x\wedge y$ $x\vee y$ $x$ $Y$ $X$ $X$ $x$ $y$ $z$ $x\wedge y$ $x\wedge z$ $x\wedge (y\vee z)$

Estas tres caracterizaciones son equivalentes: cualquier red con descomposiciones irreducibles de encuentro únicas tiene intervalos atomísticos booleanos y es distributiva de unión, cualquier red con intervalos atomísticos booleanos tiene descomposiciones irreducibles de encuentro únicas y es distributiva de unión, y cualquier red distributiva de unión tiene descomposiciones irreducibles de encuentro únicas e intervalos atomísticos booleanos. ^[20] Por lo tanto, podemos referirnos a una red con cualquiera de estas tres propiedades como distributiva de unión. Cualquier antimatroide da lugar a una red distributiva de unión finita, y cualquier red distributiva de unión finita proviene de un antimatroide de esta manera. ^[21] Otra caracterización equivalente de las redes distributivas de unión finitas es que están graduadas (cualquiera dos cadenas maximal tienen la misma longitud), y la longitud de una cadena maximal es igual al número de elementos irreducibles de encuentro de la red. ^[22] El antimatroide que representa una red distributiva de unión finita se puede recuperar de la red: los elementos del antimatroide se pueden tomar como los elementos irreducibles de encuentro de la red, y el conjunto factible correspondiente a cualquier elemento de la red consiste en el conjunto de elementos irreducibles de encuentro tales que no es mayor o igual a en la red. $x$ $y$ $y$ $x$

Esta representación de cualquier red distributiva-unión finita 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 según el cual cualquier red distributiva finita tiene una representación como una familia de conjuntos cerrados bajo uniones e intersecciones.

Antimatroides supersolubles

Motivado por un problema de definición de órdenes parciales en los elementos de un grupo de Coxeter , Armstrong (2009) estudió antimatroides que también son redes supersolubles . Un antimatroide supersoluble se define por una colección totalmente ordenada de elementos 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, si la diferencia de teoría de conjuntos no es vacía, y si es el elemento más pequeño de , entonces 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 de teoría de redes de los antimatroides que esta construcción puede formar. ^[23] $A$ $B$ $B\setminus A$ $x$ $B\setminus A$ $A\cup \{x\}$

Operación de unión y dimensión convexa

Si y son dos antimatroides, ambos descritos como una familia de conjuntos sobre el mismo universo de elementos, entonces otro antimatroides, la unión de y , se puede formar de la siguiente manera: Esta es una operación diferente a la unión considerada en las caracterizaciones de teoría reticular de antimatroides: combina dos antimatroides para formar otro antimatroides, en lugar de combinar dos conjuntos en un antimatroides para formar otro conjunto. La familia de todos los antimatroides sobre el mismo universo forma una semirretícula con esta operación de unión. ^[24] ${\mathcal {A}}$ ${\mathcal {B}}$ ${\mathcal {A}}$ ${\mathcal {B}}$ ${\mathcal {A}}\vee {\mathcal {B}}=\{S\cup T\mid S\in {\mathcal {A}}\wedge T\in {\mathcal {B}}\}.$

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 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 los lenguajes de y . Cada antimatroide se puede representar como una unión de una familia de antimatroides de cadena, o equivalentemente como el cierre de un conjunto de palabras básicas; la dimensión convexa de un antimatroide es el número mínimo de antimatroides de cadena (o equivalentemente el número mínimo de palabras básicas) en tal representación. Si es una familia de antimatroides de cadena cuyas palabras básicas pertenecen todas a , entonces genera si y solo si los conjuntos factibles de incluyen todos los caminos de . Los caminos de pertenencia a un antimatroide de cadena única deben formar una cadena en el conjunto de caminos de , por lo que la dimensión convexa de un antimatroide es igual al número mínimo de cadenas necesarias para cubrir el conjunto de caminos, que por el teorema de Dilworth es igual al ancho del conjunto de caminos. ^[25] ${\mathcal {L}}$ ${\mathcal {L}}$ ${\mathcal {L}}$ ${\mathcal {A}}$ ${\mathcal {B}}$ ${\mathcal {A}}$ ${\mathfrak {F}}$ ${\mathcal {A}}$ ${\mathfrak {F}}$ ${\mathcal {A}}$ ${\mathfrak {F}}$ ${\mathcal {A}}$ ${\mathcal {A}}$ ${\mathcal {A}}$

Si se tiene una representación de un antimatroide como el cierre de un conjunto de palabras básicas, entonces esta representación puede usarse para mapear los conjuntos factibles del antimatroide a puntos en el espacio euclidiano de dimensión -: asignar una coordenada por palabra básica , y hacer que el valor de la coordenada de un conjunto factible sea 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 todas menores o iguales que las coordenadas correspondientes de . Por lo tanto, la dimensión de orden del ordenamiento de inclusión de los conjuntos factibles es como máximo igual a la dimensión convexa del antimatroide. ^[26] Sin embargo, en general estas dos dimensiones pueden ser muy diferentes: existen antimatroides con dimensión de orden tres pero con dimensión convexa arbitrariamente grande. ^[27] $d$ $d$ $W$ $S$ $W$ $S$ $S$ $T$ $S$ $T$

Enumeración

El número de antimatroides posibles en un conjunto de elementos crece rápidamente con el número de elementos en el conjunto. Para conjuntos de uno, dos, tres, etc. elementos, el número de antimatroides distintos es ^[28] $1,3,22,485,59386,133059751,\dots \,.$

Aplicaciones

Tanto las restricciones de precedencia como las de tiempo de liberación en la notación estándar para problemas de programación teórica pueden modelarse mediante antimatroides. Boyd y Faigle (1990) utilizan antimatroides para generalizar un algoritmo voraz de Eugene Lawler para resolver de manera óptima problemas de programación de un solo procesador con restricciones de precedencia en los 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 eventos en sistemas de simulación de eventos discretos .

Parmar (2003) utiliza antimatroides para modelar el progreso hacia un objetivo en problemas de planificación de inteligencia artificial .

En la teoría de la optimalidad , 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. ^[29]

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 comprendido por el aprendiz, o una clase de problemas que él o ella podría ser capaz de resolver correctamente, y los conjuntos de elementos que forman el antimatroide representan posibles conjuntos de conceptos que podrían ser comprendidos por una sola persona. Los axiomas que definen un antimatroide pueden expresarse informalmente como afirmando que aprender un concepto nunca puede impedir que el aprendiz aprenda otro concepto, y que cualquier estado factible de conocimiento puede alcanzarse aprendiendo un solo concepto a la vez. La tarea de un sistema de evaluación de conocimientos es inferir el conjunto de conceptos conocidos por un aprendiz dado analizando sus respuestas a un conjunto pequeño y bien elegido de problemas. En este contexto, los antimatroides también se han llamado "espacios de aprendizaje" y "espacios de conocimiento bien graduados". ^[30]

Notas

^ Véase Korte, Lovász y Schrader (1991) para un estudio exhaustivo de la teoría antimatroide con muchas referencias adicionales.
^ Dos de las primeras referencias son Edelman (1980) y Jamison (1980); Jamison fue el primero en utilizar el término "antimatroides". Monjardet (1985) analiza 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ág. 2.
^ Korte, Lovász y Schrader (1991), pág. 22.
^ ab Korte, Lovász y Schrader (1991), pág. 5.
^ Korte, Lovász y Schrader (1991), Teorema 1.4, p. 24.
^abc Gordon (1997).
^ Korte, Lovász y Schrader (1991), págs. 24-25.
^ Gordon (1997) describe varios resultados relacionados con antimatroides de este tipo, pero estos antimatroides fueron mencionados anteriormente, por ejemplo, por Korte, Lovász y Schrader (1991). Chandran et al. (2003) utilizan la conexión con antimatroides como parte de un algoritmo para enumerar de manera eficiente todos los ordenamientos de eliminación perfecta de un grafo cordal dado.
^ Björner, Lovász y Shor (1991); Knauer (2009).
^ abc Korte, Lovász y Schrader (1991), Lema 3.12, p. 31.
^ Korte, Lovász y Schrader (1991), pág. 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 enraizados , conjuntos con un elemento distinguido, y establece una caracterización equivalente de las familias de conjuntos enraizados 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ág. 22: "cualquier palabra en un antimatroide puede extenderse a una palabra básica".
^ ab Korte, Lovász y Schrader (1991), Teorema 1.1, p. 21.
^ ab Korte, Lovász y Schrader (1991), pág. 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ág. 42; Eppstein (2008), sección 7.2; Falmagne et al. (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 números enteros , OEIS Foundation
^ Comerciante y Riggle (2016).
^ Doignon y Falmagne (1999).

Referencias

Adaricheva, KV; Gorbunov, VA; Tumanov, VI (2003), "Redes semidistributivas de unión 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 de Coxeter", Journal of Combinatorial Theory , Serie A, 116 (8): 1285–1305, arXiv : 0712.1047 , doi : 10.1016/j.jcta.2009.03.009 , MR 2568800, S2CID 15474840.
Birkhoff, Garrett ; Bennett, MK (1985), "La red de convexidad de un conjunto de elementos", Order , 2 (3): 223–242, doi :10.1007/BF00333128, S2CID 118907732
Björner, Anders ; Lovász, László ; Shor, Peter W. (1991), "Juegos de disparo de chips 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), "Introducción a los greedoids", en White, Neil (ed.), Matroid Applications , Enciclopedia de matemáticas y sus aplicaciones, vol. 40, Cambridge: Cambridge University Press, págs. 284–357, doi :10.1017/CBO9780511662041.009, ISBN 0-521-38165-7, Sr. 1165537
Boyd, E. Andrew; Faigle, Ulrich (1990), "Una caracterización algorítmica de antimatroides", Discrete Applied Mathematics , 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) , Theoretical Computer Science , 307 (2): 303–317, doi :10.1016/S0304-3975(03)00221-4
Dilworth, Robert P. (1940), "Redes con descomposiciones irreducibles ú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), "Redes de encuentro-distributivas y el cierre anti-intercambio", 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", Order , 5 (1): 23–32, doi :10.1007/BF00143895, S2CID 119826035.
Eppstein, David (2008), Secuencias de aprendizaje , arXiv : 0803.4030. Adaptado parcialmente 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 la 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 grafos e hipergrafos", 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): Documento de investigación 13, doi : 10.37236/1298 , MR 1445628.
Jamison, Robert (1980), "Copuntos en antimatroides", Actas de la Undécima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad Atlántica de Florida, Boca Ratón, Florida, 1980), Vol. II , Congressus Numerantium, vol. 29, págs. 535–544, MR 0608454.
Kempner, Yulia; Levit, Vadim E. (2003), "Correspondencia entre dos caracterizaciones algorítmicas antimatroides", Electronic Journal of Combinatorics , 10 : Documento de investigación 44, arXiv : math/0307013 , Bibcode :2003math......7013K, doi :10.37236/1737, MR 2014531, S2CID 11015967
Knauer, Kolja (2009), "Disparo de chips, antimatroides y poliedros", Conferencia europea sobre combinatoria, teoría de grafos y aplicaciones (EuroComb 2009) , Notas electrónicas sobre matemáticas discretas, vol. 34, págs. 9-13, doi :10.1016/j.endm.2009.07.002, MR 2591410
Korte, Bernhard ; Lovász, László ; Schrader, Rainer (1991), "Capítulo III: Convexidad abstracta - Antimatroides", Greedoids , Springer-Verlag, págs. 19–43, doi :10.1007/978-3-642-58191-5_3, ISBN 3-540-18190-3.
Merchant, Nazarré; Riggle, Jason (2016), "Gramáticas OT, más allá de ó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 con frecuencia un concepto", Order , 1 (4): 415–417, doi :10.1007/BF00582748, S2CID 119378521.
Parmar, Aarati (2003), "Algunas estructuras matemáticas que sustentan una planificación eficiente", Simposio de primavera de la AAAI sobre formalización lógica del razonamiento de sentido común (PDF).