Applications of Model Theory and Algebra to Computer Science

Question

as the title suggests I'm looking for applications of the two former to the latter.

Ofc there are some applications, Algebraic Number Theory in IT-Security, Finite Model Theory can be seen as a field at the intersection of math. logic. and theor. CS with Descriptive Complexity Theory certainly being very interesting.

But I'm looking for something a little differently, i will soon have to write a thesis in CS and as i also have a background in math i would like to use it. About Algebra, i have heard two introductory courses, so that I am now at the level of Atiyah-Macdonald, and am quite advanced in Model Theory. I just started with Markers textbook on Model Theory, and am progressing quite quick, due to my background from Algebra and Chang-Keisler.

So my question is basically, what are good references for further learning in CS where i can fully draw from the ressources of MT and Algebra and their intimate relation? I would be most interested if there are such applications in Cryptography and related fields.

Thanks a lot!

Answer 1

Well, you have a rich intersection of model theory and CS in things related to Computability, such as the Curry Howard correspondence and computability interpretations of Löb's theorem and other classic results.

Personally I find the line of research by the Machine Intelligence Research Institute fascinating. Their agents foundations Research agenda covers some interesting logic stuff.

Algebra on the other hand pops up everywhere. Maybe you can look into things like category theory, where there are certain links with CS being explored those days.

Answer 2

The question Applications of Logic and Algebra in Computer Science looks similar to yours, but is actually quite different. However, some of the answers might be of interest.

Moreover, similar questions have been asked on cstheory and some answers might provide you good references for further learning in CS. Here is my selection:

Algebra

You should have a look at the question Uses of algebraic structures in theoretical computer science, at the accepted answer and probably also at the other answers.

The question Algebra oriented branch of theoretical computer science might also be of interest to you.

Model Theory

Let me mention Pointers for CS applications of logic. In particular, here is a quote extracted from Vijay D's answer

Finite Model Theory

The simplest restriction of classical model theory from the viewpoint of computer science is to study structures over a finite universe. These structures occur in the form of relational databases, graphs, and other combinatorial objects arising everywhere in computer science.

Dai Le's answer to this question also gives some further relevant references.

Answer 3

Another area of complexity theory that relies heavily on model theoretic methods is proof complexity. This area has the advantage that it uses standard methods form (infinite) model theory. Finite model theory shares the name with infinite model theory but uses mostly different techniques.

Proof complexity can be studied from a proof theoretic or from a model theoretic point of view. A good introduction into proof complexity from a model theoretic stand point is Jan Krajíček's book ""Bounded arithmetic, propositional logic, and complexity theory". Krajíček's approach uses usually also a fair bit of algebra. Therefore, I think this book may be worth a look for you.