Usos de estructuras algebraicas en informática teórica

67

Soy un profesional del software y estoy escribiendo una encuesta sobre estructuras algebraicas para la investigación personal y estoy tratando de producir ejemplos de cómo se utilizan estas estructuras en la informática teórica (y en menor grado, otros subcampos de la informática) .

Bajo la teoría de grupo, me he encontrado con monoides sintácticos para lenguajes formales y monoides de rastreo e historia para computación paralela / concurrente.

Desde el punto de vista de la teoría de los anillos, me he encontrado con marcos de semiring para el procesamiento de gráficos y el análisis basado en semiring.

Todavía no he encontrado ningún uso de las estructuras algebraicas de la teoría de módulos en mi investigación (y me gustaría).

Supongo que hay más ejemplos y que no estoy buscando en el lugar correcto para encontrarlos.

¿Cuáles son algunos otros ejemplos de estructuras algebraicas de los dominios enumerados anteriormente que se encuentran comúnmente en la informática teórica (y otros subcampos de la informática)? Alternativamente, ¿qué revistas u otros recursos puede recomendar que cubran estos temas?

GEL
fuente
12
Esto parece bastante vasto. Todo tipo de estructuras algebraicas (grupos, anillos, semirremolques, semigrupos, campos) se muestran en la informática teórica, y es lo suficientemente generalizado como para que sea difícil encontrar un subcomponente específico. Además, no olvide los campos finitos para el hash y muchos otros métodos de huellas dactilares aleatorias.
Suresh Venkat
3
¡Posiblemente cualquier cosa que pueda ser representable tenga un uso en informática!
vs

Respuestas:

46

Mi impresión es que, en general, el álgebra tradicional es demasiado específico para su uso en informática. Entonces, los informáticos usan estructuras más débiles (y, por lo tanto, más generales), o generalizan las estructuras tradicionales para que puedan adaptarse a sus necesidades. También usamos mucho la teoría de categorías, que los matemáticos no consideran parte del álgebra, pero no vemos por qué no. La reglamentación de las matemáticas tradicionales en "álgebra" y "topología" como ramas separadas es incómoda, incluso sin sentido, porque el álgebra es generalmente de primer orden, mientras que la topología tiene la posibilidad de tratar aspectos de orden superior. Por lo tanto, las estructuras utilizadas en Informática tienen álgebra y topología mezcladas. De hecho, diría que tienden más hacia la topología que el álgebra. La reglamentación del razonamiento en "álgebra" y "lógica" es otra división sin sentido desde nuestro punto de vista, porque el álgebra se ocupa de las propiedades de la ecuación, mientras que la lógica también se ocupa de todos los otros tipos de propiedades.

Volviendo a su pregunta, los semigrupos y monoides se usan con bastante intensidad en la teoría de autómatas. Eilenberg ha escrito una colección de 2 volúmenes , el segundo de los cuales es casi completamente álgebra. Me dijeron que estaba planeando cuatro volúmenes, pero su edad no permitió que el proyecto se terminara. Jean-Eric Pin tiene una versión modernizada de gran parte de este contenido en un libro en línea . Los autómatas son "módulos monoides" (también llamados acciones monoides o "actos"), que se encuentran en el nivel correcto de generalidad para la informática. Los módulos de anillo tradicionales son probablemente demasiado específicos.

La teoría del enrejado fue una fuerza importante en el desarrollo de la semántica denotacional. La topología se mezcló con la teoría de redes cuando los informáticos, junto con los matemáticos, desarrollaron redes continuas y luego las generalizaron a dominios . Diría que la teoría del dominio es la matemática propia de los informáticos, de la cual las matemáticas tradicionales no tienen conocimiento.

El álgebra universal se usa para definir especificaciones algebraicas de tipos de datos . Habiendo llegado allí, los informáticos descubrieron de inmediato la necesidad de lidiar con propiedades más generales: ecuaciones condicionales (también llamadas cláusulas de cuerno equitativas) y propiedades lógicas de primer orden, que todavía usan las mismas ideas de álgebra universal. Como notarías, el álgebra ahora se fusiona con la teoría de modelos.

