Description

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.

Features

• 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.


Index.