Enhanced descriptions from Syndetics:

Computability, Complexity, and Languages is an introductory text that 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.

Table of contents provided by Syndetics

• 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

Reviews provided by Syndetics

CHOICE Review

If there exists 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. The introductory chapter serves as a reference for those who lack the mathematical background. The remaining 17 chapters are organized into five parts: Part 1, on computability (seven chapters), covers the topic from its basics through the Halting Problem and culminates in a chapter on classifying unsolvable problems. Grammars and languages are the focus of the three very traditional chapters in Part 2. Part 3, "Logic", leads to the Incompleteness Theorem, while Part 4 (two chapters) leads to the NP-Complete Problem. The final section, "Semantics," (three chapters) treats orderings, denotational semantics, and operational semantics. Given the depth and breadth of coverage, the set of references is surprisingly brief, the only minor flaw in an otherwise outstanding book. Upper-division undergraduate; graduate. J. Beidler; University of Scranton

Author notes provided by Syndetics

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.