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

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