Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science / Edition 2

Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science / Edition 2

5.0 4
by Martin Davis
     
 

ISBN-10: 0122063821

ISBN-13: 9780122063824

Pub. Date: 02/03/1994

Publisher: Elsevier Science

This introductory text covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability.

• Computability theory is introduced in a manner that

…  See more details below

Overview

This introductory text covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability.

• Computability theory is introduced in a manner that makes maximum use of previous programming experience, including a "universal" program that takes up less than a page.
• The number of exercises included has more than tripled.
• Automata theory, computational logic, and complexity theory are presented in a flexible manner, and can be covered in a variety of different arrangements.

Product Details

ISBN-13:
9780122063824
Publisher:
Elsevier Science
Publication date:
02/03/1994
Series:
Computer Science and Scientific Computing Series
Edition description:
REV
Pages:
609
Product dimensions:
1.56(w) x 6.00(h) x 9.00(d)

Table of Contents

Preliminaries. Computability: Programs and Computable Functions. Primitive Recursive Functions. A Universal Program. Calculations on Strings. Turing Machines. Processes and Grammars. Classifying Unsolvable Problems. Grammars and Automata: Regular Languages. Context-Free Languages. Context-Sensitive Languages. Logic: Propositional Calculus. Quantification Theory. Complexity: Abstract Complexity. Polynomial—Time Computability. Semantics: Approximation Orderings. Denotational Semantics of Recursion Equations. Operational Semantics of Recursion Equations. Suggestions for Further Reading. Subject Index.

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >

Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science 5 out of 5 based on 0 ratings. 4 reviews.
Guest More than 1 year ago
This is the best book available on theory of computation. It's 10 years old but certainly not dated. The writing is exceptionally clear, the problems very helpful. I have used it to teach both undergraduates and graduate students, and when a colleague asks for a pointer to this material, this is the book I always point them to.
Guest More than 1 year ago
I used this book as a student. It was my first introduction to the subject and it was easy to read and understand. The writing is clear, the examples helpful, and the exercises useful. I have now used this book to teach the subject, and there still isn't a book at that can match this one.
Guest More than 1 year ago
This book is really an excellent way of learning this complex topic. The authors' exposition is excellent and they also provide several different ways to use the book in courses. I have used it to teach both undergraduate and graduate students with great success.
Guest More than 1 year ago
Over the years, I have used many different texts to teach this material, and this is without a doubt the best book available. I've used it for both undergraduate courses and graduate courses with success. The authors provide several different chapter groups that can be used since the book is so comprehensive that you could not possibly cover all the material, even in a full-year course. The exposition is clear and full of examples.