This book constitutes the refereed proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, held in February 2006. The 54 revised full papers presented together with three invited papers were carefully reviewed and selected from 283 submissions. The papers address the whole range of theoretical computer science including algorithms and data structures, automata and formal languages, complexity theory, semantics, and logic in computer science.

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."