CIS 511, 2014

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

The MacTutor History of Mathematics archive

The Mathematics Genealogy Project

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.

• Faster Algorithms for Frobenius Numbers
  D. Beihoffer, J. Hendry, A. Nijenhuis, S. Wagon (pdf)

• The Frobenius Coin Problem. Upper Bounds on the Frobenius Number
  J. Gallier (pdf)

Relevant Fun Software

Back to Gallier Homepage

published by:

Jean Gallier