CIS 511, 2013

Additional Useful References:

Automata and Computability, Dexter Kozen, Springer

Introduction to the Theory of Computation, Michael Sipser, Second Edition, 2005, Thompson Course Technology

Theory of Computation, Derick Wood, Wiley

Mathematical Theory of Computation, Zohar Manna, McGraw Hill

An Introduction to the General Theory of Algorithms, M. Machtey and P. Young, Elsevier North-Holland

Introduction to Formal Language Theory, M. Harrison, Addison Wesley

The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Martin Davis, Raven Press

Theory of Recursive Functions and Effective Computability, Hartley Rogers, MIT Press

Introduction to Metamathematics, Stephen Kleene, North-Holland

Computability and Unsolvability, Martin Davis, McGraw-Hill

Enumerability, Decidability, Computability, Hans Hermes, Springer-Verlag

Computational Complexity, A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009

Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 2000

Computational Complexity, Christos Papadimitriou, Addison Wesley

Some Historical and Leading Figures

David Hilbert, Alan Turing, Stephen Kleene, Kurt Godel, Alonzo Church, Haskell Curry, Jacques Herbrand, Emil Post, Wilhelm Ackermann, Axel Thue, Walther von Dyck, Dana Scott, Stephen Cook, Anil Nerode, Sheila Greibach (home page), Sheila Greibach (photo), Half-century of automata theory

The MacTutor History of Mathematics archive

** Welcome Page

The Mathematics Genealogy Project

** Home Page

Recent Paper Relevant to the Course Material

Deterministic Finite Automata with Recursive Calls and DPDA's (ps)
With Salvatore La Torre and Supratik Mukhopadyay
March 2003.

Relevant Fun Software

** Jflap

Back to Gallier Homepage

published by:

Jean Gallier