Advanced Topics in Automata (2003)

Lectures: Tuesday 1400-1600, Ziskind 1

Lecturers

David Harel Nir Piterman

Graders

Rachel Matichin Dan Barak

Syllabus

The course will cover advanced topics in the theory of automata, with a special emphasis on the theory of automata on infinite words. As a basis for the course, we will review finite automata on finite words, and will present a few important results that are usually not covered in undergraduate courses, as well as some practical outcomes of the topic, such as statecharts. We will then introduce several variants of finite automata over infinite words, will study their closure properties and the conversions between the different variants, and will deal with some decidability issues (e.g., membership, emptiness and universality). We will show applications of automata on infinite words to logic and program verification. Finally, we intend to cover some fundamental results on context free languages and pushdown automata over finite words, such as Parikh's Theorem.

Exercises:

  • Ex1 postscript pdf
  • Ex2 postscript pdf
  • Ex3 postscript pdf
  • Ex4 postscript pdf
  • Ex5 postscript pdf
  • Ex6 postscript pdf
  • Ex7 postscript pdf
  • Ex8 postscript pdf
  • Ex9 postscript pdf
  • Exam:

    postscript pdf

    Messages