¿Para qué se utilizan las celosías?

Wikipedia dice :

Las redes completas aparecen en muchas aplicaciones en matemáticas y ciencias de la computación.

¿Se refiere solo al hecho de que el álgebra booleana estándar utilizada en el cálculo es una red completa? ¿Hay algo que ganemos al trabajar en el nivel abstracto de celosías en lugar de específicamente con la lógica booleana?

Una búsqueda en Google no encuentra mucho sobre el tema, pero probablemente estoy usando las palabras clave incorrectas.

Vea, por ejemplo, este libro: Lattice Theory with Applications, Vijay K. Garg , que comienza de la siguiente manera:

El orden parcial y la teoría de la red ahora juegan un papel importante en muchas disciplinas de la informática y la ingeniería. Por ejemplo, tienen aplicaciones en computación distribuida (relojes vectoriales, detección de predicados globales), teoría de concurrencia (pomsets, redes de ocurrencia), semántica de lenguaje de programación (semántica de punto fijo) y minería de datos (análisis de concepto). También son útiles en otras disciplinas de las matemáticas, como la combinatoria, la teoría de números y la teoría de grupos. En este libro, presento resultados importantes en la teoría del orden parcial junto con sus aplicaciones en informática. El sesgo del libro está en los aspectos computacionales de la teoría de la red (algoritmos) y en las aplicaciones (especialmente los sistemas distribuidos).

El libro no parece mencionar la teoría de la recursión (teoría de conjuntos computables), pero del artículo de Wikipedia sobre teoría de la computabilidad , vemos:

Cuando Post definió la noción de un conjunto simple como un conjunto con un complemento infinito que no contiene ningún conjunto infinito, comenzó a estudiar la estructura de los conjuntos enumerables recursivamente bajo inclusión. Este enrejado se convirtió en una estructura bien estudiada. Los conjuntos recursivos se pueden definir en esta estructura por el resultado básico de que un conjunto es recursivo si y solo si el conjunto y su complemento son enumerables recursivamente. Los reinicios infinitos siempre tienen subconjuntos recursivos infinitos; pero, por otro lado, existen conjuntos simples pero no tienen un superconjunto recursivo coinfinito. Post (1944) introdujo conjuntos ya hiperesimple e hiperhiperesimple; se construyeron conjuntos máximos posteriores que son conjuntos re de manera tal que cada superconjunto re es una variante finita del conjunto máximo dado o es co-finito. Enviar' La motivación original en el estudio de esta red era encontrar una noción estructural tal que cada conjunto que satisfaga esta propiedad no esté ni en el grado de Turing de los conjuntos recursivos ni en el grado de Turing del problema de detención. Post no encontró tal propiedad y la solución a su problema aplicó métodos de prioridad en su lugar; Harrington y Soare (1991) encontraron eventualmente tal propiedad.

Para leer más, vea la publicación del blog Teoría del enrejado para programadores y no informáticos .

Las referencias dadas por Pål GD son de hecho muy apropiadas. Por lo tanto, centrémonos en un problema secundario menor en esta respuesta. Hace un tiempo leí algo sobre redes y comencé a preguntarme si la noción de red no habría sido más apropiada para las aplicaciones. Puede objetar que una semi-red completa también es automáticamente una red, pero los homomorfismos y las subestructuras (es decir, subredes y subsemilattices) son diferentes.

La primera vez que encontré (semi) retículos cuando estudiaba semigrupos, como los semigrupos conmutativos idempotentes. Entonces pensé en la relación entre las estructuras jerárquicas y las celosías, y noté que un árbol es naturalmente también una semilattice. Luego encontré celosías en contextos de seguridad y en análisis de programas, y siempre me pareció que la estructura de la celosía era la parte realmente importante, y la celosía se tomó simplemente porque se podía obtener "gratis". Incluso para un álgebra de Heyting, hay una asimetría entre la conjunción y la disyunción que me sugiere que el modelo asimétrico de semilattice podría proporcionar más información aquí que el modelo de red simétrica.

Un caso muy importante, pero no tan famoso —es bien conocido entre los teóricos, pero no tan conocido en el sentido de que se les enseñe a los estudiantes universitarios—, el uso de una red es probar límites inferiores superpolinomiales en el tamaño de los circuitos monótonos. camarilla informática por la que Razborov ganó el premio Nevanlinna . Sin embargo, la construcción original es muy técnica y las construcciones posteriores, por ejemplo Berg / Ulfberg, simplifican el marco sin hacer referencia a las celosías.

En este caso, la teoría de la red se utilizó como marco para descubrir la prueba original, pero las formulaciones posteriores tendieron a no referirse directamente a ella como una simplificación conceptual.

entonces sí, las redes pueden considerarse como un objeto matemático más exótico [Razborov ha hablado en otra parte de su estilo de aplicar matemáticas avanzadas a CS] que podría corresponder a algún otro objeto más "concreto" en CS, en este caso son "puertas de aproximación" es decir, puertas booleanas en circuitos que dan respuestas "aproximadamente correctas" y que la red es una especie de "estructura de inducción" para convertir entre un circuito exacto en un circuito aproximado inexacto.

Desde entonces, encontré los juegos gratuitos en papel Ordered Sets and Complete Lattices: A Primer for Computer Science , para otros lectores interesados.

Las etiquetas de borde regulares y las estructuras relacionadas forman una red distributiva (ver, por ejemplo, aquí ). Esto puede explotarse para buscar eficientemente en el espacio de todas las etiquetas de borde regulares para un gráfico dado (ver aquí ). Como aplicación, puede determinar si se puede dibujar un mapa como cartograma con una determinada asignación de área para las caras.

Además, sorprendentemente (para mí, al menos) criptografía . Compruébalo, permite nuevos ataques de sistemas criptográficos conocidos y da esperanzas para la criptografía de computación post-cuántica.