STACS 2005 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2004, Proceedings

The Symposium on Theoretical Aspects of Computer Science (STACS) is alt- nately held in France and in Germany. The conference of February 24-26, 2005 inStuttgartwasthetwenty-secondinthisseries.Previousmeetingstookplacein 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), Antibes (2002), Berlin (2003), and Montpellier (2004). The interest in STACS has been increasing continuously during recent years and has turned it into a leading conference in theoretical computer science. The call for papers for STACS 2005 led to 217 submissions from all over the world. The 17 members of the Program Committee met in Stuttgart for two days at the end of October 2004 to select the contributions to be presented at the conference.Thanksareduetothecommitteeaswellastoalltheexternalreferees for their valuable work put into the reviewing process. Just 54 papers (i.e., 25% of the submissions) could be accepted, thus guaranteeing the very high scienti?c quality of the conference. Moreover, this strict selection enabled us to keep the conference in its standard format with only two parallel sessions. We would like to thank the three invited speakers Manindra Agrawal (Sin- pore), Mireille Bousquet-M ́ elou (Bordeaux), and Uwe Schoning ] (Ulm) for p- senting lectures and for their contributions to the proceedings. Finally we thank the local organizing committee and all members of the Institute of Formal Methods in Computer Science for their help. In particular wethankHolgerAustinat, HeikePhotien, andHorstProtefortheirgreate?orts.