¿Para qué se utilizan las celosías?

Question

Wikipedia dice:

Las redes completas aparecen en muchas aplicaciones en matemáticas e informática.

¿Se refiere simplemente al hecho de que el álgebra booleana estándar utilizada en computación es una red completa?¿Ganamos algo trabajando en el nivel abstracto de celosías en lugar de hacerlo 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.

Answer 1

Ver por ejemplo este libro: Teoría de la red con aplicaciones, 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 informática e ingeniería. Por ejemplo, tienen aplicaciones en computación distribuida (relojes vectoriales, detección de predicados globales), teoría de concurrencias (pomsets, redes de ocurrencia), semántica de lenguaje de programación (semántica de punto fijo) y minería de datos (análisis conceptual). 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, introdujo resultados importantes en la teoría de orden parcial junto con sus aplicaciones en informática. El sesgo del libro está en aspectos computacionales de la teoría de la red (algoritmos) y en aplicaciones (especialmente sistemas distribuidos).

El libro no parece mencionar la teoría de la recursión (teoría de conjuntos computables), sino 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 RE con un complemento infinito que no contiene ningún conjunto infinito RE, comenzó a estudiar la estructura de los conjuntos recursivamente enumerables bajo inclusión. Esta red 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 recursivamente enumerables. Los conjuntos de RE infinitos siempre tienen subconjuntos recursivos infinitos; Pero, por otro lado, existen conjuntos simples pero no tienen un superconjunto recursivo coinfinito. Post (1944) introdujo conjuntos de hipersimple e hiperhypersimple; Se construyeron conjuntos máximos posteriores que son conjuntos RE de tal manera que cada Superset de RE es una variante finita del conjunto máximo dado o es cofinito. La motivación original de Post en el estudio de esta red era encontrar una noción estructural de tal manera que cada conjunto que satisfaga esta propiedad no esté en el grado de Turing de los conjuntos recursivos ni en el grado de Turing del problema de detención. Post no encontró dicha propiedad y la solución a su problema aplicó métodos de prioridad; Harrington y Soare (1991) encontraron eventualmente tal propiedad.

Lectura adicional, vea la publicación del blog Teoría de la red para programadores y no informáticos.

Answer 2

Las referencias dadas por Pål GD son realmente muy apropiadas.Así que centrémonos en un problema secundario menor en esta respuesta.Leí un poco sobre celosías hace algún tiempo y comencé a preguntarme si la noción de semiretícula no habría sido más apropiada para las aplicaciones.Se podría objetar que una semi-red completa es automáticamente también una red, pero los homomorfismos y subestructuras (es decir,subredes y subsemiredes) son diferentes.

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

Answer 3

Un caso muy importante, pero no tan famoso, es bien conocido entre los teóricos, pero no tan conocido en el sentido de ser enseñado a estudiantes universitarios, del uso de una red es demostrar Límites inferiores superpolinomiales sobre el tamaño de los circuitos monótonos informáticos para cual Razborov ganó la Premio de Nevanlinna. La construcción original es muy técnica y construcciones posteriores, por ejemplo, Berg/Ulfberg Simplifique el marco sin la referencia a las redes.

Entonces, en este caso, la teoría de la red se usó como un 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 otro lugar de su estilo de aplicar matemáticas avanzadas a CS] que podrían corresponder a algún otro objeto más "concreto" en CS, en este caso es "Gates 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 inexacto e aproximado.

Answer 4

Desde entonces he encontrado el papel gratis Conjuntos ordenados y redes completas: una imprimación para informática, para otros lectores interesados.

Answer 5

Los etiquetados de borde regulares y las estructuras relacionadas forman una red distributiva (ver por ejemplo aquí). Esto se puede explotar para buscar eficientemente a través del espacio de todos los etiquetados de borde regulares para un gráfico determinado (ver aquí). Como aplicación, puede determinar si se puede dibujar un mapa como cartograma con una cierta asignación de área para las caras.

Answer 6

Además, sorprendentemente (para mí, al menos) criptografía. Compruébalo, permite nuevos ataques de criptosistemas conocidos y da la esperanza de la criptografía posterior al cuanto al cuanto al cuente.