# 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.