The Symposium on Theoretical Aspects of Computer Science (STACS) is - ternately held in France and Germany. The latest conference, February 27 to March 1, 2003 at the Institute of Computer Science, Freie Universit¿ at Berlin is the twentieth in this series. The previous meetings took place in Paris (1984), Saarbruc ¿ ken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wurzburg ¿ (1993), Caen (1994), Munc ¿ hen (1995), Grenoble (1996), Lub ¿ eck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), and Antibes/Juan-les-Pins (2002). Unlike some other important theory conferences STACS covers the whole range of theoretical computer science including algorithms and data structures, automata and formal languages, complexity theory, semantics, logic in computer science, and current challenges like biological computing, quantum computing, and mobile and net computing. The interest in STACS has been increasing continuously during recent years and has turned it into one of the most signi?cant conferences in theoretical computer science. The STACS 2003 call for papers led to a record number of 253 submissions from all over the world.
This book constitutes the refereed proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, held in Berlin, Germany in February/March 2003. The 58 revised full papers presented together with 2 invited papers were carefully reviewed and selected from 253 submissions. The papers address the whole range of theoretical computer science including algorithms and data structures, automata and formal languages, complexity theory, semantics, logic in computer science, as well as current challenges like biological computing, quantum computing, and mobile and net computing.
