Skip to main content Skip to main navigation
  1. Home
  2. Computer Science & IT
  3. Theory of Computation
  4. Automata
  5. Elements of the Theory of Computation

Elements of the Theory of Computation, 2nd edition

  • Harry Lewis
  • Christos H. Papadimitriou
Elements of the Theory of Computation

ISBN-13: 9780132624787

Includes: Paperback

2nd edition

Published byPearson (August 7th 1997) - Copyright © 1998

Free delivery
$186.65 $149.32
Free delivery
$186.65 $149.32

What's included

  • Paperback

    You'll get a bound printed text.


Lewis and Papadimitriou present this long awaited Second Edition of their best-selling theory of computation. The authors are well-known for their clear presentation that makes the material accessible to a a broad audience and requires no special previous mathematical experience. KEY TOPICS: In this new edition, the authors incorporate a somewhat more informal, friendly writing style to present both classical and contemporary theories of computation. Algorithms, complexity analysis, and algorithmic ideas are introduced informally in Chapter 1, and are pursued throughout the book. Each section is followed by problems.

Table of contents

1. Sets, Relations, and Languages.

2. Finite Automata.

3. Context-free Languages.

4. Turing Machines.

5. Undecidability.

6. Computational Complexity.

7. NP-completeness.


For teachers

All the material you need to teach your courses.

Discover teaching material