STACS 2002

The Symposium on Theoretical Aspects of Computer Science (STACS) has - come one of the most important annual meetings in Europe for the theoretical computer science community. It covers a wide range of topics in the area of - undationsofcomputerscience:algorithmsanddatastructures,automataand formal languages, computational and structural complexity, logic, veri?cation, and current challenges. STACS 2002, the 19th in this series, was held in Antibes - Juan les Pins, on the French Riviera, March 14 16, 2002. Previous STACS symposia took place in Paris (1984), Saarbruc ken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wurzburg (1993), Caen (1994), Munc hen (1995), Grenoble (1996), Lub eck (1997), Paris, (1998), Trier (1999), Lille (2000), and Dresden (2001). The proceedings of all these symposia have been published in the Lecture Notes in Computer Science series of Springer-Verlag. STACS 2002 received 209 submissions from 30 countries, one of the highest numbers of submissions ever, for a European conference on theoretical computer science. They were dispatched to the Program Committee members, and - derwent a thorough review process, where more than 900 reports were written. These reports then served as guidance to the Program Committee, which met on November 16 17, 2001, at the INRIA Sophia Antipolis (near Antibes), France, in order to select the conference program.

Includes supplementary material: sn.pub/extras

Inhalt
Invited Papers.- Hyper-Encryption and Everlasting Security.- Models and Techniques for Communication in Dynamic Networks.- What Is a Theory?.- Algorithms.- A Space Lower Bound for Routing in Trees.- Labeling Schemes for Dynamic Tree Networks.- Tight Bounds for the Performance of Longest-in-System on DAGs.- Approximate Strong Separation with Application in Fractional Graph Coloring and Preemptive Scheduling.- Balanced Coloring: Equally Easy for All Numbers of Colors?.- The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3.- On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets.- On Dualization in Products of Forests.- An Asymptotic (ln ?/ ln ln ?)-Approximation Algorithm for the Scheduling Problem with Duplication on Large Communication Delay Graphs.- Scheduling at Twilight the EasyWay.- Complexity of Multi-dimensional Loop Alignment.- A Probabilistic 3SAT Algorithm Further Improved.- The Secret of Selective Game Tree Search, When Using Random-Error Evaluations.- Randomized Acceleration of Fundamental Matrix Computations.- Approximations for ATSP with Parametrized Triangle Inequality.- A New Diagram from Disks in the Plane.- Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles.- Current Challenges.- On the Parameterized Intractability of Closest Substring and Related Problems.- On the Complexity of Protein Similarity Search under mRNA Structure Constraints.- Pure Dominance Constraints.- Improved Quantum Communication Complexity Bounds for Disjointness and Equality.- On Quantum Computation with Some Restricted Amplitudes.- A Quantum Goldreich-Levin Theorem with Cryptographic Applications.- On Quantum and Approximate Privacy.- On Quantum Versions of the Yao Principle.-Computational and Structural Complexity.- Describing Parameterized Complexity Classes.- On the Computational Power of Boolean Decision Lists.- How Many Missing Answers Can Be Tolerated by Query Learners?.- Games with a Uniqueness Property.- Bi-Immunity Separates Strong NP-Completeness Notions.- Complexity of Semi-algebraic Proofs.- A Lower Bound Technique for Restricted Branching Programs and Applications.- The Complexity of Constraints on Intervals and Lengths.- Automata and Formal Languages.- Nesting Until and Since in Linear Temporal Logic.- Comparing Verboseness for Finite Automata and Turing Machines.- On the Average Parallelism in Trace Monoids.- A Further Step towards a Theory of Regular MSC Languages.- Existential and Positive Theories of Equations in Graph Products.- The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL.- Recognizable Sets of Message Sequence Charts.- Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard.- On the Enumerative Sequences of Regular Languages on k Symbols.- Logic in Computer Science.- Ground Tree Rewriting Graphs of Bounded Tree Width.- Timed Control Synthesis for External Specifications.- Axiomatizing GSOS with Termination.- Axiomatising Tree-Interpretable Structures.- EXPSPACE-Complete Variant of Guarded Fragment with Transitivity.- A Parametric Analysis of the State Explosion Problem in Model Checking.- Generalized Model-Checking over Locally Tree-Decomposable Classes.- Learnability and Definability in Trees and Similar Structures.