MATH 7880: Topics in Applied Logic (fall 2008)

Instructor: Bakhadyr Khoussainov

This is a course for graduate students interested in applications of automata in mathematics and mathematical foundations of computer science. The course will be devoted to the study of mathematical structures that can be described by finite state machines such as finite automata, tree automata, and omega automata.

The course will consist of three parts. The first part studies mathematical and algorithmic properties of automata. An emphasis will be put on the well-known complementation problem in automata theory. The core of this part will be Safra's construction that solves the complementation problem for Buchi automata. The second part will introduce the concept of automatic structure. Here algorithmic and logical properties of automatic structures will be investigated. The core of this part will be to show that certain natural problems about automatic structures are decidable. The last part of the course will be devoted to understanding typical mathematical structures that are decsribed by automata. These structures include linear orders, Boolean algebras, trees, graphs, and groups.

The theory of automatic structures is a new emerging area of research in logic and theoretical computer science that has both deep mathematics as well as theoretical computer science background.