La teoría de categorías es la base de la teoría de tipos. A medida que los informáticos siguen inventando nuevas estructuras para lidiar con varios fenómenos computacionales, la teoría de categorías es un marco muy reconfortante en el que ubicar todas estas ideas. También usamos estructuras que están habilitadas por la teoría de categorías, que no tienen existencia en las matemáticas "tradicionales", como las categorías functor. Además, el álgebra vuelve a la imagen desde un punto de vista categórico en el uso de mónadas y teorías algebraicas de los efectos . Las coalgebras , que son los duales de las álgebras, también encuentran mucha aplicación.

Por lo tanto, existe una amplia aplicación de "álgebra" en informática, pero no es el tipo de álgebra que se encuentra en los libros de texto de álgebra tradicionales.

Nota adicional : Hay un sentido concreto en el que la teoría de categorías es álgebra. Monoide es una estructura fundamental en álgebra. Consiste en un operador binario de "multiplicación" que es asociativo y tiene una identidad. La teoría de categorías generaliza esta asociando "tipos" de los elementos del monoide, . Se puede "multiplicar" los elementos sólo cuando los tipos de concordancia: si y entonces . Por ejemplo, matrices tienen una operación de multiplicación que las convierte en un monoide. Sin embargo, matrices (donde ya : X Y b : Y Z a b : X Z n × n m × n m na:XYa:XYb:YZab:XZn×nm×nmnpodría ser diferente) formar una categoría. Los monoides son, por lo tanto, casos especiales de categorías que tienen un solo tipo. Los anillos son casos especiales de categorías aditivas que tienen un solo tipo. Los módulos son casos especiales de functores donde las categorías de origen y destino tienen un solo tipo. Pronto. La teoría de categorías es álgebra tipeada cuyos tipos la hacen infinitamente más aplicable que el álgebra tradicional.

Uday Reddy
fuente
24
Los teóricos de categorías piensan que el álgebra es parte de la teoría de categorías. Los álgebraistas piensan en la teoría de categorías como parte del álgebra. Los lógicos piensan que ambos están locos.
Jeffε
44
Hay mucha interacción entre la topología y el álgebra en matemáticas puras ...
Sasho Nikolov
16
Esta es una buena respuesta, pero creo que sus comentarios sobre la "reglamentación" y la "cultura del silo" son engañosos. La razón por la que el álgebra, la topología y la lógica te parecen unificadas es que, para las preguntas que te interesan , las partes de estos temas que son relevantes para ti están estrechamente entrelazadas. Pero si, por ejemplo, intentara clasificar las variedades de 4 dimensiones sobre los números complejos, vería rápidamente la utilidad de las distinciones tradicionales que hacen los matemáticos. Todo depende de qué problema estés tratando de resolver.
Timothy Chow
3
Personalmente, todavía estoy completamente perplejo por casi cualquier inferencia que hagas sobre la cultura de investigación en matemáticas y ciencias de la computación. Como señala @TimothyChow, se desarrollaron diferentes subcampos para tratar diferentes tipos de problemas y, por lo tanto, se desarrollaron diferentes herramientas. Donde tiene sentido traer herramientas de diferentes subcampos, y las personas se han dado cuenta de eso, hay interacción. Los ejemplos no deberían ser difíciles de encontrar, por ejemplo, en las notas de clase sobre álgebra de mentiras.
Sasho Nikolov
3
con respecto a que hay menos cultura del silo en informática, tampoco estaría de acuerdo allí. Personalmente, no tengo idea de por qué los investigadores de PL necesitan toda esta maquinaria pesada, para qué la usan, qué problema resuelven con ella y por qué debería importarme. Tal vez sea mi propia ignorancia, pero dudo que la mayoría de los teóricos de la complejidad y los algorítmicos sepan las respuestas a estas preguntas ...
Sasho Nikolov
23

Mi aplicación favorita de todos los tiempos de la teoría de grupos en TCS es el Teorema de Barrington. Puede encontrar una exposición de este teorema en el blog de complejidad , y la exposición de Barrington en la sección de comentarios de esa publicación.

