+612 9045 4394
Computability, Complexity, and Languages : Fundamentals of Theoretical Computer Science - Martin Davis

Computability, Complexity, and Languages

Fundamentals of Theoretical Computer Science


Published: 3rd February 1994
Ships: 7 to 10 business days
7 to 10 business days
RRP $224.99
or 4 easy payments of $38.94 with Learn more

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.

"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

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
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9780122063824
ISBN-10: 0122063821
Series: Computer Science & Scientific Computing
Audience: Professional
Format: Hardcover
Language: English
Number Of Pages: 609
Published: 3rd February 1994
Country of Publication: US
Dimensions (cm): 23.52 x 16.36  x 4.75
Weight (kg): 1.1
Edition Number: 2
Edition Type: Revised