To Shaula, Inbal, Itai, Erez, Netta, and Danna
Preface
1 GENERAL CONCEPTS
1.1 Alphabets, Strings, and Representations
1.2 Formal Languages and Grammars
1.3 Programs
1.4 Problems
1.5 Reducibility among Problems
Exercises
Bibliographic Notes
2 FINITE-MEMORY PROGRAMS
2.1 Motivation
2.2 Finite-State Transducers
2.3 Finite-State Automata and Regular Languages
2.4 Limitations of Finite-Memory Programs
2.5 Closure Properties for Finite-Memory Programs
2.6 Decidable Properties for Finite-Memory Programs
Exercises
Bibliographic Notes
3 RECURSIVE FINITE-DOMAIN PROGRAMS
3.1 Recursion
3.2 Pushdown Transducers
3.3 Context-Free Languages
3.4 Limitations of Recursive Finite-Domain Programs
3.5 Closure Properties for Recursive Finite-Domain Programs
3.6 Decidable Properties for Recursive Finite-Domain Programs
Exercises
Bibliographic Notes
4 GENERAL PROGRAMS
4.1 Turing Transducers
4.2 Programs and Turing Transducers
4.3 Nondeterminism versus Determinism
4.4 Universal Turing Transducers
4.5 Undecidability
4.6 Turing Machines and Type 0 Languages
4.7 Post's Correspondence Problem
Exercises
Bibliographic Notes
5 RESOURCE-BOUNDED COMPUTATION
5.1 Time and Space
5.2 A Time Hierarchy
5.3 Nondeterministic Polynomial Time
5.4 More NP-Complete Problems
5.5 Polynomial Space
5.6 P-Complete Problems
Exercises
Bibliographic Notes
6 PROBABILISTIC COMPUTATION
6.1 Error-Free Probabilistic Programs
6.2 Probabilistic Programs That Might Err
6.3 Probabilistic Turing Transducers
6.4 Probabilistic Polynomial Time
Exercises
Bibliographic Notes
7 PARALLEL COMPUTATION
7.1 Parallel Programs
7.2 Parallel Random Access Machines
7.3 Circuits
7.4 Uniform Families of Circuits
7.5 Uniform Families of Circuits and Sequential Computations
7.6 Uniform Families of Circuits and PRAM's
Exercises
Bibliographic Notes
A MATHEMATICAL NOTIONS
A.1 Sets, Relations, and Functions
A.2 Graphs and Trees
B BIBLIOGRAPHY
Index
[errata | sketches of solutions | notes on the hypertext version | zipped files]