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

Hardcover (Print)
Buy New
Buy New from BN.com
$72.95
Used and New from Other Sellers
Used and New from Other Sellers
from $13.35
Usually ships in 1-2 business days
(Save 81%)
Other sellers (Hardcover)
  • All (17) from $13.35   
  • New (6) from $43.77   
  • Used (11) from $13.35   

Overview

This book is a rigorous but readable introduction to some of the central topics in theoretical computer science. The main subjects are computability theory, formal languages, logic and automated deduction, computational complexity (including NP-completeness), and programming language semantics.

Audience: Junior, senior, and graduate level students in Computability, Complexity, and Languages or Introduction to Theoretical Computer Science courses.

Read More Show Less

Editorial Reviews

From the Publisher
"If there is a single book on the theory of computing that should be in every college library collection, this is it. Although written as a text for an advanced undergraduate course in theoretical computer science, the book may serve as an introductory resource, or the foundation for independent study, in many areas of theoretical computing: grammars, automata theory, computability, complexity theory, and unsolvability. The beauty of this book is that the breadth of coverage is complemented with extraordinary depth." —CHOICE

"Theoretical computer science is often viewed as a collection of disparate topics, including computability theory, formal language theory, complexity theory, logic, and so on. This well-written book attempts to unify the subject by introducing each of these topics in turn, then showing how they relate to each other... This is an excellent book that succeeds in tying together a number of areas in theoretical computer science." —COMPUTING REVIEWS

Booknews
A rigorous but readable introduction to some of the central topics in theoretical computer science, including computability theory, formal languages, logic and automated deduction, computational complexity including NP-completeness, and programming language semantics. This second edition features more than triple the exercises of the previous edition and a new discussion of computability theory; a section on the denotational and operational semantics of recursion equations has been added. Annotation c. Book News, Inc., Portland, OR (booknews.com)
Read More Show Less

Product Details

Meet the Author

Born in New York City in 1928, Martin Davis was a student of Emil L. Post at City College and his doctorate at Princeton in 1950 was under the supervision of Alonzo Church. Davis's book Computability and Unsolvability (1958) has been called "one of the few real classics in computer science." He is best known for his pioneering work in automated deduction and for his contributions to the solution of Hilbert's tenth problem. For this latter work he was awarded the Chauvenet and Lester R. Ford Prizes by the Mathematical Association of America and the Leroy P. Steele Prize by the American Mathematical Society. In 1983 he was a Guggenheim Foundation Fellow and in 2005 he received the Herbrand Prize from the Conference on Automated Deduction. His books have been translated into a number of languages including Russian and Japanese. Davis has been on the faculty of the Courant Institute of Mathematical Sciences of New York University since 1965, was one of the charter members of the Computer Science Department founded in 1969, and is now Professor Emeritus. He is currently a Visiting Scholar at the University of California, Berkeley.

Ron Sigal is an independently employed software developer who has held positions at Yale University, Lafayette College, Hofstra University, and the University of Catania in Italy. He has a PhD in computer science and has published in the areas of mathematical logic, robotics, and programming languages.

Elaine Weyuker is a researcher at AT&T Labs who specializes in empirical software engineering and testing research. She is a member of the National Academy of Engineering, an IEEE Fellow, an ACM Fellow, and an AT&T Fellow. She is the co-chair of the ACM Committee on Women in Computing (ACM-W) and a member of the Coalition to Diversify Computing's steering committee. She was the 2004 recipient of the Harlan D. Mills Award, the Rutgers University 50th Anniversary Outstanding Alumni Award, and the AT&T Chairman's Diversity Award. Before moving to AT&T, she was a computer science professor at the Courant Institute of Mathematical Sciences of NYU.

Read More Show Less

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.

Read More Show Less

Customer Reviews

Average Rating 5
( 4 )
Rating Distribution

5 Star

(4)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously
Sort by: Showing all of 4 Customer Reviews
  • Anonymous

    Posted September 8, 2005

    Excellent book

    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.

    Was this review helpful? Yes  No   Report this review
  • Anonymous

    Posted February 10, 2005

    Best Way to Learn Theory of Computation

    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.

    Was this review helpful? Yes  No   Report this review
  • Anonymous

    Posted October 25, 2004

    Best Theory of Computation Book on the Market

    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.

    Was this review helpful? Yes  No   Report this review
  • Anonymous

    Posted February 7, 2001

    a wonderful way to learn theory of computation

    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.

    Was this review helpful? Yes  No   Report this review
Sort by: Showing all of 4 Customer Reviews

If you find inappropriate content, please report it to Barnes & Noble
Why is this product inappropriate?
Comments (optional)