1. Home

The Symposium on Theoretical Aspects of Computer Science (STACS) is held alternately in France and in Germany. The conference of March 4-6, 2010, held in Nancy, is the 27th 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), Bordeaux (2008), and Freiburg (2009).
The interest in STACS has remained at a high level over the past years. The STACS 2010 call for papers led to over 238 submissions from 40 countries. Each paper was assigned to three program committee members. The committee selected 54 papers during a two- week electronic meeting held in 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. In particular, there were intense and interesting discussions. 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, Mikołaj Bojańczyk, Rolf Niedermeier, and Jacques Stern. Special thanks go to Andrei Voronkov for his EasyChair software (www.easychair.org). Moreover, we would like to warmly thank Wadie Guizani for preparing the conference proceedings and continuous help throughout the conference organization.
For the third time, this year’s STACS proceedings are published in electronic form. A printed version was also available at the conference, with ISBN. The electronic proceedings are available through several portals, and in particular through HAL and LIPIcs series . The proceedings of the Symposium, which are published electronically in the LIPIcs (Leibniz International Proceedings in Informatics) series, are available through Dagstuhl’s website. The LIPIcs series provides an ISBN for the proceedings volume and manages the indexing issues. HAL is an electronic repository managed by several French research agencies. Both, HAL and the LIPIcs series, guarantee perennial, free and easy electronic access, while the authors will retain the rights over their work. 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- conf.org/faq.html for more details).
STACS 2010 received funds from Nancy-University (UHP, Nancy 2 and INPL), from Région Lorraine, from CUGN, from GIS 3SG, from GDR IM and from Mairie de Nancy. We thank them for their support!

February 2010

Jean-Yves Marion and Thomas Schwentick

Proceedings Foreword
Proceedings Table of Contents
Full Proceedings of STACS 2010

The site of STACS 2010: http://stacs.loria.fr
The site of the STACS conferences: stacs-conf.org