Seminar: Computability and Complexity II

Dr. Heinrich Rolletschek

March 20, 2007

Preliminary meeting:

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

Time and place:

Friday, 8:30, seminar room.

Contents:

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.

Literature:

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

Assessment:

Grades will be based on presentations given in the seminar.