by Prof. Dr. rer. nat. Jürgen Dix



The first chapter covers some topics from the Chomsky hierarchy: the Myhill-Nerode theorem (how to construct a minimal finite automaton), deterministic PDA’s, type 1 languages, normalform for type 0 and type 1 languages, Ehrenfeuchts theorem and Lindenmayer systems, a class of grammars that is orthogonal to parts of the Chomsky hierarchy.
Chapter 2 discusses undecidability results in greater depth (Posts Correspondence theorem, (primitive) recursive functions, Hilberts 10. problem (solving diophantine equations)). We also cover Rices theorem and its analogue for grammars. Makanins problem (word equations over a free monoid) is decidable but not primitive recursive.

Chapters 3 and 4 cover classical complexity results: time versus space, speed-up, gap-theorem, union-theorem and complexity classes: PH (the polynomial hierarchy), PSPACE, EXPSPACE and most of their interesting subclasses. We also cover closure properties and the Immerman/Szelepcsényi theorem.
Chapter 5 covers the arithmetical and analytical hierarchy (extending EXPSPACE into the undecidable) and discusses descriptive complexity: can we find logics corresponding to complexity classes (Fagins theorem).


Lecture recordings

  • Short information

    Semester: SS 2011

    Lecture number: S 1228

  • Contributors
    Anja Michaela Kaiser
    Prof. Dr. rer. nat. Jürgen Dix
  • Hints / Further information

    Videoserver FAQ (in german only)

    Additional information about the lecture: