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