STACS 2002

Articles available online at: http://link.springer.de/link/service/series/0558/tocs/t2285.htm

A Space Lower Bound for Routing in Trees
Pierre Fraigniaud and Cyril Gavoille

Labeling Schemes for Dynamic Tree Networks
Amos Korman, David Peleg, and Yoav Rodeh

Tight Bounds for the Performance of Longest-in-System on DAGs
Micah Adler and Adi Rosén

Approximate Strong Separation with Application in Fractional Graph Coloring and Preemptive Scheduling
Klaus Jansen

Balanced Coloring: Equally Easy for All Numbers of Colors?
Benjamin Doerr

The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3
Johannes Köbler and Jacobo Torán

On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets
E. Boros, V. Gurvich, L. Khachiyan, and K. Makino

On Dualization in Products of Forests
Khaled M. Elbassioni

An Asymptotic $\mathcal{O}(\ln\rho/\ln\ln\rho)$-Approximation Algorithm for the Scheduling Problem with Duplication on Large Communication Delay Graphs
R. Lepere and C. Rapine

Scheduling at Twilight the Easy Way
Hannah Bast

Complexity of Multi-dimensional Loop Alignment
Alain Darte and Guillaume Huard

A Probabilistic 3-SAT Algorithm Further Improved
Thomas Hofmeister, Uwe Schöning, Rainer Schuler, and Osamu Watanabe

The Secret of Selective Game Tree Search, When Using Random-Error Evaluations
U. Lorenz and B. Monien

Randomized Acceleration of Fundamental Matrix Computations
Victor Y. Pan

Approximations for ATSP with Parametrized Triangle Inequality
L. Sunil Chandran and L. Shankar Ram

A New Diagram from Disks in the Plane
Joachim Giesen and Matthias John

Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles
Stefan Langerman, Pat Morin, and Michael Soss
Current Challenges

On the Parameterized Intractability of CLOSEST SUBSTRINGsize and Related Problems
Michael R. Fellows, Jens Gramm, and Rolf Niedermeier

On the Complexity of Protein Similarity Search under mRNA Structure Constraints
Rolf Backofen, N.S. Narayanaswamy, and Firas Swidan

Pure Dominance Constraints
Manuel Bodirsky and Martin Kutz

Improved Quantum Communication Complexity Bounds for Disjointness and Equality
Peter Høyer and Ronald de Wolf

On Quantum Computation with Some Restricted Amplitudes
Harumichi Nishimura

A Quantum Goldreich-Levin Theorem with Cryptographic Applications
Mark Adcock and Richard Cleve

On Quantum and Approximate Privacy
Hartmut Klauck

On Quantum Versions of the Yao Principle
Mart de Graaf and Ronald de Wolf
Computational and Structural Complexity

Describing Parameterized Complexity Classes
Jörg Flum and Martin Grohe

On the Computational Power of Boolean Decision Lists
Matthias Krause

How Many Missing Answers Can Be Tolerated by Query Learners?
Hans Ulrich Simon

Games with a Uniqueness Property
Shin Aida, Marcel Crasmaru, Kenneth Regan, and Osamu Watanabe

Bi-Immunity Separates Strong NP-Completeness Notions
A. Pavan and Alan L. Selman

Complexity of Semi-algebraic Proofs
Dima Grigoriev, Edward A. Hirsch, and Dmitrii V. Pasechnik

A Lower Bound Technique for Restricted Branching Programs and Applications
Philipp Woelfel

The Complexity of Constraints on Intervals and Lengths
Andrei Krokhin, Peter Jeavons, and Peter Jonsson
Automata and Formal Languages

Nesting Until and Since in Linear Temporal Logic
Denis Thérien and Thomas Wilke

Comparing Verboseness for Finite Automata and Turing Machines
Till Tantau

On the Average Parallelism in Trace Monoids
Daniel Krob, Jean Mairesse, and Ioannis Michos

A Further Step towards a Theory of Regular MSC Languages
Dietrich Kuske

Existential and Positive Theories of Equations in Graph Products
Volker Diekert and Markus Lohrey

The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL
Holger Petersen

Recognizable Sets of Message Sequence Charts
Rémi Morin

Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard
Ji$\hbox{\v{r}}$í Srba

On the Enumerative Sequences of Regular Languages on k Symbols
Marie-Pierre Béal and Dominique Perrin
Logic in Computer Science

Ground Tree Rewriting Graphs of Bounded Tree Width
Christof Löding

Timed Control Synthesis for External Specifications
Deepak D'Souza and P. Madhusudan

Axiomatizing GSOS with Termination
J.C.M. Baeten and E.P. de Vink

Axiomatising Tree-Interpretable Structures
Achim Blumensath

EXPSPACE-Complete Variant of Guarded Fragment with Transitivity
Emanuel Kieronski

A Parametric Analysis of the State Explosion Problem in Model Checking
S. Demri, F. Laroussinie, and P. Schnoebelen

Generalized Model-Checking over Locally Tree-Decomposable Classes
Markus Frick

Learnability and Definability in Trees and Similar Structures
Martin Grohe and Gyorgy Turán