Introduction to the theory of computation
By: Michael Sipser.
Publisher: PWS Pub. Co.
Published: 1997
Place of publication: Boston
Language: eng
Number of pages: 396
Subjects: Machine theory; Computational complexity
Notes: Includes bibliographical references (p. 381-385) and index.
Table of contents: title: Preface
pagenum: xi; title: To the Student
pagenum: xi; title: To the Educator
pagenum: xii; title: The Current Edition
pagenum: xiii; title: Feedback to the Author; title: Acknowledgments
pagenum: xiv; label: 0
title: Introduction
pagenum: 1; label: 0.1
title: Automata, Computability, and Complexity
pagenum: 1; title: Complexity Theory
pagenum: 2; title: Computability Theory
pagenum: 2; title: Automata Theory
pagenum: 3; label: 0.2
title: Mathematical Notions and Terminology
pagenum: 3; title: Sets
pagenum: 3; title: Sequences and Tuples
pagenum: 6; title: Functions and Relations
pagenum: 7; title: Graphs
pagenum: 10; title: Strings and Languages
pagenum: 13; title: Boolean Logic
pagenum: 14; title: Summary of Mathematical Terms
pagenum: 16; label: 0.3
title: Definitions, Theorems, and Proofs
pagenum: 17; title: Finding Proofs
pagenum: 17; label: 0.4
title: Types of Proof
pagenum: 21; title: Proof by Construction
pagenum: 21; title: Proof by Contradiction
pagenum: 21; title: Proof by Induction
pagenum: 23; title: Exercises and Problems
pagenum: 25; label: Part One
title: Automata and Languages
pagenum: 29; label: 1
title: Regular Languages
pagenum: 31; label: 1.1
title: Finite Automata
pagenum: 31; title: Formal Definition of a Finite Automaton
pagenum: 35; title: Examples of Finite Automata
pagenum: 37; title: Formal Definition of Computation
pagenum: 40; title: Designing Finite Automata
pagenum: 41; title: The Regular Operations
pagenum: 44; label: 1.2
title: Nondeterminism
pagenum: 47; title: Formal Definition of a Nondeterministic Finite Automaton
pagenum: 53; title: Equivalence of NFAs and DFAs
pagenum: 54; title: Closure Under the Regular Operations
pagenum: 58; label: 1.3
title: Regular Expressions
pagenum: 63; title: Formal Definition of a Regular Expression
pagenum: 64; title: Equivalence with Finite Automata
pagenum: 66; label: 1.4
title: Nonregular Languages
pagenum: 77; title: The Pumping Lemma for Regular Languages
pagenum: 77; title: Exercises and Problems
pagenum: 83; label: 2
title: Context-Free Languages
pagenum: 91; label: 2.1
title: Context-Free Grammars
pagenum: 92; title: Formal Definition of a Context-Free Grammar
pagenum: 94; title: Examples of Context-Free Grammars
pagenum: 95; title: Designing Context-Free Grammars
pagenum: 96; title: Ambiguity
pagenum: 97; title: Chomsky Normal Form
pagenum: 98; label: 2.2
title: Pushdown Automata
pagenum: 101; title: Formal Definition of a Pushdown Automaton
pagenum: 103; title: Examples of Pushdown Automata
pagenum: 104; title: Equivalence with Context-Free Grammars
pagenum: 106; label: 2.3
title: Non-Context-Free Languages
pagenum: 115; title: The Pumping Lemma for Context-Free Languages
pagenum: 115; title: Exercises and Problems
pagenum: 119; label: Part Two
title: Computability Theory
pagenum: 123; label: 3
title: The Church–Turing Thesis
pagenum: 125; label: 3.1
title: Turing Machines
pagenum: 125; title: Formal Definition of a Turing Machine
pagenum: 127; title: Examples of Turing Machines
pagenum: 130; label: 3.2
title: Variants of Turing Machines
pagenum: 136; title: Multitape Turing Machines
pagenum: 136; title: Nondeterministic Turing Machines
pagenum: 138; title: Enumerators
pagenum: 140; title: Equivalence with Other Models
pagenum: 141; label: 3.3
title: The Definition of Algorithm
pagenum: 142; title: Hilbert's Problems
pagenum: 142; title: Terminology for Describing Turing Machines
pagenum: 144; title: Exercises and Problems
pagenum: 147; label: 4
title: Decidability
pagenum: 151; label: 4.1
title: Decidable Languages
pagenum: 152; title: Decidable Problems Concerning Regular Languages
pagenum: 152; title: Decidable Problems Concerning Context-Free Languages
pagenum: 156; label: 4.2
title: The Halting Problem
pagenum: 159; title: The Diagonalization Method
pagenum: 160; title: The Halting Problem Is Undecidable
pagenum: 165; title: A Turing-Unrecognizable Language
pagenum: 167; title: Exercises and Problems
pagenum: 168; label: 5
title: Reducibility
pagenum: 171; label: 5.1
title: Undecidable Problems from Language Theory
pagenum: 172; title: Reductions via Computation Histories
pagenum: 176; label: 5.2
title: A Simple Undecidable Problem
pagenum: 183; label: 5.3
title: Mapping Reducibility
pagenum: 189; title: Computable Functions
pagenum: 190; title: Formal Definition of Mapping Reducibility
pagenum: 191; title: Exercises and Problems
pagenum: 195; label: 6
title: Advanced Topics in Computability Theory
pagenum: 197; label: 6.1
title: The Recursion Theorem
pagenum: 197; title: Self-Reference
pagenum: 198; title: Terminology for the Recursion Theorem
pagenum: 201; title: Applications
pagenum: 202; label: 6.2
title: Decidability of Logical Theories
pagenum: 204; title: A Decidable Theory
pagenum: 206; title: An Undecidable Theory
pagenum: 209; label: 6.3
title: Turing Reducibility
pagenum: 211; label: 6.4
title: A Definition of Information
pagenum: 213; title: Minimal Length Descriptions
pagenum: 214; title: Optimality of the Definition
pagenum: 217; title: Incompressible Strings and Randomness
pagenum: 217; title: Exercises and Problems
pagenum: 220; label: Part Three
title: Complexity Theory
pagenum: 223; label: 7
title: Time Complexity
pagenum: 225; label: 7.1
title: Measuring Complexity
pagenum: 225; title: Big-O and Small-o Notation
pagenum: 226; title: Analyzing Algorithms
pagenum: 229; title: Complexity Relationships Among Models
pagenum: 231; label: 7.2
title: The Class P
pagenum: 234; title: Polynomial Time
pagenum: 234; title: Examples of Problems in P
pagenum: 236; label: 7.3
title: The Class NP
pagenum: 241; title: Examples of Problems in NP
pagenum: 245; title: The P Versus NP Question
pagenum: 247; label: 7.4
title: NP-Completeness
pagenum: 248; title: Polynomial Time Reducibility
pagenum: 249; title: Definition of NP-Completeness
pagenum: 253; title: The Cook–Levin Theorem
pagenum: 254; label: 7.5
title: Additional NP-Complete Problems
pagenum: 260; title: The Vertex Cover Problem
pagenum: 261; title: The Hamiltonian Path Problem
pagenum: 262; title: The Subset Sum Problem
pagenum: 268; title: Exercises and Problems
pagenum: 271; label: 8
title: Space Complexity
pagenum: 277; label: 8.1
title: Savitch's Theorem
pagenum: 279; label: 8.2
title: The Class PSPACE
pagenum: 281; label: 8.3
title: PSPACE-Completeness
pagenum: 283; title: The TQBF Problem
pagenum: 283; title: Winning Strategies for Games
pagenum: 287; title: Generalized Geography
pagenum: 289; label: 8.4
title: The Classes L and NL
pagenum: 294; label: 8.5
title: NL-Completeness
pagenum: 297; title: Searching in Graphs
pagenum: 298; label: 8.6
title: NL Equals coNL
pagenum: 300; title: Exercises and Problems
pagenum: 302; label: 9
title: Intractability
pagenum: 305; label: 9.1
title: Hierarchy Theorems
pagenum: 306; title: Exponential Space Completeness
pagenum: 313; label: 9.2
title: Relativization
pagenum: 318; title: Limits of the Diagonalization Method
pagenum: 319; label: 9.3
title: Circuit Complexity
pagenum: 321; title: Exercises and Problems
pagenum: 330; label: 10
title: Advanced Topics in Complexity Theory
pagenum: 333; label: 10.1
title: Approximation Algorithms
pagenum: 333; label: 10.2
title: Probabilistic Algorithms
pagenum: 335; title: The Class BPP
pagenum: 336; title: Primality
pagenum: 339; title: Read-Once Branching Programs
pagenum: 343; label: 10.3
title: Alternation
pagenum: 348; title: Alternating Time and Space
pagenum: 349; title: The Polynomial Time Hierarchy
pagenum: 353; label: 10.4
title: Interactive Proof Systems
pagenum: 354; title: Graph Nonisomorphism
pagenum: 355; title: Definition of the Model
pagenum: 355; title: IP = PSPACE
pagenum: 357; label: 10.5
title: Parallel Computation
pagenum: 366; title: Uniform Boolean Circuits
pagenum: 367; title: The Class NC
pagenum: 369; title: P-Completeness
pagenum: 371; label: 10.6
title: Cryptography
pagenum: 372; title: Secret Keys
pagenum: 372; title: Public-Key Cryptosystems
pagenum: 374; title: One-Way Functions
pagenum: 374; title: Trapdoor Functions
pagenum: 376; title: Exercises and Problems
pagenum: 378; title: Selected Bibliography
pagenum: 381; title: Index
pagenum: 387