Paun G., Rozenberg G., Salomaa A. (eds.) Current Trends in Theoretical Computer Science. The Challenge of the New Century

Издательство World Scientific, 2004, -1317 pp.This book continues the tradition of two previous books Current Trends in Theoretical Computer Science, published by World Scientific Publishing Company in 1993 and 2001. We have been very impressed and encouraged by the exceptionally good reception of the two previous books. The positive comments received show that books of this nature are really needed.
The book is based on columns and tutorials published in the Bulletin of the European Association for Theoretical Computer Science (EATCS) in the period 2000-2003. The columnists selected themselves the material they wanted to be included in the book, and the authors were asked to update their contributions. Special effort has been given to presentation - most articles are reader-friendly and do not presuppose much knowledge of the area in question. We believe that the book will constitute suitable supplementary reading material for various courses in computer science. Indeed, the book highlights some key issues and challenges in theoretical computer science, as they seem to us now at the beginning of the new millennium. A glance through the subsequent table of contents should show that many of the most active current research lines in theoretical computer science are represented. Both survey articles and papers dealing with specific problems are included.
In addition to the chapters covered in the two previous books, the current one has two new chapters, "Algorithmics" and "Distributed Computing", that include selected contributions from the corresponding two new columns of the EATCS Bulletin (i.e., columns initiated in the period 2000-2003).
As a matter of fact, with the two new chapters the amount of material to be covered became much too big for a single book, and therefore the chapters were divided into two volumes: "Algorithms and Complexity" and "Formal Models and Semantics". This is by now a traditional division of theoretical computer science (used, e.g., by the "Handbook of Theoretical Computer Science" and by ICALP - the major general conference devoted to theoretical computer science).
The current first volume, "Algorithms and Complexity", includes the following chapters: "Algorithmics", "Complexity", "Distributed Computing", and "Natural Computing", while the second volume, "Formal Models and Semantics", consists of the following chapters: "Formal Specification", "Logic in Computer Science", "Concurrency", and "Formal Language Theory".Volume 1 Algorithms and Complexity
Algorithmics
H-Coloring of Graphs
Open Problems in the Theory of Scheduling
Analysis of Algorithms (AofA). Part I: 1993–1998 ("Dagstuhl Period")
Analysis of Algorithms (AofA). Part II: 1998–2000 ("Princeton-Barcelona-Gdansk")
Algorithm Engineering
PRIMES ⋲ P (Without Assumptions)
Selfish Task Allocation
Computational Complexity
A Physics-Free Introduction to the Quantum Computation Model
The Division Breakthroughs
Derandomization: A Brief Overview
Recent Developments in Explicit Constructions of Extractors
The Art of Uninformed Decisions: A Primer to Property Testing
Time-Space Lower Bounds for NP-Complete Problems
Distributed Computing
A Combinatorial Characterization of Properties Preserved by Antitokens
Distributed Computation Meets Design Theory: Local Scheduling for Disconnected Cooperation
Distributed Communication Algorithms for Ad-hoc Mobile Networks
Selfish Routing in Non-Cooperative Networks: A Survey
Distributed Algorithmic Mechanism Design: Recent Results and Future Directions
Stability in Routing: Networks and Protocols
Natural Computing
Quantum Computation Explained to My Mother
Universality and Quantum Computing
Some Open Problems Related to Quantum Computing
Aqueous Computing: Writing Into Fluid Memory
Biomolecular Computing in Silico
Gene Assembly in Ciliates. Part I: Molecular Operations
Gene Assembly in Ciliates. Part II: Formal Frameworks
A Grand Challenge for Computing: Towards Full Reactive Modeling of a Multi-Cellular Animal
Evolutionary Computation: A Guided Tour
Artificial Chemistries
Neural Computing
Volume 2 Formal Models and Semantics
Formal Specification
The Role of Mathematics and Formal Specification Techniques in Software System Development
Failure-Divergence Semantics as a Formal Basis for an Object-Oriented Integrated Formal Method
Bigraphs Meet Double Pushouts
A New Experience with Graph Transformation
Meta-Modelling and Graph Transformation for the Simulation of Systems
Net Transformations for Petri Net Technology
On the Relevance of High-Level Net Processes
Logic in Computer Science
A New Zero-One Law and Strong Extension Axioms
Tree-Decompositions and the Model-Checking Problem
Is Randomness "Native" to Computer Science?
How to Find a Coin: Prepositional Program Logics Made Easy
Algorithms vs. Machines
Pairwise Testing
Newman's Lemma - A Case Study in Proof Automation and Geometric Logic
Algorithms: A Quest for Absolute Definitions
Concurrency
Some of My Favourite Results in Classic Process Algebra
Roadmap of Infinite Results
Construction and Verification of Concurrent Performance and Reliability Models
Does Combining Nondeterminism and Probability Make Sense?
The Algebraic Structure of Petri Nets
Formal Language Theory
Combinatorics on Words — A Tutorial
Two Problems on Commutation of Languages
Counting (Scattered) Subwords
Post Correspondence Problem - Recent Results
The DFOL Language Equivalence Problem
An Overview of Conjunctive Grammars
State Complexity of Finite and Infinite Regular Languages
GSMs and Contexts
The Depth of Functional Compositions
Language Generating by Means of Membrane Systems
Membrane Computing: New Results, New Problems