A Word From My Publisher
In The Language of Machines, Robert Floyd and Richard Beigel
revolutionize the teaching of computability and languages. They
propose nothing less than redefinition of the building blocks of
automata theory: their unified model of computation clarifies the
subject as never before. Floyd and Beigel's single model encompasses
all the traditional types of computing machines and even "real world"
electronic computers.
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
Floyd an Beigel's bold reformulation of computability and formal
language theory provides a firm foundation on which students can
build a rich and enduring body of knowledge.
Contents (starred sections are optional)
- 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
1994, 706 pages, cloth, 0-7167-8266-9
Instructor's Manual available
German and French editions available
Contacting the Publisher
For comp copies or an instructor's manual, please contact Jennifer Jenkins.