CIS 511, Fall 2021
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
(pdf)
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)
-
Hidden Markov Models, in Speech and Language Processing,
by Jurafsky and Martin
(pdf)
-
A Revealing Introduction to Hidden Markov Models, by Mark Stamp
(pdf)
-
A Tutorial on Hidden Markov Models and
Selected Applications in Speech Rcognition, by L. Rabiner
(pdf)
-
HMM: Viterbi algorithm: a toy example (to predict DNA coding)
(pdf)
-
Slides by Bjorn Poonen (UPenn Rademacher Lecture 1, Fall 2017;
Undecidability in Number Theory)
(pdf)
-
Wines in the area around Beaune
(pdf)
Relevant Fun Software
Jflap
Back to
Gallier Homepage
published by: