Издательство 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 ammount 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.
Chapter 1 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.
Chapter 2 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.
Chapter 3 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.
Chapter 4 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.
Chapter 1 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.
Chapter 2 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.
Chapter 3 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.
Chapter 4 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.
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 ammount 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.
Chapter 1 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.
Chapter 2 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.
Chapter 3 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.
Chapter 4 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.
Chapter 1 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.
Chapter 2 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.
Chapter 3 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.
Chapter 4 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.