STACS 2001

the long version

The Symposium on Theoretical Aspects of Computer Science (STACS) is held annually, alternating between France and Germany. The STACS meetings are organized jointly by the Special Interest Group for Theoretical Computer S- ence of the Gesellschaft fu ¨r Informatik (GI) in Germany and the Maison de l’Informatique et des Math ematiques Discr etes (MIMD) in France. STACS2001 was the 18th in this series, held in Dresden, February 15-17, 2001. PreviousSTACS symposia took placein Paris(1984),Saarbr¨ ucken(1985), Orsay(1986),Passau(1987),Bordeaux(1988),Paderborn(1989),Rouen(1990), Hamburg(1991),Cachan(1992),Wu ¨rzburg(1993),Caen(1994),Mu ¨nchen(1995), Grenoble (1996), Lub ¨ eck (1997), Paris (1998), Trier (1999), and Lille (2000). It may be worth noting that in 2001 the symposium was held in one of the new states of reunited Germany for the r st time. The proceedings of all of these symposia have been published in the Lecture Notes in Computer Science series of Springer{Verlag. STACS has become 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 foundations of computer science: algorithms and data structures, automata and formallanguages,computationaland structuralcomplexity, logic, veri cation, and current challenges. This year, 153 submissions were received, mostly in electronic form, from more than 30 countries, with a fair portion from non{European countries. We would like to thank Jochen Bern who designed the electronic submission procedure which performed marvelously and was of great help to the program committee.