Note: Supplemental materials are not guaranteed with Rental or Used book purchases.
Purchase Benefits
What is included with this book?
Preface to the First Edition | p. xi |
To the student | p. xi |
To the educator | p. xii |
The first edition | p. xiii |
Feedback to the author | p. xiii |
Acknowledgments | p. xiv |
Preface to the Second Edition | p. xvii |
Preface to the Third Edition | p. xxi |
Introduction | p. 1 |
Automata, Computability, and Complexity | p. 1 |
Complexity theory | p. 2 |
Computability theory | p. 3 |
Automata theory | p. 3 |
Mathematical Notions and Terminology | p. 3 |
Sets | p. 3 |
Sequences and tuples | p. 6 |
Functions and relations | p. 7 |
Graphs | p. 10 |
Strings and languages | p. 13 |
Boolean logic | p. 14 |
Summary of mathematical terms | p. 16 |
Definitions, Theorems, and Proofs | p. 17 |
Finding proofs | p. 17 |
Types of Proof | p. 21 |
Proof by construction | p. 21 |
Proof by contradiction | p. 21 |
Proof by induction | p. 22 |
Exercises, Problems, and Solutions | p. 25 |
Automata and Languages | p. 29 |
Regular Languages | p. 31 |
Finite Automata | p. 31 |
Formal definition of a finite automaton | p. 35 |
Examples of finite automata | p. 37 |
Formal definition of computation | p. 40 |
Designing finite automata | p. 41 |
The regular operations | p. 44 |
Nondeterminism | p. 47 |
Formal definition of a nondeterministic finite automaton | p. 53 |
Equivalence of NFAs and DFAs | p. 54 |
Closure under the regular operations | p. 58 |
Regular Expressions | p. 63 |
Formal definition of a regular expression | p. 64 |
Equivalence with finite automata | p. 66 |
Nonregular Languages | p. 77 |
The pumping lemma for regular languages | p. 77 |
Exercises, Problems, and Solutions | p. 82 |
Context-Free Languages | p. 101 |
Context-Free Grammars | p. 102 |
Formal definition of a context-free grammar | p. 104 |
Examples of context-free grammars | p. 105 |
Designing context-free grammars | p. 106 |
Ambiguity | p. 107 |
Chomsky normal form | p. 108 |
Pushdown Automata | p. 111 |
Formal definition of a pushdown automaton | p. 113 |
Examples of pushdown automata | p. 114 |
Equivalence with context-free grammars | p. 117 |
Non-Context-Free Languages | p. 125 |
The pumping lemma for context-free languages | p. 125 |
Deterministic Context-Free Languages | p. 130 |
Properties of DCFLs | p. 133 |
Deterministic context-free grammars | p. 135 |
Relationship of DPDAs and DCFGs | p. 146 |
Parsing and LR(k) Grammars | p. 151 |
Exercises, Problems, and Solutions | p. 154 |
Computability Theory | p. 163 |
The Church-Turing Thesis | p. 165 |
Turing Machines | p. 165 |
Formal definition of a Turing machine | p. 167 |
Examples of Turing machines | p. 170 |
Variants of Turing Machines | p. 176 |
Multitape Turing machines | p. 176 |
Nondeterministic Turing machines | p. 178 |
Enumerators | p. 180 |
Equivalence with other models | p. 181 |
The Definition of Algorithm | p. 182 |
Hilbert's problems | p. 182 |
Terminology for describing Turing machines | p. 184 |
Exercises, Problems, and Solutions | p. 187 |
Decidability | p. 193 |
Decidable Languages | p. 194 |
Decidable problems concerning regular languages | p. 194 |
Decidable problems concerning context-free languages | p. 198 |
Undecidability | p. 201 |
The diagonalization method | p. 202 |
An undecidable language | p. 207 |
A Turing-unrecognizable language | p. 209 |
Exercises, Problems, and Solutions | p. 210 |
Reducibility | p. 215 |
Undecidable Problems from Language Theory | p. 216 |
Reductions via computation histories | p. 220 |
A Simple Undecidable Problem | p. 227 |
Mapping Reducibility | p. 234 |
Computable functions | p. 234 |
Formal definition of mapping reducibility | p. 235 |
Exercises, Problems, and Solutions | p. 239 |
Advanced Topics in Computability Theory | p. 245 |
The Recursion Theorem | p. 245 |
Self-reference | p. 246 |
Terminology for the recursion theorem | p. 249 |
Applications | p. 250 |
Decidability of logical theories | p. 252 |
A decidable theory | p. 255 |
An undecidable theory | p. 257 |
Turing Reducibility | p. 260 |
A Definition of Information | p. 261 |
Minimal length descriptions | p. 262 |
Optimality of the definition | p. 266 |
Incompressible strings and randomness | p. 267 |
Exercises, Problems, and Solutions | p. 270 |
Complexity Theory | p. 273 |
Time Complexity | p. 275 |
Measuring Complexity | p. 275 |
Big-O and small-o notation | p. 276 |
Analyzing algorithms | p. 279 |
Complexity relationships among models | p. 282 |
The Class P | p. 284 |
Polynomial time | p. 284 |
Examples of problems in P | p. 286 |
The Class NP | p. 292 |
Examples of problems in NP | p. 295 |
The P versus NP question | p. 297 |
NP-completeness | p. 299 |
Polynomial time reducibility | p. 300 |
Definition of NP-completeness | p. 304 |
The Cook-Levin Theorem | p. 304 |
Additional NP-complete Problems | p. 311 |
The vertex cover problem | p. 312 |
The Hamiltonian path problem | p. 314 |
The subset sum problem | p. 319 |
Exercises, Problems, arid Solutions | p. 322 |
Space Complexity | p. 331 |
SavitchÆs Theorem | p. 333 |
The Class PSPACE | p. 336 |
PSPACE-completeness | p. 337 |
The TQBF problem | p. 338 |
Winning strategies for games | p. 341 |
Generalized geography | p. 343 |
The Classes L and NL | p. 348 |
NL-completeness | p. 351 |
Searching in graphs | p. 353 |
NL equals coNL | p. 354 |
Exercises, Problems, and Solutions | p. 356 |
Intractability | p. 363 |
Hierarchy Theorems | p. 364 |
Exponential space completeness | p. 371 |
Relativization | p. 376 |
Limits of the diagonalization method | p. 377 |
Circuit Complexity | p. 379 |
Exercises, Problems, and Solutions | p. 388 |
Advanced Topics in Complexity Theory | p. 393 |
Approximation Algorithms | p. 393 |
Probabilistic Algorithms | p. 395 |
The class BPP | p. 395 |
Primality | p. 399 |
Read-once branching programs | p. 404 |
Alternation | p. 408 |
Alternating time and space | p. 410 |
The Polynomial time hierarchy | p. 414 |
Interactive Proof Systems | p. 415 |
Graph nonisomorphism | p. 415 |
Definition of the model | p. 415 |
IP = PSPACE | p. 418 |
Parallel Computation | p. 427 |
Uniform Boolean circuits | p. 428 |
The class NC | p. 430 |
P-completeness | p. 432 |
Cryptography | p. 433 |
Secret keys | p. 433 |
Public-key cryptosystems | p. 435 |
One-way functions | p. 435 |
Trapdoor functions | p. 437 |
Exercises, Problems, and Solutions | p. 439 |
Selected Bibliography | p. 443 |
Index | p. 448 |
Table of Contents provided by Ingram. All Rights Reserved. |