Dai Le
fuente
2
+1: y muchos lo consideran uno de los resultados más sorprendentes en la teoría de la complejidad. :)
Kaveh
15

Grupos, anillos, campos y módulos están en todas partes en la topología computacional. Ver especialmente el trabajo de Carlsson y Zomorodian [ex: 1 ] sobre homología persistente (multidimensional), que se trata de módulos calificados sobre dominios ideales principales.

Jeffε
fuente
@JeffE, enlaces, por favor.
scaaahu
1
@JeffE, mi comentario no fue ofensivo. Sí, sé cómo Google. Mi punto fue, ¿hay un artículo en particular escrito por Carlsson y Zomorodian, que sería una especie de resumen de la homología persistente? Si hay uno, háganoslo saber. Gracias.
scaaahu
Sugiero comenzar con este artículo . (Lo siento, mi comentario anterior estaba fuera de lugar.)
Jeffε
@JeffE, lo tengo, exactamente lo que estaba buscando. Gracias.
scaaahu
14

Este es un uso muy agradable y práctico: un algoritmo para calcular la conectividad gráfica (de FOCS2011 ). Para calcular la conectividad s-> t de un gráfico, los autores dan un algoritmo que asigna vectores aleatorios con entradas dibujadas desde un campo finito a los bordes externos desde s, luego construye vectores similares para todos los bordes en el gráfico tomando aleatoriamente combinaciones lineales, y finalmente descubren la conectividad calculando el rango de los vectores resultantes asignados a los bordes internos de t.

Aaron Roth
fuente
¡Gracias por el puntero y la descripción general! Esto fue de FOCS 2011: dx.doi.org/10.1109/FOCS.2011.55
András Salamon
12

Los enrejados y los puntos fijos son la base del análisis y la verificación del programa. Aunque los resultados avanzados de la teoría de la red rara vez se usan porque nos preocupan los problemas algorítmicos como la computación y la aproximación de puntos fijos, mientras que la investigación en la teoría de la red tiene un enfoque diferente (conexiones a la topología, la teoría de la dualidad, etc.). Los trabajos iniciales de interpretación abstracta utilizan la teoría básica de la red. El trabajo de Roberto Giacobazzi y sus colaboradores utiliza resultados más avanzados.

En la informática distribuida, se obtuvo una familia célebre de resultados imposibles utilizando métodos de topología algebraica (ver el trabajo de Maurice Herlihy y Nir Shavit).

[Editar: consulte Aplicaciones de topología en informática ].

Vijay D
fuente
12

El álgebra universal es una herramienta importante para estudiar la complejidad de los problemas de satisfacción de restricciones.

Por ejemplo, la Conjetura de la dicotomía establece que, en términos generales, un problema de satisfacción de restricciones sobre un dominio finito es NP-completo o puede resolverse en tiempo polinómico. Tenga en cuenta que, según el teorema de Ladner, hay problemas en NP que no están en P ni en NP completos, a menos que P = NP, por lo que la conjetura dice que los CSP son especiales para tener una dicotomía que las clases de mayor complejidad no tienen. También proporcionaría alguna explicación de por qué la mayoría de los problemas que encontramos en la práctica pueden clasificarse como NP-completos o en P.

Las dicotomías se probaron para varios casos especiales, por ejemplo, CSP de dominio binario (Schaefer) y CSP de dominio ternario (Bulatov), ​​y homomorfismos en gráficos no dirigidos (Hell y Nesetril). Pero el caso general es bastante abierto. Una de las principales líneas de ataque es a través del álgebra universal. En términos generales (¡y definitivamente no soy un experto en esto!) Se define un polimorfismo de CSP como una función en el dominio del CSP que deja satisfechas todas las restricciones satisfechas si se aplica a cada variable. El conjunto de polimorfismos de un CSP en cierto sentido captura su complejidad. Por ejemplo, si un CSP A admite todos los polimorfismos de un CSP B, entonces A es polinomial reducible en tiempo a B. El conjunto de polimorfismos forma un álgebra, cuya estructura parece útil para diseñar algoritmos / mostrar reducciones. Por ejemplo, si el álgebra de polimorfismo de un CSP es idempotente y admite el tipo unario, entonces el CSP es NP-completo. La idempotencia es un supuesto simplificador que puede hacerse más o menos sin pérdida de generalidad. Demostrar que un CSP cuyo álgebra es idempotente y no admite el tipo unario puede resolverse en tiempo polinómico demostrará la Conjetura de la dicotomía.

