Introduction. PART 1: AUTOMATA AND LANGUAGES. 1. Regular Languages. 2. Context-Free Languages. PART 2: COMPUTABILITY THEORY. 3. The Church-Turing Thesis. 4. Decidability. 5. Reducibility. 6. Advanced Topics in Computability Theory. PART 3: COMPLEXITY THEORY. 7. Time Complexity. 8. Space Complexity. 9. Intractability. 10. Advanced Topics in Complexity Theory. Selected Bibliography.
Michael Sipser has taught theoretical computer science and mathematics at the Massachusetts Institute of Technology for the past 32 years. He is a Professor of Applied Mathematics, a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL), and the current head of the mathematics department. He enjoys teaching and pondering the many mysteries of complexity theory.
"As one of my students puts it, the book is 'fun to read and helps
him learn the subject better'."
"Excellent prose (simple and succinct) with very good diagrams. It
is by far the best presentation of automata in the business."
"The text meets my objectives very well. The author presents the
material in an appealing manner, making a hard subject accessible
and intuitive to the students. He manages to do that while
maintaining the rigor and formalism that the subject warrants. The
book has a lot of information packed in it, and can serve as a
reference book for students interested in research in theoretical
CS."
"This is a model for readability, with sensitivity for what
students find difficult."
|
Ask a Question About this Product More... |
|
