Theory of computation
By: Derick Wood.
Publisher: Wiley
Published: 1987
Place of publication: New York, NY
Language: eng
Number of pages: 558
Subjects: Computational complexity.; Machine theory.; Computer science -- Mathematics.
Notes: Bibliogr.

1
Table of contents: title: Preface
pagenum: xiii; title: Course Outlines
pagenum: xvii; label: Part I
title: Introduction
pagenum: 1; label: Chapter 0
title: Preliminaries; label: 0.1
title: Sequences, Sets, and Tuples
pagenum: 3; label: 0.1.1
title: Sets and Their Specification
pagenum: 3; label: 0.1.2
title: Set Operations
pagenum: 6; label: 0.1.3
title: Multisets
pagenum: 8; label: 0.1.4
title: Sequences
pagenum: 8; label: 0.1.5
title: Tuples
pagenum: 9; label: 0.2
title: Directed Graphs
pagenum: 9; label: 0.2.1
title: Digraphs
pagenum: 10; label: 0.2.2
title: Multiset Digraphs and Trees
pagenum: 14; label: 0.3
title: Functions, Relations, and Closure
pagenum: 17; label: 0.3.1
title: Functions
pagenum: 17; label: 0.3.2
title: Big-O Notation
pagenum: 19; label: 0.3.3
title: Relations
pagenum: 20; label: 0.3.4
title: Closure
pagenum: 25; label: 0.4
title: Cardinality, Countability, and Enumerability
pagenum: 27; label: 0.5
title: Proof Methods and Techniques
pagenum: 28; label: 0.5.1
title: Direct Proof
pagenum: 29; label: 0.5.2
title: Proof by Contradiction
pagenum: 30; label: 0.5.3
title: Proof by Induction
pagenum: 31; label: 0.5.4
title: The Pigeonhole Principle
pagenum: 34; label: 0.5.5
title: Counting
pagenum: 35; label: 0.5.6
title: Diagonalization
pagenum: 36; label: 0.6
title: Additional Remarks
pagenum: 38; label: 0.6.1
title: Summary
pagenum: 38; label: 0.6.2
title: Further Reading
pagenum: 38; title: Exercises
pagenum: 38; title: Programming Projects
pagenum: 49; label: Chapter 1
title: Languages and Computation; label: 1.1
title: Programming Problems and Computation
pagenum: 50; label: 1.2
title: Alphabets, Words, and Languages
pagenum: 63; label: 1.2.1
title: Alphabets and Words
pagenum: 64; label: 1.2.2
title: Languages and Operations
pagenum: 68; label: 1.2.3
title: Defining Languages
pagenum: 71; label: 1.2.4
title: Definition Summaries
pagenum: 76; label: 1.3
title: Languages, Problems, and Computation
pagenum: 77; label: 1.4
title: Additional Remarks
pagenum: 80; label: 1.4.1
title: Summary
pagenum: 80; label: 1.4.2
title: History
pagenum: 80; label: 1.5
title: Springboard
pagenum: 81; label: 1.5.1
title: The 2-Calculus
pagenum: 81; label: 1.5.2
title: Markov Algorithms
pagenum: 81; label: 1.5.3
title: Post Systems and Production Systems
pagenum: 82; label: 1.5.4
title: Recursive Functions
pagenum: 83; label: 1.5.5
title: Formal Semantics
pagenum: 84; label: 1.5.6
title: Program Correctness
pagenum: 85; label: 1.5.7
title: Program Construction
pagenum: 86; title: Exercises
pagenum: 86; title: Programming Projects
pagenum: 90; label: Part II
title: Models
pagenum: 93; label: Chapter 2
title: Finite Automata; label: 2.1
title: States, State Diagrams, and Transitions
pagenum: 95; label: 2.2
title: Deterministic Finite Automata
pagenum: 98; label: 2.3
title: Nondeterministic Finite Automata
pagenum: 111; label: 2.4
title: Minimization and Simplification
pagenum: 127; label: 2.5
title: DFAs and Tries
pagenum: 133; label: 2.6
title: λ-FAs and Lazy FAs
pagenum: 135; label: 2.6.1
title: 2-FAs and 2-Transitions
pagenum: 135; label: 2.6.2
title: Lazy Finite Automata
pagenum: 140; label: 2.7
title: Additional Remarks
pagenum: 142; label: 2.7.1
title: Summary
pagenum: 142; label: 2.7.2
title: History
pagenum: 143; label: 2.8
title: Springboard
pagenum: 143; label: 2.8.1
title: The Syntactic Monoid
pagenum: 143; label: 2.8.2
title: Life and Cellular Automata
pagenum: 144; label: 2.8.3
title: Communication Protocols
pagenum: 144; label: 2.8.4
title: Security
pagenum: 144; label: 2.8.5
title: Tree Automata
pagenum: 145; label: 2.8.6
title: Avoiding Spaghetti Programming
pagenum: 145; title: Exercises
pagenum: 147; title: Programming Projects
pagenum: 153; label: Chapter 3
title: Regular Expressions
pagenum: 155; label: 3.1
title: Motivation and Definition
pagenum: 155; label: 3.2
title: Regular Expressions into Finite Automata
pagenum: 161; label: 3.3
title: Extended Finite Automata into Regular Expressions
pagenum: 166; label: 3.4
title: Extended Regular Expressions
pagenum: 175; label: 3.5
title: Additional Remarks
pagenum: 179; label: 3.5.1
title: Summary
pagenum: 179; label: 3.5.2
title: History
pagenum: 179; label: 3.6
title: Springboard
pagenum: 180; label: 3.6.1
title: A Differential Calculus
pagenum: 180; label: 3.6.2
title: Descriptional Complexity
pagenum: 180; label: 3.6.3
title: VLSI
pagenum: 181; label: 3.6.4
title: Path Expressions
pagenum: 181; title: Exercises
pagenum: 182; title: Programming Projects
pagenum: 185; label: Chapter 4
title: Context-Free Grammars
pagenum: 187; label: 4.1
title: Basics of Context-Free Grammars
pagenum: 187; label: 4.2
title: Simplifications
pagenum: 211; label: 4.2.1
title: Redundant Symbols
pagenum: 212; label: 4.2.2
title: Empty Productions
pagenum: 215; label: 4.2.3
title: Unit Productions
pagenum: 220; label: 4.2.4
title: Binary Form and Chomsky Normal Form
pagenum: 221; label: 4.2.5
title: Greibach Normal Form and Two-Standard Normal Form
pagenum: 224; label: 4.3
title: Linear and Regular Grammars
pagenum: 229; label: 4.4
title: Extended Context-Free Grammars
pagenum: 232; label: 4.5
title: Additional Remarks
pagenum: 236; label: 4.5.1
title: Summary
pagenum: 236; label: 4.5.2
title: History
pagenum: 237; label: 4.6
title: Springboard
pagenum: 237; label: 4.6.1
title: Recognition and Parsing
pagenum: 237; label: 4.6.2
title: Ambiguity
pagenum: 238; label: 4.6.3
title: W-grammars
pagenum: 238; label: 4.6.4
title: Simplifications and Efficiency
pagenum: 239; label: 4.6.5
title: Context-Free Expressions
pagenum: 239; label: 4.6.6
title: EOL Grammars and Languages
pagenum: 239; label: 4.6.7
title: ALGOL-Like Languages
pagenum: 240; title: Exercises
pagenum: 240; title: Programming Projects
pagenum: 246; label: Chapter 5
title: Pushdown Automata
pagenum: 248; label: 5.1
title: Deterministic Pushdown Automata
pagenum: 248; label: 5.2
title: Nondeterministic Pushdown Automata
pagenum: 259; label: 5.3*
title: Counter Automata *
pagenum: 270; label: 5.4*
title: Two-Way Deterministic Pushdown Automata *
pagenum: 271; label: 5.5
title: Additional Remarks
pagenum: 273; label: 5.5.1
title: Summary
pagenum: 273; label: 5.5.2
title: History
pagenum: 274; label: 5.6
title: Springboard
pagenum: 274; label: 5.6.1
title: Data Structure Automata
pagenum: 274; label: 5.6.2
title: Preset Pushdown Automata
pagenum: 274; label: 5.6.3
title: Multihead and Multipushdown Automata
pagenum: 274; label: 5.6.4
title: Finite-Buffer PDAs and Lazy PDAs
pagenum: 274; label: 5.6.5
title: Small PDAs
pagenum: 275; title: Exercises
pagenum: 276; title: Programming Projects
pagenum: 279; label: Chapter 6
title: Turing Machines
pagenum: 280; label: 6.1
title: The Turing Machine
pagenum: 280; label: 6.2
title: Turing Machine Programming
pagenum: 295; label: 6.3*
title: Simplifications *
pagenum: 301; label: 6.4
title: Extensions
pagenum: 311; label: 6.4.1
title: Two-Way Infinite Tape Turing Machines
pagenum: 312; label: 6.4.2
title: Nondeterministic Turing Machines
pagenum: 316; label: 6.4.3
title: Multihead Turing Machines
pagenum: 318; label: 6.4.4
title: Multitape Turing Machines
pagenum: 320; label: 6.5
title: Universal Turing Machines
pagenum: 320; label: 6.6
title: Resource-Bounded Turing Machines
pagenum: 326; label: 6.7
title: Additional Remarks
pagenum: 331; label: 6.7.1
title: Summary
pagenum: 331; label: 6.7.2
title: History
pagenum: 331; label: 6.8
title: Springboard
pagenum: 331; label: 6.8.1
title: The Busy Beaver Game
pagenum: 331; label: 6.8.2
title: The Turing Micros
pagenum: 332; label: 6.8.3
title: Computable Functions
pagenum: 333; label: 6.8.4
title: NP-Completeness
pagenum: 333; label: 6.8.5
title: Simulation Efficiency
pagenum: 333; label: 6.8.6
title: Recursively Enumerable Languages
pagenum: 334; label: 6.8.7
title: Context-Sensitive Languages
pagenum: 334; title: Exercises
pagenum: 334; title: Programming Projects
pagenum: 337; label: Chapter 7
title: Functions, Relations, and Translations
pagenum: 338; label: 7.1
title: Introduction
pagenum: 338; label: 7.2
title: Finite Transducers
pagenum: 339; label: 7.3
title: Translation Grammars
pagenum: 348; label: 7.4
title: Pushdown Transducers
pagenum: 352; label: 7.5
title: Turing Machines and Computable Functions
pagenum: 355; label: 7.6
title: Recursive Functions
pagenum: 359; label: 7.7
title: Additional Remarks
pagenum: 364; label: 7.7.1
title: Summary
pagenum: 364; label: 7.7.2
title: History
pagenum: 364; label: 7.8
title: Springboard
pagenum: 364; label: 7.8.1
title: Lexical Analysis
pagenum: 364; label: 7.8.2
title: Syntax-Directed Translations
pagenum: 364; label: 7.8.3
title: File Compaction
pagenum: 365; label: 7.8.4
title: Translation Expressions
pagenum: 365; label: 7.8.5
title: String Similarity
pagenum: 365; label: 7.8.6
title: Recursive Function Theory
pagenum: 365; title: Exercises
pagenum: 366; title: Programming Projects
pagenum: 368; label: Part III
title: Properties
pagenum: 371; label: Chapter 8
title: Family Relationships
pagenum: 373; label: 8.1
title: Finite, Regular, and Context-Free Languages
pagenum: 373; label: 8.1.1
title: Introduction
pagenum: 373; label: 8.1.2
title: Regular Languages
pagenum: 375; label: 8.1.3*
title: Unary Regular Languages *
pagenum: 379; label: 8.2
title: Context-Free and Tractable Languages
pagenum: 382; label: 8.2.1
title: Deterministic Context-Free Languages
pagenum: 382; label: 8.2.2*
title: Tractable Languages *
pagenum: 383; label: 8.2.3
title: Context-Free Pumping Lemma
pagenum: 387; label: 8.2.4*
title: Parikh's Theorem *
pagenum: 394; label: 8.3*
title: Tractable and Recursive Languages *
pagenum: 397; label: 8.4
title: Recursive and DTM Languages
pagenum: 403; label: 8.5
title: Additional Remarks
pagenum: 406; label: 8.5.1
title: Summary
pagenum: 406; label: 8.5.2
title: History
pagenum: 406; label: 8.6
title: Springboard
pagenum: 407; label: 8.6.1
title: Hierarchy Results
pagenum: 407; label: 8.6.2
title: Pumping Lemmas
pagenum: 407; label: 8.6.3
title: Nonlanguages and Closure Properties
pagenum: 408; title: Exercises
pagenum: 408; label: Chapter 9
title: Closure Properties
pagenum: 412; label: 9.1
title: Boolean and Reversal Operations
pagenum: 412; label: 9.2
title: Mappings
pagenum: 420; label: 9.2.1
title: Morphism and Substitution
pagenum: 420; label: 9.2.2*
title: Inverse Morphism and Finite Transduction *
pagenum: 429; label: 9.3
title: Catenation, Quotient, and Star
pagenum: 434; label: 9.4
title: Composition
pagenum: 435; label: 9.5
title: Cylinders, Cones, and AFLs
pagenum: 438; label: 9.6
title: Additional Remarks
pagenum: 440; label: 9.6.1
title: Summary
pagenum: 440; label: 9.6.2
title: History
pagenum: 440; label: 9.7
title: Springboard
pagenum: 441; label: 9.7.1
title: Closure Properties
pagenum: 441; label: 9.7.2
title: Cones
pagenum: 441; title: Exercises
pagenum: 441; label: Chapter 10
title: Decision Problems
pagenum: 446; label: 10.1
title: Decidability and Membership
pagenum: 446; label: 10.1.1
title: Introduction
pagenum: 446; label: 10.1.2
title: Finite Automata
pagenum: 447; label: 10.1.3
title: Context-Free Grammars
pagenum: 447; label: 10.1.4
title: Deterministic Turing Machines
pagenum: 448; label: 10.2
title: Emptiness and Finiteness
pagenum: 450; label: 10.2.1
title: Finite Automata
pagenum: 450; label: 10.2.2
title: Context-Free Grammars
pagenum: 451; label: 10.2.3
title: Deterministic Turing Machines
pagenum: 452; label: 10.3
title: Containment, Equivalence, and Intersection
pagenum: 454; label: 10.3.1
title: Finite Automata
pagenum: 454; label: 10.3.2
title: Context-Free Grammars
pagenum: 455; label: 10.4
title: Context-Free Ambiguity
pagenum: 462; label: 10.5
title: Additional Remarks
pagenum: 462; label: 10.5.1
title: Summary
pagenum: 462; label: 10.5.2
title: History
pagenum: 462; label: 10.6
title: Springboard
pagenum: 463; label: 10.6.1
title: Post's Correspondence Problem
pagenum: 463; title: Exercises
pagenum: 464; label: Part IV
title: Onward
pagenum: 469; label: Chapter 11
title: Further Topics; label: 11.1
title: NP-Complete Problems
pagenum: 472; label: 11.1.1
title: The Ordering ∝
pagenum: 472; label: 11.1.2
title: An NP-Complete Problem
pagenum: 475; label: 11.1.3
title: Satisfiability
pagenum: 476; label: 11.1.4
title: Traveling Salesman
pagenum: 481; label: 11.1.5
title: Subset Sum
pagenum: 488; label: 11.1.6
title: Hierarchical Grammars
pagenum: 492; label: 11.2
title: Rewriting Systems and Church's Thesis
pagenum: 497; label: 11.2.1
title: Phrase Structure Grammars
pagenum: 497; label: 11.2.2
title: Interactive Lindenmayer Grammars
pagenum: 500; label: 11.3
title: Parsing
pagenum: 504; label: 11.3.1
title: General CFG Parsing
pagenum: 504; label: 11.3.2
title: Deterministic Top-Down Parsing
pagenum: 507; label: 11.3.3
title: Deterministic Bottom-Up Parsing
pagenum: 515; label: 11.4
title: Additional Remarks
pagenum: 523; label: 11.4.1
title: Summary
pagenum: 523; label: 11.4.2
title: History
pagenum: 523; label: 11.5
title: Springboard
pagenum: 524; label: 11.5.1
title: Dealing with NP-Completeness
pagenum: 524; label: 11.5.2
title: LALR Grammars
pagenum: 525; label: 11.5.3
title: Other Kinds of Completeness
pagenum: 525; title: Exercises
pagenum: 526; title: Bibliography
pagenum: 531; title: Index
pagenum: 547