STACS 2002: 19th Annual Symposium on Theoretical Aspects of Computer Science Antibes – Juan les Pins, France, March 14–16, 2002 Proceedings

Yan Zong Ding, Michael O. Rabin (auth.), Helmut Alt, Afonso Ferreira (eds.)3540432833, 9783540432838

This book constitutes the refereed proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002, held in Antibes – Juan les Pins, France, in March 2002.
The 50 revised full papers presented together with three invited papers were carefully reviewed and selected from a total of 209 submissions. The book offers topical sections on algorithms, current challenges, computational and structural complexity, automata and formal languages, and logic in computer science.

---

Table of contents :
Hyper-Encryption and Everlasting Security….Pages 1-26
Models and Techniques for Communication in Dynamic Networks….Pages 27-49
What Is a Theory?….Pages 50-64
A Space Lower Bound for Routing in Trees….Pages 65-75
Labeling Schemes for Dynamic Tree Networks….Pages 76-87
Tight Bounds for the Performance of Longest-in-System on DAGs….Pages 88-99
Approximate Strong Separation with Application in Fractional Graph Coloring and Preemptive Scheduling….Pages 100-111
Balanced Coloring: Equally Easy for All Numbers of Colors?….Pages 112-120
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3….Pages 121-132
On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets….Pages 133-141
On Dualization in Products of Forests….Pages 142-153
Scheduling at Twilight the EasyWay….Pages 154-165
Complexity of Multi-dimensional Loop Alignment….Pages 166-178
A Probabilistic 3—SAT Algorithm Further Improved….Pages 179-191
The Secret of Selective Game Tree Search, When Using Random-Error Evaluations….Pages 192-202
Randomized Acceleration of Fundamental Matrix Computations….Pages 203-214
Approximations for ATSP with Parametrized Triangle Inequality….Pages 215-226
A New Diagram from Disks in the Plane….Pages 227-237
Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles….Pages 238-249
On the Parameterized Intractability of Closest Substring and Related Problems….Pages 250-261
On the Complexity of Protein Similarity Search under mRNA Structure Constraints….Pages 262-273
Pure Dominance Constraints….Pages 274-286
Improved Quantum Communication Complexity Bounds for Disjointness and Equality….Pages 287-298
On Quantum Computation with Some Restricted Amplitudes….Pages 299-310
A Quantum Goldreich-Levin Theorem with Cryptographic Applications….Pages 311-322
On Quantum and Approximate Privacy….Pages 323-334
On Quantum Versions of the Yao Principle….Pages 335-346
Describing Parameterized Complexity Classes….Pages 347-358
On the Computational Power of Boolean Decision Lists….Pages 359-371
How Many Missing Answers Can Be Tolerated by Query Learners?….Pages 372-383
Games with a Uniqueness Property….Pages 384-395
Bi-Immunity Separates Strong NP-Completeness Notions….Pages 396-407
Complexity of Semi-algebraic Proofs….Pages 408-418
A Lower Bound Technique for Restricted Branching Programs and Applications….Pages 419-430
The Complexity of Constraints on Intervals and Lengths….Pages 431-442
Nesting Until and Since in Linear Temporal Logic….Pages 443-454
Comparing Verboseness for Finite Automata and Turing Machines….Pages 455-464
On the Average Parallelism in Trace Monoids….Pages 465-476
A Further Step towards a Theory of Regular MSC Languages….Pages 477-488
Existential and Positive Theories of Equations in Graph Products….Pages 489-500
The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL….Pages 501-512
Recognizable Sets of Message Sequence Charts….Pages 513-522
Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard….Pages 523-534
On the Enumerative Sequences of Regular Languages on k Symbols….Pages 535-546
Ground Tree Rewriting Graphs of Bounded Tree Width….Pages 547-558
Timed Control Synthesis for External Specifications….Pages 559-570
Axiomatizing GSOS with Termination….Pages 571-582
Axiomatising Tree-Interpretable Structures….Pages 583-595
EXPSPACE-Complete Variant of Guarded Fragment with Transitivity….Pages 596-607
A Parametric Analysis of the State Explosion Problem in Model Checking….Pages 608-619
Generalized Model-Checking over Locally Tree-Decomposable Classes….Pages 620-631
Learnability and Definability in Trees and Similar Structures….Pages 632-644
….Pages 645-657