Course: Advanced Automata Theory

Summer 2017

Introduction

We shall study automata on finite/infinite words and trees and their relationship to logic and computer-aided verification of systems.

Computer science or math students with background in logic and theory of computation. (Familiarity with basic algorithms, logic, and theory of computation will be assumed). Talk to the instructor if you are not sure if you have the background. We shall try to keep the class self-contained, please attend the initial lecture for background material.

Further, I expect you (1) have "mathematical maturity" (e.g., you should be comfortable with proofs and abstract reasoning); (2) are interested in the material; and (3) are willing to spend time outside of class in order to better understand the material presented in lectures.

Grading will be based on a written, open-notes, final exam. Open notes means that you are free to bring your notes to the exam. However, you may not use internet access on any device during an exam.

In order to appear for the exam, you have to turn in homework problems (to be assigned approximately biweekly), write up lecture notes for two lectures, and present a result to the class.

The following text books cover most of the material:

  1. Michael Sipser, Introduction to the theory of computation, MIT Press b. Graedel, Thomas, Wilke, Automata, Logics, and Infinite Games, Springer

In addition, we shall provide lecture notes, surveys, or research papers for topics not covered in these books.

Homework exercises will be handed out approximately every two weeks (weekday TBA). Your answers must be handed in until the day specified in the homework, at the beginning of the lecture.

Students may collaborate on homework assignments, but each student needs to individually write up a solution set and be prepared to present it in class on the due date. The work you submit in this course must be the result of your individual effort. You may discuss homework problems and general proof strategies or algorithms with other students in the course, but you must not collaborate in the detailed development or actual writing of problem sets. This implies that one student should never have in his or her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. In writing up your homework you are allowed to use any book, paper, or published material. However, you are not allowed to ask others for specific solutions, either in person or by using electronic forums such as newsgroups. Of course, during the administration of exams any form of cooperation or help is forbidden. Academic dishonesty has no place in a university; it wastes our time and yours, and it is unfair to the majority of students. Any dishonest behavior will be severely penalized and may lead to failure in the course.

Announcements

Schedule

This schedule is preliminary and subject to change.

#

Date

Course topic / lecture

Homework

Additional Materials (lecture notes/papers)

L1

April 23

Introduction to formal verification

April 25

L2

April 28

Preliminaries: graph algorithms, automata theory

Homework 1. Need not be turned in.

Lecture notes

L3

April 30

Preliminaries: propositional logic

Lecture notes
Problem L (Labyrinth). Solution.
Try OCaml, Learn OCaml, Real World OCaml

T1

May 2

Solutions to Homework 1.

L4

May 5

The invariant verification problem. Enumerative invariant verification. Depth first search. Spin.

Notes from an unpublished text book by Rajeev Alur and Tom Henzinger:
The Reactive modules modeling language.
Invariant verification.
SPIN web page.

L5

May 7

Peterson's protocol. Heuristics for enumerative invariant verification. Symbolic invariant verification. Symbolic reachability.

Alur and Henzinger. Symbolic graph representation.

MPG (660 MB)

T2

May 9

Q & A

L6

May 12

Symbolic model checking with SAT

Malik and Weissenbacher. Boolean satisfiability solvers: Techniques and extensions.
Nieuwenhuis, Oliveras, and Tinelli. Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T).

MPG (678 MB)

L7

May 14

Implementing a SAT Solver. BDDs.

Homework 2. Due May 28, 2014.

MP4 (529 MB)

T3

May 16

Q & A