Introduction to automata theory, languages, and computation
Publisher: Pearson/Addison-Wesley; Pearson/Addison Wesley
Published: 2007
Place of publication: USA
Language: eng
Format: Hardcover
Number of pages: 535
Copyright date: 2007
Description: "This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with increased coverage of practical applications. This third edition offers students a less formal writing style while providing the most accessible coverage of automata theory available, solid treatment on constructing proofs, many figures and diagrams to help convey ideas, and sidebars to highlight related material. A new feature of this edition is Gradiance, a Web-based homework and assessment tool. Each chapter offers an abundance of exercises, including selected Gradiance problems, for a true hands-on learning experience for students."--BOOK JACKET.
Table of contents: label: 1
title: Automata: The Methods and the Madness
pagenum: 1; label: 1.1
title: Why Study Automata Theory
pagenum: 2; label: 1.1.1
title: Introduction to Finite Automata
pagenum: 2; label: 1.1.2
title: Structural Representations
pagenum: 4; label: 1.1.3
title: Automata and Complexity
pagenum: 5; label: 1.2
title: Introduction to Formal Proof
pagenum: 5; label: 1.2.1
title: Deductive Proofs
pagenum: 6; label: 1.2.2
title: Reduction to Definitions
pagenum: 8; label: 1.2.3
title: Other Theorem Forms
pagenum: 10; label: 1.2.4
title: Theorems That Appear Not to Be If-Then Statements
pagenum: 13; label: 1.3
title: Additional Forms of Proof
pagenum: 13; label: 1.3.1
title: Proving Equivalences About Sets
pagenum: 14; label: 1.3.2
title: The Contrapositive
pagenum: 14; label: 1.3.3
title: Proof by Contradiction
pagenum: 16; label: 1.3.4
title: Counterexamples
pagenum: 17; label: 1.4
title: Inductive Proofs
pagenum: 19; label: 1.4.1
title: Induction on Integers
pagenum: 19; label: 1.4.2
title: More General Forms of Integer Inductions
pagenum: 22; label: 1.4.3
title: Structural Inductions
pagenum: 23; label: 1.4.4
title: Mutual Inductions
pagenum: 26; label: 1.5
title: The Central Concepts of Automata Theory
pagenum: 28; label: 1.5.1
title: Alphabets
pagenum: 28; label: 1.5.2
title: Strings
pagenum: 29; label: 1.5.3
title: Languages
pagenum: 30; label: 1.5.4
title: Problems
pagenum: 31; label: 1.6
title: Summary of Chapter 1
pagenum: 33; label: 1.7
title: Gradiance Problems for Chapter 1
pagenum: 35; label: 1.8
title: References for Chapter 1
pagenum: 36; label: 2
title: Finite Automata
pagenum: 37; label: 2.1
title: An Informal Picture of Finite Automata
pagenum: 38; label: 2.1.1
title: The Ground Rules
pagenum: 38; label: 2.1.2
title: The Protocol
pagenum: 39; label: 2.1.3
title: Enabling the Automata to Ignore Actions
pagenum: 41; label: 2.1.4
title: The Entire System as an Automaton
pagenum: 43; label: 2.1.5
title: Using the Product Automaton to Validate the Protocol
pagenum: 44; label: 2.2
title: Deterministic Finite Automata
pagenum: 45; label: 2.2.1
title: Definition of a Deterministic Finite Automoton
pagenum: 45; label: 2.2.2
title: How a DFA Processes Strings
pagenum: 46; label: 2.2.3
title: Simpler Notations for DFA's
pagenum: 47; label: 2.2.4
title: Extending the Transition Function to Strings
pagenum: 49; label: 2.2.5
title: The Language of a DFA
pagenum: 52; label: 2.2.6
title: Exercises for Section 2.2
pagenum: 52; label: 2.3
title: Nondeterministic Finite Automata
pagenum: 55; label: 2.3.1
title: An Informal View of Nondeterministic Finite Automata
pagenum: 55; label: 2.3.2
title: Definition of Nondeterministic Finite Automata
pagenum: 57; label: 2.3.3
title: The Extended Transition Function
pagenum: 58; label: 2.3.4
title: The Language of an NFA
pagenum: 59; label: 2.3.5
title: Equivalence of Deterministic and Nondeterministic Finite Automata
pagenum: 60; label: 2.3.6
title: A Bad Case for the Subset Construction
pagenum: 64; label: 2.3.7
title: Exercises for Section 2.3
pagenum: 65; label: 2.4
title: An Application: Text Search
pagenum: 68; label: 2.4.1
title: Finding Strings in Text
pagenum: 68; label: 2.4.2
title: Nondeterministic Finite Automata for Text Search
pagenum: 69; label: 2.4.3
title: A DFA to Recognize a Set of Keywords
pagenum: 70; label: 2.4.4
title: Exercises for Section 2.4
pagenum: 71; label: 2.5
title: Finite Automata With EpsilonTransitions
pagenum: 72; label: 2.5.1
title: Uses of ϵ-Transitions
pagenum: 72; label: 2.5.2
title: The Formal Notation for an ϵ-NFA
pagenum: 73; label: 2.5.3
title: Epsilon-Closures
pagenum: 74; label: 2.5.4
title: Extended Transitions and Languages for ϵ-NFA's
pagenum: 75; label: 2.5.5
title: Eliminationg ϵ-Transitions
pagenum: 77; label: 2.5.6
title: Exercises for Section 2.5
pagenum: 79; label: 2.6
title: Summary of Chapter 2
pagenum: 80; label: 2.7
title: Gradiance Problems for Chapter 2
pagenum: 80; label: 2.8
title: References for Chapter 2
pagenum: 83; label: 3
title: Regular Expressions and Languages
pagenum: 85; label: 3.1
title: Regular Expressions
pagenum: 85; label: 3.1.1
title: The Operators of Regular Expressions
pagenum: 86; label: 3.1.2
title: Bulding Regular Expressions
pagenum: 87; label: 3.1.3
title: Precedence of Regular-Expression Operators
pagenum: 90; label: 3.1.4
title: Exercises for Section 3.1
pagenum: 91; label: 3.2
title: Finite Automata and Regular Expressions
pagenum: 92; label: 3.2.1
title: From DFA's to Regular Expressions
pagenum: 93; label: 3.2.2
title: Converting DFA's to Regular Expressions by Eliminating States
pagenum: 98; label: 3.2.3
title: Converting Regular Expressions to Automata
pagenum: 102; label: 3.2.4
title: Exercises for Section 3.2
pagenum: 107; label: 3.3
title: Applications of Regular Expressions
pagenum: 109; label: 3.3.1
title: Regular Expressions in UNIX
pagenum: 109; label: 3.3.2
title: Lexical Analysis
pagenum: 110; label: 3.3.3
title: Finding Patterns in Text
pagenum: 112; label: 3.3.4
title: Exercises for Section 3.3
pagenum: 114; label: 3.4
title: Algebraic Laws for Regular Expressions
pagenum: 115; label: 3.4.1
title: Associativity and Commutativity
pagenum: 115; label: 3.4.2
title: Identities and Annihilators
pagenum: 116; label: 3.4.3
title: Distributive Laws
pagenum: 116; label: 3.4.4
title: The Idempotent Laws
pagenum: 117; label: 3.4.5
title: Laws Involving Closures
pagenum: 118; label: 3.4.6
title: Discovering Laws for Regular Expressions
pagenum: 118; label: 3.4.7
title: The Test for a Regular-Expression Algebraic Law
pagenum: 120; label: 3.4.8
title: Exercises for Section 3.4
pagenum: 121; label: 3.5
title: Summary of Chapter 3
pagenum: 123; label: 3.6
title: Gradiance Problems for Chapter 3
pagenum: 123; label: 3.7
title: References for Chapter 3
pagenum: 125; label: 4
title: Properties of Regular Languages
pagenum: 127; label: 4.1
title: Proving Languages Not to Be Regular
pagenum: 128; label: 4.1.1
title: The Pumping Lemma for Regular Languages
pagenum: 128; label: 4.1.2
title: Applications of the Pumping Lemma
pagenum: 129; label: 4.1.3
title: Exercises for Section 4.1
pagenum: 131; label: 4.2
title: Closure Properties of Regular Languages
pagenum: 133; label: 4.2.1
title: Closure of Regular Languages Under Boolean Operations
pagenum: 133; label: 4.2.2
title: Reversal
pagenum: 139; label: 4.2.3
title: Homomorphisms
pagenum: 140; label: 4.2.4
title: Inverse Homomorphisms
pagenum: 142; label: 4.2.5
title: Exercises for Section 4.2
pagenum: 147; label: 4.3
title: Decision Properties of Regular Languages
pagenum: 150; label: 4.3.1
title: Converting Among Representations
pagenum: 151; label: 4.3.2
title: Testing Emptiness of Regular Languages
pagenum: 153; label: 4.3.3
title: Testing Membership in a Regular Language
pagenum: 154; label: 4.3.4
title: Exercises for Section 4.3
pagenum: 155; label: 4.4
title: Equivalence and Minimization of Automata
pagenum: 155; label: 4.4.1
title: Testing Equivalence of States
pagenum: 155; label: 4.4.2
title: Testing Equivalence of Regular Languages
pagenum: 159; label: 4.4.3
title: Minimization of DFA's
pagenum: 160; label: 4.4.4
title: Why the Minimized DFA Can't Be Beaten
pagenum: 163; label: 4.4.5
title: Exercises for Section 4.4
pagenum: 165; label: 4.5
title: Summary of Chapter 4
pagenum: 166; label: 4.6
title: Gradiance Problems for Chapter 4
pagenum: 167; label: 4.7
title: References for Chapter 4
pagenum: 169; label: 5
title: Context-Free Grammars and Languages
pagenum: 171; label: 5.1
title: Context-Free Grammars
pagenum: 171; label: 5.1.1
title: An Informal Example
pagenum: 172; label: 5.1.2
title: Definition of Context-Free Grammars
pagenum: 173; label: 5.1.3
title: Derivations Using a Grammar
pagenum: 175; label: 5.1.4
title: Leftmost and Rightmost Derivations
pagenum: 177; label: 5.1.5
title: The Language of a Grammar
pagenum: 179; label: 5.1.6
title: Sentential Forms
pagenum: 180; label: 5.1.7
title: Exercises for Section 5.1
pagenum: 181; label: 5.2
title: Parse Trees
pagenum: 183; label: 5.2.1
title: Constructing Parse Trees
pagenum: 183; label: 5.2.2
title: The Yield of a Parse Tree
pagenum: 185; label: 5.2.3
title: Inference, Derivations, and Parse Trees
pagenum: 185; label: 5.2.4
title: From Inferences to Trees
pagenum: 187; label: 5.2.5
title: From Trees to Derivations
pagenum: 188; label: 5.2.6
title: From Derivations to Recursive Inferences
pagenum: 191; label: 5.2.7
title: Exercises for sectino 5.2
pagenum: 193; label: 5.3
title: Applications of Context-Free Grammars
pagenum: 193; label: 5.3.1
title: Parsers
pagenum: 194; label: 5.3.2
title: The YACC Parser-Generator
pagenum: 196; label: 5.3.3
title: Markup Languages
pagenum: 197; label: 5.3.4
title: XML and Document-Type Definitions
pagenum: 200; label: 5.3.5
title: Exercises for Section 5.3
pagenum: 206; label: 5.4
title: Ambiguity in Grammars and Languages
pagenum: 207; label: 5.4.1
title: Ambiguous Grammars
pagenum: 207; label: 5.4.2
title: Removing Ambiguity From Grammars
pagenum: 209; label: 5.4.3
title: Leftmost Derivations as a Way to Express Ambiguity
pagenum: 212; label: 5.4.4
title: Inherent Ambiguity
pagenum: 213; label: 5.4.5
title: Exercises for Section 5.4
pagenum: 215; label: 5.5
title: Summary of Chapter 5
pagenum: 216; label: 5.6
title: Gradiance Problems for Chapter 5
pagenum: 218; label: 5.7
title: References for Chapter 5
pagenum: 224; label: 6
title: Pushdown Automata
pagenum: 225; label: 6.1
title: Definition of the Pushdown Automaton
pagenum: 225; label: 6.1.1
title: Informal Introduction
pagenum: 225; label: 6.1.2
title: The Formal Definition of Pushdown Automata
pagenum: 227; label: 6.1.3
title: A Graphical Notation for PDA's
pagenum: 229; label: 6.1.4
title: Instantaneous Descriptions of a PDA
pagenum: 230; label: 6.1.5
title: Exercises for Section 6.1
pagenum: 233; label: 6.2
title: The Languages of a PDA
pagenum: 234; label: 6.2.1
title: Acceptance by Final State
pagenum: 235; label: 6.2.1
title: Acceptance by Empty Stack
pagenum: 236; label: 6.2.1
title: From Empty Stack to Final State
pagenum: 237; label: 6.2.1
title: From Final State to Empty Stack
pagenum: 240; label: 6.2.1
title: Exercises for Section 6.2
pagenum: 241; label: 6.3
title: Equivalence of PDA's and CFG's
pagenum: 243; label: 6.3.1
title: From Grammars to Pushdown Automata
pagenum: 243; label: 6.3.2
title: From PDA's to Grammars
pagenum: 247; label: 6.3.3
title: Exercises for Section 6.3
pagenum: 251; label: 6.4
title: Deterministic Pushdown Automata
pagenum: 252; label: 6.4.1
title: Definition of a Deterministic PDA
pagenum: 252; label: 6.4.2
title: Regular Languages and Deterministic PDA's
pagenum: 253; label: 6.4.3
title: DPDA's and Context-Free Languages
pagenum: 254; label: 6.4.4
title: DPDA's and Ambiguous Grammars
pagenum: 255; label: 6.4.5
title: Exercises for Section 6.4
pagenum: 256; label: 6.5
title: Summary of Chapter 6
pagenum: 257; label: 6.6
title: Gradiance Problems for Chapter 6
pagenum: 258; label: 6.7
title: References for Chapter 6
pagenum: 260; label: 7
title: Properties of Context-Free Languages
pagenum: 261; label: 7.1
title: Normal Forms for Context-Free Grammars
pagenum: 261; label: 7.1.1
title: Eliminating Useless Symbols
pagenum: 263; label: 7.1.2
title: Computing the Generating and Reachable Symbols
pagenum: 264; label: 7.1.3
title: Eliminating ϵ-Productions
pagenum: 265; label: 7.1.4
title: Eliminating Unit Productions
pagenum: 268; label: 7.1.5
title: Chomsky Normal Form
pagenum: 272; label: 7.1.1
title: Exercises For Section 7.1
pagenum: 275; label: 7.2
title: The Pumping Lemma for Context-Free Languages
pagenum: 179; label: 7.2.1
title: The Size of Parse Trees
pagenum: 280; label: 7.2.2
title: Statement of the Pumping Lemma
pagenum: 280; label: 7.2.3
title: Applications of the Pumping Lemma for CFL's
pagenum: 283; label: 7.2.4
title: Exercises for Section 7.2
pagenum: 286; label: 7.3
title: Closure Properties of Context-Free Languages
pagenum: 287; label: 7.3.1
title: Substitutions
pagenum: 287; label: 7.3.2
title: Applications of the Substitution Theorem
pagenum: 289; label: 7.3.3
title: Reversal
pagenum: 290; label: 7.3.4
title: Intersection With a Regular language
pagenum: 291; label: 7.3.5
title: Inverse Homomorphism
pagenum: 295; label: 7.3.6
title: Exercises for Section 7.3
pagenum: 297; label: 7.4
title: Decision Properties of CFL's
pagenum: 299; label: 7.4.1
title: Complexity of Converting Among CFG's and PDA's
pagenum: 299; label: 7.4.2
title: Running Time of Conversion to Chomsky Normal Form
pagenum: 301; label: 7.4.3
title: Testing Emptiness of CFL's
pagenum: 302; label: 7.4.4
title: Testing Membership in a CFL
pagenum: 303; label: 7.4.5
title: Preview of Undecidable CFL Problems
pagenum: 307; label: 7.4.6
title: Exercises for Section 7.4
pagenum: 307; label: 7.5
title: Summary of Chapter 7
pagenum: 308; label: 7.6
title: Gradiance Problems for Chapter 7
pagenum: 309; label: 7.7
title: References for Chapter 7
pagenum: 314; label: 8
title: Introduction to Turing Machines
pagenum: 315; label: 8.1
title: Problems That Computers Cannot Solve
pagenum: 315; label: 8.1.1
title: Programs that Print "Hello, World"
pagenum: 316; label: 8.1.2
title: The Hypothetical "Hello, World" Tester
pagenum: 318; label: 8.1.3
title: Reducing One Problem to Another
pagenum: 321; label: 8.1.4
title: Exercises for Section 8.1
pagenum: 324; label: 8.2
title: The Turing Machine
pagenum: 324; label: 8.2.1
title: The Quest to Decide All Mathematical Questions
pagenum: 325; label: 8.2.2
title: Notation for the Turing Machine
pagenum: 326; label: 8.2.3
title: Instantaneous Descriptions for Turing Machines
pagenum: 327; label: 8.2.4
title: Transition Diagrams for Turing Machines
pagenum: 331; label: 8.2.5
title: The Language of a Turing Machine
pagenum: 334; label: 8.2.6
title: Turing Machines and Halting
pagenum: 334; label: 8.2.7
title: Exercises for Section 8.2
pagenum: 335; label: 8.3
title: Programming Techniques for Turing Machines
pagenum: 337; label: 8.3.1
title: Storage in the State
pagenum: 337; label: 8.3.2
title: Multiple Tracks
pagenum: 339; label: 8.3.3
title: Subroutines
pagenum: 341; label: 8.3.4
title: Exercises for Section 8.3
pagenum: 343; label: 8.4
title: Extensions to the Basic Turing Machine
pagenum: 343; label: 8.4.1
title: Multitape Turing Machines
pagenum: 344; label: 8.4.2
title: Equivalence of One-Tape and Multitape TM's
pagenum: 345; label: 8.4.3
title: Running Time and the Many-Tapes-to-One Construction
pagenum: 346; label: 8.4.4
title: Nondeterministic Turing Machines
pagenum: 347; label: 8.4.5
title: Exercises for Section 8.4
pagenum: 349; label: 8.5
title: Restricted Turing Machines
pagenum: 352; label: 8.5.1
title: Turing Machines with Semi-infinite Tapes
pagenum: 352; label: 8.5.2
title: Multistack Machines
pagenum: 355; label: 8.5.3
title: Counter Machines
pagenum: 358; label: 8.5.4
title: The Power of Counter Machines
pagenum: 359; label: 8.5.5
title: Exercises for Section 8.5
pagenum: 361; label: 8.6
title: Turing Machines and Computers
pagenum: 362; label: 8.6.1
title: Simulating a Turing Machine by Computer
pagenum: 362; label: 8.6.2
title: Simulating a Computer by a Turing Machine
pagenum: 363; label: 8.6.3
title: Comparing the Running Times of Computers and Turing Machines
pagenum: 368; label: 8.7
title: Summary of Chapter 8
pagenum: 370; label: 8.8
title: Gradiance Problems for Chapter 8
pagenum: 372; label: 8.9
title: References for Chapter 8
pagenum: 374; label: 9
title: Undecidability
pagenum: 377; label: 9.1
title: A Language That Is Not Recursively Enumerable
pagenum: 378; label: 9.1.1
title: Enumerating the Binary Strings
pagenum: 379; label: 9.1.2
title: Codes for Turing Machines
pagenum: 379; label: 9.1.3
title: The Diagonalization Language
pagenum: 380; label: 9.1.4
title: Proof that L[d]XXX Is Not Recursively Enumerable
pagenum: 382; label: 9.1.5
title: Exercises for Section 9.1
pagenum: 382; label: 9.2
title: An Undecidable Problem That Is RE
pagenum: 383; label: 9.2.1
title: Recursive Languages
pagenum: 383; label: 9.2.2
title: Complements of Recursive and RE languages
pagenum: 384; label: 9.2.3
title: The Universal Language
pagenum: 387; label: 9.2.4
title: Undecidability of the Universal Language
pagenum: 389; label: 9.2.5
title: Exercises for Section 9.2
pagenum: 390; label: 9.3
title: Undecidable Problems About Turing Machines
pagenum: 392; label: 9.3.1
title: Reductions
pagenum: 392; label: 9.3.2
title: Turing Machines That Accept the Empty Language
pagenum: 394; label: 9.3.3
title: Rice's Theorem and Properties of the RE Languages
pagenum: 397; label: 9.3.4
title: Problems and Turing-Machine Specifications
pagenum: 399; label: 9.3.5
title: Exercises for Section 9.3
pagenum: 400; label: 9.4
title: Post's Correspondence Problem
pagenum: 401; label: 9.4.1
title: Definition of Post's Correspondence Problem
pagenum: 401; label: 9.4.2
title: The "Modified" PCP
pagenum: 404; label: 9.4.3
title: Completion of the Proof of PCP Undecidability
pagenum: 407; label: 9.4.4
title: Exercises for Section 9.4
pagenum: 412; label: 9.5
title: Other Undecidable Problems
pagenum: 412; label: 9.5.1
title: Problems About Programs
pagenum: 413; label: 9.5.2
title: Undecidability of Ambiguity for CFG's
pagenum: 413; label: 9.5.3
title: The Complement of a List Language
pagenum: 415; label: 9.5.4
title: Exercises for Section 9.5
pagenum: 418; label: 9.6
title: Summary of Chapter 9
pagenum: 419; label: 9.7
title: Gradiance Problems for Chapter 9
pagenum: 420; label: 9.8
title: References for Chapter 9
pagenum: 422; label: 10
title: Intractable Problems
pagenum: 425; label: 10.1
title: The Classes P and NP
pagenum: 426; label: 10.1.1
title: Problems Solvable in Polynomial Time
pagenum: 426; label: 10.1.2
title: An Example: Kruskal's Algorithm
pagenum: 426; label: 10.1.3
title: Nondeterministic Polynomial Time
pagenum: 431; label: 10.1.4
title: An NP EXample: The Traveling Salesman Problem
pagenum: 431; label: 10.1.5
title: Polynomial-Time Reductions
pagenum: 433; label: 10.1.6
title: NP-Complete Problems
pagenum: 434; label: 10.1.7
title: Exercises for Section 10.1
pagenum: 435; label: 10.2
title: An NP-Complete Problem
pagenum: 438; label: 10.2.1
title: The Satisfiability Problem
pagenum: 438; label: 10.2.2
title: Representing SAT Instances
pagenum: 439; label: 10.2.3
title: NP-Completeness of the SAT Problem
pagenum: 440; label: 10.2.4
title: Exercises for Section 10.2
pagenum: 447; label: 10.3
title: A Restricted Satisfiability Problem
pagenum: 447; label: 10.3.1
title: Normal forms for Boolean Expressions
pagenum: 448; label: 10.3.2
title: Converting Expressions to CNF
pagenum: 449; label: 10.3.3
title: NP-Completeness of CSAT
pagenum: 452; label: 10.3.4
title: NP-Completeness of 3SAT
pagenum: 456; label: 10.3.5
title: Exercises for Section 10.3
pagenum: 458; label: 10.4
title: Additional NP-Complete Problems
pagenum: 458; label: 10.4.1
title: Describing NP-complete Problems
pagenum: 459; label: 10.4.2
title: The Problem of Independent Sets
pagenum: 459; label: 10.4.3
title: The Node-Cover Problem
pagenum: 463; label: 10.4.4
title: The Directed Hamilton-Circuit Problem
pagenum: 465; label: 10.4.5
title: Undirected Hamilton Circuits and the TSP
pagenum: 471; label: 10.4.6
title: Summary of NP-Complete Problems
pagenum: 473; label: 10.4.7
title: Exercises for Section 10.4
pagenum: 473; label: 10.5
title: Summary of Chapter 10
pagenum: 477; label: 10.6
title: Gradiance Problems for Chapter 10
pagenum: 478; label: 10.7
title: References for Chapter 10
pagenum: 481; label: 11
title: Additional Classes of Problems
pagenum: 483; label: 11.1
title: Complements of Languages in NP
pagenum: 484; label: 11.1.1
title: The Class of Languages Co-NP
pagenum: 484; label: 11.1.2
title: NP-Complete Preblems and Co-NP
pagenum: 485; label: 11.1.3
title: Exercises for Section 11.1
pagenum: 486; label: 11.2
title: Problems Solvable in Polynomial Space
pagenum: 487; label: 11.2.1
title: Polynomial-Space Turing Machines
pagenum: 487; label: 11.2.2
title: Relationship of PS and NPS to Previously Defined Classes
pagenum: 488; label: 11.2.3
title: Deterministic and Nondeterministic Polynomial Space
pagenum: 490; label: 11.3
title: A Problem That Is Complete for PS
pagenum: 492; label: 11.3.1
title: PS-Completeness
pagenum: 492; label: 11.3.2
title: Quantified Boolean Formulas
pagenum: 493; label: 11.3.3
title: Evaluating Quantified Boolean Formulas
pagenum: 494; label: 11.3.4
title: PS-Completeness of the QBF Problem
pagenum: 496; label: 11.3.5
title: Exercises for Section 11.3
pagenum: 501; label: 11.4
title: Language Classes Based on Randomization
pagenum: 501; label: 11.4.1
title: Quicksort: an Example of a Randomized Algorithm
pagenum: 502; label: 11.4.2
title: A Turing-Machine Model using Randomization
pagenum: 503; label: 11.4.3
title: The Language of a Randomized Turing Machine
pagenum: 504; label: 11.4.4
title: The Class RP
pagenum: 508; label: 11.4.5
title: Recognizing Languages in RP
pagenum: 508; label: 11.4.6
title: The Class ZPP
pagenum: 509; label: 11.4.7
title: Relationship Between RP and ZPP
pagenum: 510; label: 11.4.8
title: Relationships to the Classes P and NP
pagenum: 511; label: 11.5
title: The Complexity of Primality Testing
pagenum: 512; label: 11.5.1
title: The Importance of Testing Primality
pagenum: 512; label: 11.5.2
title: Introduction to Modular Arithmetic
pagenum: 514; label: 11.5.3
title: The Complexity of Modular-Arithmetic Computations
pagenum: 516; label: 11.5.4
title: Random-Polynomial Primality Testing
pagenum: 517; label: 11.5.5
title: Nondeterministic Primality Tests
pagenum: 518; label: 11.5.6
title: Exercises for Section 11.5
pagenum: 521; label: 11.6
title: Summary of Chapter 11
pagenum: 522; label: 11.7
title: Gradiance Problems for Chapter 11
pagenum: 523; label: 11.8
title: References for Chapter 11
pagenum: 524; title: Index
pagenum: 527