[clean-list] STACS 2002 -- accepted papers

[Jerome Durand-Lose]

=====================================================================
   We apologize for reception of multiple copies 
=====================================================================

Please find below the list of the papers accepted for 

                        +--------------------+
                        |                    |
                        |     STACS 2002     |
                        |                    |
                        +--------------------+

                   19th International Symposium on
               Theoretical Aspects of Computer Science

                    Antibes Juan-les-Pins, France
                          March 14-16 2002

                    http://www.inria.fr/stacs2002


These papers represent less than 25% of the 209 submissions
(one of the highest number of submissions for a European 
conference in TCS). The selection at the PC meeting was
guided by more than 900 reports.


                 ====  please post and distribute  ====   

=====================================================================

D. Therien, T. Wilke
   Nesting until and since in linear temporal logic

K. Jansen
   Approximate strong separation with application in fractional graph coloring and preemptive scheduling

M. Frick
   Generalized model-checking over locally tree-decomposable classes

H. U. Simon
   How many missing answers can be tolerated by query learners

A. Korman, D. Peleg, Y. Rodeh
   Labeling schemes for dynamic tree networks

D. Grigoriev, E. A. Hirsch, D. V. Pasechnik
   Inequalities-based proof systems

P. Woelfel
   A lower bound technique for restricted branching programs and applications

S. Aida, M. Crasmaru, K. W. Regan, O. Watanabe
   On games with unique solutions

P. Hoyer, R. de Wolf
   Improved quantum communication complexity bounds for disjointness and equality

B. Doerr
   Balanced coloring: equally easy for all numbers of colors?

M. R. Fellows, J. Gramm, R. Niedermeier
   Parameterized intractability of closest substring

T. Tantau
   Comparing verboseness for finite automata and turing machines

M. Krause
   On the computational power of boolean decision lists

D. Krob, J. Mairesse, I. Michos
   On the average height in trace monoids 

D. Kuske
   A further step towards a theory of regular MSC languages

M. Grohe, G. Turan
   Learnability and definability in trees and similar structures

V. Diekert, M. Lohrey
   Existential and positive theories of equations in graph products

A. Pavan, A. L Selman
   Bi-immunity separates strong np-completeness notions

H. Nishimura
   On quantum computation with some restricted amplitudes

J.C.M. Baeten, E.P. de Vink
   Axiomatizing GSOS with termination

M. Bodirsky, M. Kutz
   Pure dominance constraints

M. Adler, A. Rosen
   Tight bounds for the performance of longest in system on DAGs

P. Fraigniaud, C. Gavoille
   A space lower bound for routing in trees

M. Adcock, R. Cleve
   A quantum Goldreich-Levin theorem with cryptographic applications

R. Lepere, C. Rapine
   An asymptotic $O(\ln\rho\/\ln\ln\rho)$-approximation algorithm for the scheduling problem with duplication

J. Flum, M. Grohe
   Describing parameterized complexity classes

V. Y. Pan
   Randomized acceleration of fundamental matrix computations

H. Petersen
   The membership problem for regular expressions with intersection is complete in LOGCFL

A. Blumensath
   Axiomatising tree-interpretable structures

H. Klauck
   On quantum and approximate privacy

J. Koebler, J. Toran
   The complexity of graph isomorphism for colored graphs with color classes of size 2 and 3

R. Morin
   Recognizability vs. realizability and MSO-definability in unbounded hierarchical message sequence charts

J. Giesen, M. John
   A new diagram from disks in the plane

K. M. ELbassioni
   On dualization in products of forests

C. L\"oding
   Ground tree rewriting graphs of bounded tree width

L. S. Chandran, L. S. Ram
   Approximations for ATSP with parametrized triangle inequality

R. Backofen, N.S. Narayanaswamy, F. Swidan
   On the complexity of protein similarity search under mRNA structure constraints

D. D`Souza, P. Madhusudan
   Timed control synthesis for external specifications

A. Krokhin, P. Jeavons, P. Jonsson
   The complexity of constraints on intervals and lengths

A. Darte, G. Huard
   Complexity of multi-dimensional loop alignment

J. Srba
   Checking strong bisimilarity and regularity of BPP is PSPACE-hard

M.-P. Beal, D. Perrin
   On the enumerative sequences of regular languages on k symbols

M. de Graaf, R. de Wolf
   On quantum versions of the Yao principle

E. Kieronski
   EXPSPACE-complete variant of guarded fragment with transitivity

S. Langerman, P. Morin, M. Soss
   Computing the maximum detour and spanning ratio of planar chains, trees and cycles

T. Hofmeister, U. Sch\"oning, R. Schuler, O. Watanabe
   A probabilistic 3-SAT algorithm further improved

S. Demri, F. Laroussinie, P. Schnoebelen
   A parametric analysis of the state explosion problem in model checking

E. Boros, V. Gurvich, L. Khachiyan, K. Makino
   An inequality limiting the number of maximal frequent sets

H. Bast
   Scheduling at twilight the easy way

U. Lorenz, B. Monien
   The secret of selective game tree search, when using random-error evaluations