Aplicaciones de la teoría de modelos y el álgebra a la informática

Question

Como sugiere el título, busco aplicaciones de las dos primeras a la segunda.

Por supuesto, hay algunas aplicaciones: la teoría algebraica de números en la seguridad informática, la teoría de modelos finitos, que puede considerarse un campo en la intersección de las matemáticas, la lógica y la teoría. CS con la Teoría de la Complejidad Descriptiva siendo ciertamente muy interesante.

Pero estoy buscando algo un poco diferente, pronto tendré que escribir una tesis en CS y como también tengo formación en matemáticas me gustaría utilizarla. Sobre Álgebra, he escuchado dos cursos introductorios, de modo que ahora estoy al nivel de Atiyah-Macdonald, y estoy bastante avanzado en Teoría de Modelos. Acabo de empezar con el libro de texto de Markers sobre la Teoría de Modelos, y estoy progresando bastante rápido, debido a mis antecedentes de Álgebra y Chang-Keisler.

Así que mi pregunta es básicamente, ¿cuáles son las buenas referencias para seguir aprendiendo en CS donde puedo aprovechar plenamente los recursos de MT y Álgebra y su íntima relación? Estaría muy interesado si hay tales aplicaciones en Criptografía y campos relacionados.

¡Muchas gracias!

Answer 1

La cuestión Aplicaciones de la lógica y el álgebra a la informática se parece a la suya, pero en realidad es muy diferente. Sin embargo, algunas de las respuestas pueden ser de interés.

Además, se han planteado preguntas similares en cstheory y algunas respuestas podrían proporcionarte buenas referencias para seguir aprendiendo en CS. Esta es mi selección:

Álgebra

Debería echar un vistazo a la pregunta Usos de estructuras algebraicas en informática teórica en el respuesta aceptada y probablemente también en las otras respuestas.

La cuestión Rama de la informática teórica orientada al álgebra también puede interesarle.

Teoría de modelos

Permítanme mencionar Punteros para aplicaciones CS de la lógica . En particular, he aquí una cita extraída de Respuesta de Vijay D

Teoría de los modelos finitos

La restricción más simple de la teoría clásica de modelos desde el punto de vista de la informática es estudiar estructuras sobre un universo finito. Estas estructuras se presentan en forma de bases de datos relacionales, grafos y otros objetos combinatorios que surgen por doquier en informática. informática.

Respuesta de Dai Le a este pregunta también ofrece otras referencias pertinentes.

Answer 2

Otro ámbito de la teoría de la complejidad que se basa en gran medida en los métodos de la teoría de modelos es la complejidad de las pruebas. Esta área tiene la ventaja de que utiliza métodos estándar de la teoría de modelos (infinitos). La teoría de modelos finitos comparte el nombre con la teoría de modelos infinitos, pero utiliza técnicas muy diferentes.

La complejidad de las pruebas puede estudiarse desde el punto de vista de la teoría de pruebas o de la teoría de modelos. Una buena introducción a la complejidad de las pruebas desde el punto de vista de la teoría de modelos es el libro de Jan Krajícek "Bounded arithmetic, propositional logic, and complexity theory". El enfoque de Krajícek suele utilizar también bastante álgebra. Por lo tanto, creo que puede valer la pena echarle un vistazo a este libro.

Answer 3

Bueno, existe una rica intersección entre la teoría de modelos y la computación computacional en cosas relacionadas con la computabilidad, como la correspondencia Curry-Howard y las interpretaciones computacionales del teorema de Löb y otros resultados clásicos.

Personalmente, la línea de investigación del Instituto de Investigación de Inteligencia Artificial me parece fascinante. Su programa de investigación sobre los fundamentos de los agentes abarca algunas cuestiones lógicas interesantes.

En cambio, el álgebra aparece por todas partes. Quizá puedas investigar cosas como la teoría de categorías, donde se están explorando ciertos vínculos con la CS.