Vea la encuesta de Bulatov: http://www.springerlink.com/content/a553847g6h673k05/ .

Sasho Nikolov
fuente
11

Aquí hay dos aplicaciones de una parte diferente de TCS.

Semirings se utilizan para modelar anotaciones en bases de datos (especialmente aquellas necesarias para la procedencia), y a menudo también para las estructuras de valoración en la satisfacción de restricciones valoradas. En ambas aplicaciones, los valores individuales deben combinarse de manera que conduzcan naturalmente a una estructura semired, con asociatividad y una operación semiring distribuyendo sobre la otra. Con respecto a su consulta sobre módulos, ninguno de los monoides tiene un inverso en estas aplicaciones, en general.

András Salamon
fuente
10

Los anillos, los módulos y las variedades algebraicas se usan en la corrección de errores y, más generalmente, en la teoría de la codificación.

Específicamente, hay un esquema de corrección de errores abstracto (códigos de geometría algebraica) que generaliza los códigos Reed-Solomon y los códigos chinos restantes. El esquema consiste básicamente en tomar sus mensajes para que provengan de un anillo R y codificarlo tomando sus módulos de módulos de muchos ideales diferentes en R. Bajo ciertas suposiciones sobre R, uno puede probar que esto hace un error decente al corregir el código.

En el mundo de la decodificación de listas, un artículo reciente de Guruswami ofrece un método lineal-algebraico de decodificación de listas de códigos Reed-Solomon plegados, que tiene la buena propiedad de que todos los mensajes candidatos se encuentran en un subespacio afín de baja dimensión del espacio de mensajes . Se pueden construir conjuntos evasivos del subespacio , conjuntos que son casi tan grandes como todo el espacio pero que tienen una pequeña intersección con cada subespacio afín de baja dimensión. Si uno restringe los mensajes para que provengan de un conjunto evasivo del subespacio dentro del espacio de mensajes, entonces el esquema de Guruswami proporciona un algoritmo que garantiza un buen tamaño de lista. Hasta ahora, la única construcción explícita de conjuntos evasivos subespaciales es dada por Dvir y Lovett en su próximo documento STOC, Conjuntos evasivos subespaciales y construya el conjunto tomando una variedad afín específica (y tomando su producto cartesiano consigo mismo).

Alan Guo
fuente
6

Echa un vistazo a la teoría de Ramsey : básicamente, una generalización significativa del principio del casillero que subyace a muchos autómatas y teoría del lenguaje formal (o debería decir que el principio del casillero es el caso más simple de la teoría de Ramsey). Básicamente dice que incluso las estructuras altamente desordenadas necesariamente contienen mucho orden si son lo suficientemente grandes. Para un pequeño ejemplo, más allá del principio del casillero, tenga en cuenta que si toma seis personas, tres de ellas se conocen mutuamente o tres no se conocen entre sí.

Este documento parece un buen lugar para comenzar a conectarse con la informática, pero puede buscar en Google para obtener más información. Es más combinatorio que algebraico en su naturaleza básica, pero tiene muchas aplicaciones en álgebra y CS teórica.

Y también echa un vistazo a la historia del inventor, Frank Ramsey , verdaderamente un polímato notable que hizo contribuciones fundamentales, incluso revolucionarias en economía y filosofía, así como en matemáticas, muchas de las cuales no fueron apreciadas hasta mucho más tarde, todo antes de morir a la edad de 26 años. ¡solo piensa! De hecho, el teorema original de Ramsey, la base de la teoría de Ramsey, era un mero lema en un artículo con un objetivo mayor en lógica matemática.

David Lewis
fuente
2
Esto es algo clásico de combinatoria extrema, me pregunto ¿dónde ves la conexión con el álgebra? (No discuto que la teoría de Ramsey es una fuente de grandes problemas y teoremas)
Sasho Nikolov
Bueno, por un lado, la teoría de grafos es extremadamente importante en la CS teórica. Y mira el enlace en mi respuesta, así como esta búsqueda . Además, de Pin, JE, Variedades de lenguajes formales , Teorema 1.11: cualquier semigrupo finito generado por , tiene con cada palabra loinger que tiene idempotente con , y all . Esto se demuestra más fácilmente con el Teorema de Ramsey. A k > = 2 n w A + n e S w = x u 1 . . . u n y x , y A ˉ u i = eSAk>=2nwA+neSw=xu1...unyx,yAu¯i=e
David Lewis
No estoy discutiendo la relevancia de la teoría de Ramsey, y mucho menos la teoría de gráficos, para tcs. Estoy diciendo que el OP preguntó sobre aplicaciones de álgebra y la teoría de ramsey no es algo generalmente asociado con álgebra, afaik. pero como parece tener alguna conexión con la teoría de ramsey -> álgebra -> tcs en mente, quizás pueda agregar eso a su respuesta
Sasho Nikolov
@Sasho: si quieres decir que la teoría de Ramsey no es un tema de álgebra, entonces mi respuesta está fuera de lugar, entonces estás 100% correcto. Pido disculpas por mi respuesta. Supongo que mi mente tiende a cruzar los límites disciplinarios y subdisciplinarios con bastante facilidad. Pero es peor que eso: la teoría de Ramsey no es en absoluto una "estructura algebraica". Por favor, siéntase libre de votar mi respuesta. Saludos.
David Lewis
bueno, aunque tal vez el downvoting sea lógico, me encanta la combinatoria extrema, así que no voy a :) Por cierto, estoy bastante seguro de que hay algunos fenómenos de tipo ramsey que ocurren con estructuras algebraicas, tal vez incluso a "densidades" más bajas debido a la simetrías, así que me estás dando una idea sobre una pregunta
Sasho Nikolov
5

El análisis de cualquier problema con mucha simetría se facilita mediante el uso de la teoría de grupos. Un ejemplo sería encontrar algoritmos para cosas como el cubo de Rubic. Aunque no conozco los detalles, estoy seguro de que probar que el número de Dios es 20 requería una poda teórica grupal seria. En un contexto diferente, los solucionadores prácticos para el problema de isomorfismo gráfico como náutico usan el grupo automorfismo del gráfico.

Shitikanth
fuente
Además, los algoritmos para el isomorfismo gráfico [Luks '81; Babai - Luks '82] con las garantías más conocidas (es decir, funciona en teoría, pero puede ser ineficiente en la práctica) utiliza la teoría de grupos en gran medida, incluso invocando la clasificación de grupos simples finitos.
Joshua Grochow
5

El álgebra (y la geometría algebraica) ha tenido un papel bastante importante en la criptografía, con grupos de curvas elípticas, redes (teóricas de números) y, por supuesto, es la base de casi todo el trabajo criptográfico moderno.Zp

Pratyush Mishra
fuente
1
Según tengo entendido, hay otras estructuras algebraicas (campos finitos, anillos y otras estructuras) que se utilizan en la criptografía moderna, que está abandonando gradualmente la teoría de números y centrándose más en redes, códigos de corrección de errores y problemas de "resistencia cuántica".
josh
1

En la programación funcional, las abstracciones más generales y elegantes para los problemas son a menudo de naturaleza algebraica (o teórica de categoría): monoides, semirremolques , functores, mónadas, álgebras F , carbonebras F, etc. Algunos resultados clásicos (por ejemplo, el Yoneda lema) resultan tener contenido computacional y utilidad.

Además, existe la teoría de tipos de homotopía, que interpreta la teoría de tipos en (tipo de) un entorno topológico algebraico.

xrq
fuente