Mathematical Theory of Computation Qualifying Exam Syllabus (Draft June 1996)

1. Background: Logic; Computability, Complexity and Recursion Theory. • Enderton, H.B., A Mathematical Introduction to Logic. Academic Press, 1972.

• Hopcroft, J.E. and Ullman, J.D., Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Chapters 4, 7, 8, 12 and 13 (context-free grammars, Turing machines and undecidability, basic complexity). · Alternates

– Cutland, N., Computability, an Introduction to Recursive Function Theory. Cambridge University Press, 1980. Chapters 1–7.

– Floyd, R. and Beigel, R., whatever

– Kleene, S., Introduction to Metamathematics. North-Holland, 1952. Chapters 1–3.

– Lewis, H. and Papadimitriou, C.H., whatever

2. Programming Language Theory, Universal Algebra and Category Theory.

• Mitchell, J., Foundations for Programming Languages, MIT Press, 1996. Chapters 1–7. · Alternates

– Gunter, C., Semantics of Programming Languages MIT Press, 1992. Chapters 3–5.

– Pierce, B., Basic Category Theory for Computer Scientists MIT Press, 1991.

3. Models of Concurrency.

• Milner, R., Communication and Concurrency. Prentice-Hall, 1989. Chapters 1–7.

• Hennessy, M., Algebraic Theory of Processes. MIT Press, 1988. Chapters 1–2.

• van Glabbeek, R., Comparative Concurrency Semantics and Refinement of Actions, CWI Tract 109, 1996. Chapter 1.

• Peterson, J., Petri Nets, in ACM Computing Surveys 9(3), 223-252 (1977)

4. Automated Theorem Proving and Verification

• Manna, Z. and Pnueli, A., Temporal Verification of Reactive Systems: Safety. Springer-

Verlag, 1995.

5. Recommended courses: CS 256, CS 258, CS ???.