This work constitutes the refereed proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 99, held in Trier, Germany in March 1999. The 51 revised full papers presented were selected from a total of 146 submissions. Also included are three invited papers. The volume is divided in topical sections on complexity, parallel algorithms, computational geometry, algorithms and data structures, automata and formal languages, verification, algorithmic learning, and logic in computer science.

STACS, the SymposiumonTheoreticalAspects ofComputerScience, isheld- nually, alternating between France and Germany. STACS is organizedjointly by the Special Interest Group for Theoretical Computer Science of the Gesellschaft f] ur Informatik (GI) in Germany and the Maison de l Informatique et des Ma- ematiquesDiscr etes(MIMD)inFrance.STACS2000wasthe17thintheseries.It was held in Lille from February 17th to 19th, 2000. Previous STACS symposia took place in Paris (1984), Saarbru ]cken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan...