Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science
- ISBN-10
- 1483264580
- ISBN-13
- 9781483264585
- Category
- Reference
- Pages
- 446
- Language
- English
- Published
- 2014-05-10
- Publisher
- Academic Press
- Authors
- Martin D. Davis, Elaine J. Weyuker
Description
Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science provides an introduction to the various aspects of theoretical computer science. Theoretical computer science is the mathematical study of models of computation. This text is composed of five parts encompassing 17 chapters, and begins with an introduction to the use of proofs in mathematics and the development of computability theory in the context of an extremely simple abstract programming language. The succeeding parts demonstrate the performance of abstract programming language using a macro expansion technique, along with presentations of the regular and context-free languages. Other parts deal with the aspects of logic that are important for computer science and the important theory of computational complexity, as well as the theory of NP-completeness. The closing part introduces the advanced recursion and polynomial-time computability theories, including the priority constructions for recursively enumerable Turing degrees. This book is intended primarily for undergraduate and graduate mathematics students.
Get the book
Other editions
-
- 1994
- 609 pages
- Paperback
- Academic Press
-
- 1994-03-18
- 609 pages
- Ebook
- Elsevier
Similar books
-
Computability and Complexity: From a Programming Perspective
By Neil D. JonesNew results in the book include a proof that constant time factors do matter for its programming-oriented model of computation. (In contrast, Turing machines have a counterintuitive "constant speedup" property: that almost any program can ...
-
Computability and Complexity Theory
By Steven Homer, Alan L. SelmanSubstantial new content in this edition includes: a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of Karp─Lipton. a chapter studying properties of the fundamental probabilistic complexity ...
-
Automata, Computability and Complexity: Theory and Applications
By Elaine RichFor upper level courses on Automata.
-
Computability and Unsolvability
By Martin DavisClassic graduate-level introduction to theory of computability.
-
Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography
By Juraj HromkovičThe book also presents the development of the computer scientist's way of thinking as well as fundamental concepts such as approximation and randomization in algorithmics, and the basic ideas of cryptography and interconnection network ...
-
Computability, Complexity, Logic
By E. BörgerThe theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning, facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for ...
-
Computational Complexity: A Modern Approach
By Sanjeev Arora, Boaz BarakNew and classical results in computational complexity, including interactive proofs, PCP, derandomization, and quantum computation. Ideal for graduate students.
-
Introduction to the Theory of Computation
By Michael Sipser"Intended as an upper-level undergraduate or introductory graduate text in computer science theory," this book lucidly covers the key concepts and theorems of the theory of computation.
-
Elements of Computation Theory
By Arindama SinghIt has thus become more than a necessity to revisit the foundation, learn the techniques, and apply them with con?dence. Overview and Goals This book is about this solid, beautiful, and pervasive foundation of computer s- ence.
-
Algorithmic Randomness and Complexity
By Denis R. Hirschfeldt, Rodney G. DowneyTheorem 2.18.5 (Yates [410], Cooper [76]). Every nonzero c.e. degree bounds a minimal degree. In particular, there are minimal degrees below 0 (which was first shown by Sacks [342]), and hence hyperimmune minimal degrees.