Using an approach that has been successfully class tested at Stanford, Yale, and Johns Hopkins, Floyd and Beigel offer valuable innovations:

**Unified definitions**that yield insight into the capabilities of a wide variety of machines**The perfect combination of simplicity and rigor**---their new approach makes formerly obscure results accessible.**Ideas and examples from practical computer science**bring theory to life**A mechanism to combine programs,**akin to pipes in UNIX(tm)**The first formal definition of simulation**that permits modularized proofs**A general system of standardization of programs,**which streamlines proofs

- Chapter 0: Mathematical Preliminaries
- Quantifiers and Two-Player Games
- Sets, Bags, Relations, Functions, and Sequences
- Strings
- Graphs
- Big-O Notation
- Induction

- Chapter 1: Introduction to Machines
- Programs
- Controls
- Unsigned Counters
- Signed Counters
- Stacks
- Two-Counter Machines
- Turing Machines
- Random Access Machines
- Determinism and Nondeterminism

- Chapter 2: Devices, Machines, and Programs
- Representing Problems
- Devices
- Machines
- Instructions
- Initializers and Terminators
- Programs
- Running a Program
- Determinism and Blocking
- Three Important Kinds of Programs

- Chapter 3: Simulation
- Simulation of Programs
- Lockstep Simulation
- Simulation via Subprograms
- Standardization

- Chapter 4: Finite Machines and Regular Languages
- Standardizing Finite Machine Programs
- Regular Expressions and Languages
- *Regular Expressions in the Real World: egrep
- Kleene's Theorem
- NFA Languages Are the Same as Regular Languages
- Equivalence of NFAs and DFAs
- Minimizing DFRs
- Closure Properties
- Pumping Theorems for Regular Languages

- Chapter 5: Context-Free Languages
- Defining Languages as Solutions to Equations
- *Existence of Unique Minimal Solutions
- CFGs and Their Standardizations *Parse Trees
- Derivations CFLs Are The Same as NSA Languages
- *The Chomsky Hierarchy
- Pumping Theorems for CFLs
- Ambiguity
- *Greibach Normal Form
- CYK Parsing Algorithm
- *Earley's Parsing Algorithm

- Chapter 6: Stack and Counter Machines
- Closure Properties
- DSA Languages Are DSR Languages
- Unambiguous Programs
- On-line Recognition
- Two Counters Simulate a Stack
- Two Counters Simulate Any Number of Counters
- *Counter Languages and Prefix Equivalence

- Chapter 7: Computability
- Tapes and Turing Machines
- Putting the Argument on a Tape, Stack, or Counter
- Random Access Memory
- Universal Turing Machine Program
- *Herbrand-Godel Computability
- Recursive and Recursively Enumerable Sets
- The Halting Problem
- Diagonalization
- Many-One Reductions
- Rewriting Systems and Word Problems
- *The Post Correspondence Problem
- Undecidability of First-Order Logic
- Valid and Invalid Computations
- *Diophantine and Exponential Diophantine Equations

- Chapter 8: Recursion Theory
- Rice's Theorem
- The Recursion Theorem and the Fixed-Point Theorem
- Godel's Incompletedness Theorem
- Oracles and Turing Reductions
- Arithmetical Hierarchy

- Chapter 9: Feasible and Infeasible Problems
- Time-Bounded Computation: P and NP
- NP-Completeness
- Search and Optimization vs. Decision
- Canonical NP-Complete Problems
- Symbol Systems
- Boolean Formula Satisfiability
- NP-Complete Graph Problems
- NP-Complete Problems Involving Sets, Vectors, and Numbers
- An NP-Complete Problem about DFRs
- *Complexity of Some Problems Involving Regular Languages

- Appendixes
- Index

Instructor's Manual available

German and French editions available

- Email:
`facultyservices@sasmp.com` - Physical mail:
Computer Science Press

41 Madison Ave. Floor 37

New York, NY 10010