Current Trends in Theoretical Computer Science: The Challenge of the New Century (Vol 1: Algorithms and Complexity) (Vol 2: Formal Models and Semantics)

HOW TO GO TO YOUR PAGE......Page 2
PREFACE
......Page 7
VOLUME 1: ALGORITHMS AND COMPLEXITY
......Page 5
Contents: Volume 1
......Page 9
CHAPTER 1 ALGORITHMICS......Page 15
Introductory Remarks......Page 17
H-Coloring of Graphs......Page 19
Open Problems in the Theory of Scheduling......Page 33
Analysis of Algorithms (AOFA). Part I: 1993-1998 ("Dagstuhl Period")......Page 53
Analysis of Algorithms (AOFA). Part II: 1998-2000 ("Princeton-Barcelona-Gdansk")......Page 77
Algorithm Engineering......Page 97
PRIMES E P (Without Assumptions)......Page 119
Selfish Task Allocation......Page 125
CHAPTER 2 COMPUTATIONAL COMPLEXITY......Page 135
Introductory Remarks......Page 137
A Physics-Free Introduction to the Quantum Computation Model......Page 139
The Division Breakthroughs......Page 161
Derandomization: A Brief Overview......Page 179
Recent Developments in Explicit Constructions of Extractors......Page 203
The Art of Uninformed Decisions: A Primer to Property Testing......Page 243
Time-Space Lower Bounds for NP-Complete Problems......Page 279
CHAPTER 3 DISTRIBUTED COMPUTING......Page 307
Introductory Remarks......Page 309
A Combinatorial Characterization of Properties Preserved by Antitokens......Page 311
Distributed Computation Meets Design Theory: Local Scheduling for Disconnected Cooperation......Page 329
Distributed Communication Algorithms for Ad-hoc Mobile Networks......Page 351
Selfish Routing in Non-Cooperative Networks: A Survey......Page 387
Distributed Algorithmic Mechanism Design: Recent Results and Future Directions......Page 417
Stability in Routing: Networks and Protocols......Page 449
CHAPTER 4 NATURAL COMPUTING......Page 465
Introductory Remarks......Page 467
Quantum Computation Explained to My Mother......Page 469
Universality and Quantum Computing......Page 483
Some Open Problems Related to Quantum Computing......Page 491
Aqueous Computing: Writing Into Fluid Memory......Page 507
Biomolecular Computing in silico......Page 519
Gene Assembly in Ciliates. Part I: Molecular Operations......Page 541
Gene Assembly in Ciliates. Part II: Formal Frameworks......Page 557
A Grand Challenge for Computing: Towards Full Reactive Modeling of a Multi-Cellular Animal......Page 573
Evolutionary Computation: A Guided Tour......Page 583
Artificial Chemistries......Page 627
Neural Computing......Page 647
VOLUME 2: FORMAL MODELS AND SEMANTICS
......Page 680
Contents: Volume 2
......Page 684
CHAPTER 1 FORMAL SPECIFICATION......Page 691
Introductory Remarks......Page 693
The Role of Mathematics and Formal Specification Techniques in Software System Development......Page 695
Failure-Divergence Semantics as a Formal Basis for an Object-Oriented Integrated Formal Method......Page 705
Bigraphs Meet Double Pushouts......Page 717
A New Experience with Graph Transformation......Page 731
Meta-Modelling and Graph Transformation for the Simulation of Systems......Page 737
Net Transformations for Petri Net Technology......Page 753
On the Relevance of High-Level Net Processes......Page 779
CHAPTER 2 LOGIC IN COMPUTER SCIENCE......Page 785
Introductory Remarks......Page 787
A New Zero-One Law and Strong Extension Axioms......Page 789
Tree-Decompositions and the Model-Checking Problem......Page 809
Is Randomness "Native" to Computer Science?......Page 831
How to Find a Coin: Prepositional Program Logics Made Easy......Page 871
Algorithms vs. Machines......Page 905
Pairwise Testing......Page 927
Newman's Lemma - A Case Study in Proof Automation and Geometric Logic......Page 957
Algorithms: A Quest for Absolute Definitions......Page 973
CHAPTER 3 CONCURRENCY......Page 1003
Introductory Remarks......Page 1005
Some of My Favourite Results in Classic Process Algebra......Page 1007
Roadmap of Infinite Results......Page 1027
Construction and Verification of Concurrent Performance and Reliability Models......Page 1041
Does Combining Nondeterminism and Probability Make Sense?......Page 1067
The Algebraic Structure of Petri Nets......Page 1075
CHAPTER 4 FORMAL LANGUAGE THEORY......Page 1101
Introductory Remarks......Page 1103
Combinatorics on Words - A Tutorial......Page 1105
Two Problems on Commutation of Languages......Page 1167
Counting (Scattered) Subwords......Page 1185
Post Correspondence Problem - Recent Results......Page 1201
The DF0L Language Equivalence Problem......Page 1223
An Overview of Conjunctive Grammars......Page 1235
State Complexity of Finite and Infinite Regular Languages......Page 1257
GSMs and Contexts......Page 1271
The Depth of Functional Compositions......Page 1279
Language Generating by Means of Membrane Systems......Page 1289
Membrane Computing: New Results New Problems......Page 1303
ABOUT THE EDITORS
......Page 1315