Models of Computation: Exploring the Power of Computing

Book Description:

The focus of this book is on finite problems and concrete computational models. It covers the traditional topics of formal languages, automata and complexity classes, as well as an introduction to the more modern topics of space-time tradeoffs, memory hierarchies, parallel computation, the VLSI model, and circuit complexity. These topics are integrated throughout the book as illustrated by the early introduction of P-complete and NP-complete problems. Models of Computation provides the first textbook treatment of space-time tradeoffs and memory hierarchies. It gives a comprehensive introduction to computational complexity as well as a brief but modern coverage of circuit complexity. Parallelism is integrated throughout the book.

 

Models of Computation: Exploring the Power of Computing

I. Overview of the Book

Preface

Chapter 1: The Role of Theory in Computer Science

II. General Computational Models

Chapter 2: Logic Circuits

Chapter 3: Machines with Memory

Chapter 4: Finite-State Machines and Pushdown Automata

Chapter 5: Computability

Chapter 6: Algebraic and Combinatorial Circuits

Chapter 7: Parallel Computation

III. Computational Complexity

Chapter 8: Complexity Classes

Chapter 9: Circuit Complexity

Chapter 10: Space-Time Tradeoffs

Chapter 11: Memory-Hierarchy Tradeoffs

Chapter 12: VLSI Models of Computation

Bibliography

Index