index - STACS2009 - Symposium on Theoretical Aspects of Computer Science 2009 Access content directly
The Symposium on Theoretical Aspects of Computer Science (STACS) is held alternately in France and in Germany. The conference of February 26-28, 2009, held in Freiburg, is the 26th in this series. Previous meetings took place in Paris (1984), Saarbrücken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Würzburg (1993), Caen (1994), München (1995), Grenoble (1996), Lübeck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), Antibes (2002), Berlin (2003), Montpellier (2004), Stuttgart (2005), Marseille (2006), Aachen (2007), and Bordeaux (2008).
The interest in STACS has remained at a high level over the past years. The STACS 2009 call for papers led to over 280 submissions from 41 countries. Each paper was assigned to three program committee members. The committee selected 54 papers during a two-week electronic meeting held at the beginning of November. As co-chairs of the program committee, we would like to sincerely thank its members and the many external referees for their valuable work. The overall very high quality of the submissions made the selection a difficult task.

We would like to express our thanks to the three invited speakers, Monika Henzinger, Jean-Eric Pin and Nicole Schweikardt, for their contributions to the proceedings. Special thanks go to Andrei Voronkov for his EasyChair software ( Moreover, we would like to thank Sonja Lauer for preparing the conference proceedings and continuous help throughout the conference organization.

For the second time, this year’s STACS proceedings are published in electronic form. A printed version was also available at the conference, with ISBN 978-3-939897-09-5. The electronic proceedings are available through several portals, and in particular through HAL and DROPS. HAL is an electronic repository managed by several French research agencies, and DROPS is the Dagstuhl Research Online Publication Server. We want to thank both these servers for hosting the proceedings of STACS and guaranteeing them perennial availability. The rights on the articles in the proceedings are kept with the authors and the papers are available freely, under a Creative Commons license (see www.stacs- for more details).
STACS 2009 received funds from the German Research Foundation (Deutsche Forschungs- gemeinschaft, DFG) and the University of Freiburg. We thank them for their support!

Proceeding Foreword
Proceeding Table of Contents

The site of STACS 2009:
The site of the STACS conferences: