Elements of the Theory of Computation

Front Cover
Prentice-Hall, 1998 - Computers - 361 pages
This the Second Edition of Lewis and Papadimtriou'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. For example, long proofs have been simplified and/or truncated, with their more technical points delegated to exercises, advanced material is presented in an informal and friendly manner, and problems follow each section to check student comprehension. The book continues to comprise a mathematically sound introduction to the classical and contemporary theory of computation, and provide deep insights into the fundamental paradigms of computer science.

From inside the book

What people are saying - Write a review

LibraryThing Review

User Review  - bnielsen - LibraryThing

Indeholder "Preface", "Chapter 1. Sets, Relations and Languages", " 1.1 "If-Then" and its Relatives", " 1.2 Sets", " 1.3 Relations and Functions", " 1.4 Special Types of Binary Relations", " 1.5 ... Read full review

User Review - Flag as inappropriate

First edition is a great book, requiring discipline to master, but providing those who wish to be computer scientists a lifetime conceptual framework. No excuse for the dumb-downed version.


Finite Automata
Contextfree Languages

5 other sections not shown

Other editions - View all

Common terms and phrases

About the author (1998)

Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at the University of California, Berkeley and a member of the National Academy of Engineering and the American Academy of Arts and Sciences. He is the author of many books on computational theory.

Bibliographic information