Seminar: Computability and Complexity I
Dr. Heinrich Rolletschek
October 9, 2006
Monday October 9, 15:00, Seminarraum Schloß Hagenberg
Wednesday, 10:00, seminar room, beginning October 11.
This schedule is just provisorial and may be changed.
The seminar will deal with selected topics in the following areas:
- Classical recursive function theory.
- Lower-level computability (regular and context-free languages)
- Abstract complexity theory
The first and third of these areas are also topics of my lectures Computability Theory and
Decidability and Complexity Classes, and knowledge of basic concepts will certainly be helpful.
- W. Brainerd, L. Landweber: Theory of Computation. Wiley 1974.
- J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley
1979.
- M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company 2005.
- G. Tourlakis: Computability. Reston Publishing Company 1984.
Grades will be based on presentations given in the seminar.
