Elements of the Theory of Computation

Prentice Hall
Harry Lewis / Christos H. Papadimitriou  
Total pages
August 1997
Related Titles

Product detail

Product Price CHF Available  
Elements of the Theory of Computation
201.30 approx. 7-9 days


Appropriate for senior and graduate level courses in Computer Science Theory, Automata, and Theory of Computation.

This is the long awaited Second Edition of Lewis and Papadimitriou's best-selling theory of computation text. In this substantially modified edition, the authors have enhanced the clarity of their presentation by making the material more accessible to a broader undergraduate audience with no special mathematical experience.


  • Offers a mathematically sound introduction to the classical and contemporary theory of computation, and provide deep insights into the fundamental paradigms of computer science.

Would you like a theory of computation text that provides a solid, specialized introduction to algorithms?

  • Informally introduces algorithms, complexity analysis, and algorithmic ideas in Ch. 1 (in connection to transitive and other closures), and explores them throughout the book.
    • Introduces asymptotic analysis and O- notation.

  • Features a more “student-friendly” approach.
    • Truncates long proofs and presents them as exercises.

    • Provides problems after each section to check student comprehension.

  • Considers automata in the context of their applications.
    • Includes extensive discussion of state minimization, the Myhill-Nerode Theorem, string matching, and parsing.

  • Complexity starts with a proof that P = EXP.
    • Many combinatorial problems are introduced and analyzed (including variants of satisfiability), and their apparent complexity contrasted.

Would you like to teach NP-completeness, as well as ways of coping with it, in your course?

  • Features a separate chapter on NP-completeness.
    • Extensive section on coping with NP - completeness that covers special cases, approximation algorithms, backtracking, and local search heuristics.

    • Covers NP - completeness including state minimization problem of nondeterministic finite automata.

    • Logic coverage has been limited to propositional logic in relation to NP - completeness.

    • Considers Cook's Theorem again via the tiling problem.

    • Discusses approximation and its complexity.

  • Introduces the Turing machine notation more informally.
    • Uses the terms recursive and recursively innumerably.

    • Quantitatively analyzes simulations between machine models.

    • Introduces and analyzes a model of random access Turing machines, similar to RAMs.

  • Offers a more succinct treatment of general grammars and …¿¿-recursive functions.
    • Uses random access Turing machines to bridge the “credibility gap” between Turing machine model and the empirical concept of an algorithm.

    • Includes some recursion theory (up to Rice's theorem).

    • Provides an informal, concise development of A-recursive functions.

  • Explores Chomsky normal form and the resulting dynamic programming algorithm.

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.


Instructor Resources