# Seminar: Computability and Complexity II

## Dr. Heinrich Rolletschek

### March 20, 2007

Monday March 5, 14:00, Seminarraum Schloß Hagenberg

Friday, 8:30, seminar room.

The seminar will deal with selected topics in the following areas:

- Classical recursive function theory.
- Lower-level computability (deterministic context-free languages, context-sensitive languages)
- Abstract complexity theory
- Polynomial-time complexity

Some material in these areas (except for lower-level computability) is contained in 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.
- R. Soare:
*Recursively Enumerable Sets and Degrees*. Springer 1986.
- G. Tourlakis:
*Computability*. Reston Publishing Company 1984.

Grades will be based on presentations given in the seminar.