STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999 Proceedings

The Symposium on Theoretical Aspects of Computer Science (STACS) is held annually, alternating between France and Germany. The current volume cons- tutes the proceedings of the 16th STACS conference, organized jointly by the Special Interest Group for Theoretical Computer Science of the Gesellschaft fur .. Informatik (GI) in Germany, and Maison de l'Informatique et des Math e- tiques Discr etes (MIMD) in France. The conference took place in Trier { the oldest town in Germany, with more than 2 millennia of history. Previous symposia of the series were held in Paris (1984), Saarbru cken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wur .. zburg (1993), Caen (1994), Mu nchen (1995), Grenoble (1996), Lu beck (1997), and Paris (1998). All proceedings of the series have been published in the Lecture Notes of Computer Science series of Springer-Verlag. STACShasbecome oneofthe mostimportantannualmeetingsin Europefor the theoretical computer science community. This time, altogether 300 authors from36countriesonv econtinentssubmittedtheirpapers.Eachsubmissionwas sent to v e members of the program committee for review. During the program committee session 51 out of the 146 submissions were accepted for presen- tion. In two of the selected papers the same result was proved independently.