The maturity of a field of research is probably best characterized by the existence of handbooks that explain its problems, results, applications, and methodology; allow their easy use and understanding by the beginner; state the major unsolved problems; and help the worker in the field master its knowledge. Looking at the two volumes of this handbook, we may conclude that the area we commonly call theoretical computer science is maturing.

Theoretical computer science has many branches and is involved in many aspects of computer and computing systems. This handbook provides a good encyclopedic dictionary of the field. Hence, because any researcher, teacher, or practitioner of computer science needs a good encyclopedic dictionary of computer science, he or she needs this handbook.

This two-volume handbook covers practically all aspects of theoretical computer science; 37 chapters present 37 topics. Some of the most authoritative researchers in the area cover these topics. No similar work is available. Thus, this handbook provides a unique and valuable source of inspiration for every student, teacher, and researcher in computer science. The handbook is not structured like a dictionary, however, and cannot be used as one. First, the topics are divided into two large parts--algorithms and models--with one volume dedicated to each. Second, the topics covered by each of these parts are ordered by their relationship to each other, following a kind of bottom-up approach. The topics treated in the first chapter of each volume are rather independent of the other topics of the volume and thus provide a good foundation. Volume A begins with “Machine Models and Simulations,” and volume B begins with “Finite Automata.”

The rest of each of the volumes builds on these first chapters. In volume A, chapters 2 through 4 are dedicated to various models of complexity expressed in terms of number and structure of operations of various machine models presented in chapter 1. The rest of the chapters discuss the complexity of algorithms used in various branches of computer science. Chapters 2 through 4 of volume B are dedicated to various automata that generalize finite automata and are used as mechanisms for language generation and recognition, a crucial problem of program development. Chapters 5 through 9 present various types of languages and automata-based algorithms for the generation and recognition of the elements of these languages. Finally, the rest of volume B is dedicated to the mathematical models used for specifying the semantics of the languages treated so far.

Each chapter is self-contained and covers a well-defined subject. The chapters of volume A are:

• Machine Models and Simulations;

• A Catalog of Complexity Classes;

• Machine-Independent Complexity Theory;

• Kolmogorov Complexity and Its Applications;

• Algorithms for Finding Patterns in Strings;

• Data Structures;

• Computational Geometry;

• Algorithmic Motion Planning in Robotics;

• Average-case Analysis of Algorithms and Data Structures;

• Graph Algorithms;

• Algebraic Complexity Theory;

• Algorithms in Number Theory;

• Cryptography;

• The Complexity of Finite Functions;

• Communication Networks;

• VLSI Theory;

• Parallel Algorithms for Shared-Memory Machines; and

• General Purpose Parallel Architectures.

• Finite Automata;

• Context-free Languages;

• Formal Languages and Power Series;

• Automata on Infinite Objects;

• Graph Rewriting: An Algebraic and Logic Approach;

• Rewrite Systems;

• Functional Programming and Lambda Calculus;

• Type Systems for Programming Languages;

• Recursive Applicative Program Schemes;

• Logic Programming;

• Denotational Semantics;

• Semantic Domains;

• Algebraic Specification;

• Logics of Programs;

• Methods and Logics for Proving Programs;

• Temporal and Modal Logic;

• Elements of Relational Database Theory;

• Distributed Computing: Models and Methods; and

• Operational and Algebraic Semantics of Concurrent Processes.

The selection of topics in these two volumes raises several questions. Why would one use the term “theoretical computer science” in the first place? Does a branch of computer science exist that is not theoretical or is not based on a theory? I believe the term bears the same relation to the rest of computer science as “analysis” does to numerical analysis in mathematics. Who would say that numerical analysis is not a mathematical theory? While we can say that the design and implementation of an operating system is not a field of theoretical computer science, who can be sure that it will not become one tomorrow? I would justify the use of the term theoretical computer science in this handbook only as a short expression of the criteria for topic selection, and not as defining what we can now call computer science. Essentially, this handbook shows that the term computer science has scientific substance and that the universe of discourse of this substance is extremely large, including both computations as abstractions and the hardware mechanisms performing computations.