Volumes

The present volume collects the proceedings of the Aofa'12, 23st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms held at the Centre de Recherches Mathématiques at Université de Montreal, Canada, between June 18-22, 2012. The conference builds on the communities of the former series of conferences ``Mathematics and Computer Science'' and ``Analysis of Algorithms'', and aims at studying rigorously the combinatorial objects which appear in particular as data structures, algorithms, models of networks and as well as the essential ubiquitous combinatorial structures. The program committee selected submissions covering this wide range of topics. The regular papers were presented in 30-minute talks, and short abstracts in presentations of 15 minutes. They all appear in the present volume.

The conference included five invited plenary lectures:

• Michael Drmota (TU Vienna, Austria): Extremal parameters in critical and subcritical graph classes
• Svante Janson (Uppsala, Sweden): Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Amin Coja-Oghlan (Warwick, UK): Phase transitions and computational complexity
• Claire Mathieu (Brown, USA): Algorithms for optimization over noisy data
• Avi Wigderson (IAS, USA): Population Recovery via Partial Identification

We thank the members of the steering and program committees for their involvement. We also thank the invited speakers, and the authors of the contributed papers. We express our gratitute to the people at CRM and especially Louis Pelletier for their invaluable help in making sure that the meeting went smoothly. We are also grateful to the editor-in-chief of DMTCS Jens Gustedt for his help in the compilation of the proceedings.

Finally, our special thanks go to the sponsors of the conference for their contributions: CRM, Inria, and NSERC.

Nicolas Broutin and Luc Devroye, Editors

Steering Committee

• Brigitte Chauvin (Versailles, France)
• Luc Devroye (McGill, Canada)
• Michael Drmota (TU Vienna, Austria)
• Daniel Panario (Carleton, Canada)
• Robert Sedgewick (Princeton, USA)
• Wojciech Szpankowski (Purdue, USA)
• Brigitte Vallée (Caen, France)

Program Committee

• Frédérique Bassino, Paris 13, France
• Jit Bose, Carleton, Canada
• Nicolas Broutin (co-chair), Inria, France
• Philippe Chassaing, Nancy, France
• Julien Clément, Caen, France
• Luc Devroye (co-chair), McGill, Canada
• Uriel Feige, Weizmann, Israel
• Alan Frieze, Carnegie-Mellon, USA
• Bernhard Gittenberger, TU Vienna, Austria
• Hsien-Kuei Hwang, Academia Sinica, Taiwan
• Philippe Jacquet, Inria, France
• Colin McDiarmid, Oxford, UK
• Mike Molloy, Toronto, Canada
• Ralph Neininger, Frankfurt, Germany
• Marc Noy, Barcelona, Spain
• Daniel Panario, Carleton, Canada
• Alois Panholzer, TU Vienna, Austria
• Bruno Salvy, Inria, France
• Mohit Singh, McGill, Canada
• Brigitte Vallée, Caen, France
• Mark Ward, Purdue, USA

• Nicolas Broutin
• Luc Devroye

This volume contains all the full papers presented at AUTOMATA 2011, the 17th international workshop on cellular automata and discrete complex systems. The workshop was held on November 21-23, 2011, at the Center for Mathematical Modeling, University of Chile, Santiago, Chile.

AUTOMATA is an annual workshop on the fundamental aspects of cellular automata and related discrete dynamical systems. The spirit of the workshop is to foster collaborations and exchanges between researchers on these areas. The workshop series was started in 1995 by members of the Working Group 1.5 of IFIP, the International Federation for Information Processing.

The volume contains the « full » papers selected by the program committee, which consisted of 27 international experts on cellular automata and related models, and the selection was based on 3 peer reviews on each paper.

Papers in this volume represent a rich sample of current research topics on cellular automata and related models. The papers include theoretical studies of the classical cellular automata model, but also many investigations into various variants and generalizations of the basic concept. The versatile nature and the flexibility of the model is evident from the presented papers, making it a rich source of new research problems for scientists representing a variety of disciplines.

As the editors of these proceedings, we thank all contributors to the scientific program of the workshop. We are especially indebted to the invited speakers and the authors of the contributed papers.

Nazim Fatès, Eric Goles, Alejandro Maass, Iván Rapaport

Program Committee

• Andrew Adamatzky, University of West England, UK
• Stefania Bandini, Università degli Studi di Milano-Bicocca, Italy
• Marie-Pierre Béal, Université Paris-Est, France
• Bruno Durand, Université de Provence, France
• Nazim Fatès, Inria Nancy Grand-Est, France, co-chair
• Paola Flocchini, University of Ottawa, Canada
• Enrico Formenti, Université de Nice-Sophia Antipolis, France
• Henryk Fuks, Brock University, Canada
• Anahí Gajardo, Universidad de Concepción, Chile
• Eric Goles, Universidad Adolfo Ibáñez, Chile, co-chair
• Martin Kutrib, University of Giessen, Germany
• Alejandro Maass, Universidad de Chile, co-chair
• Andrés Moreira, Universidad Técnica Federico Santa María, Chile
• Kenichi Morita, Hiroshima University, Japan
• Pedro de Oliveira, Universidade Presbiteriana Mackenzie, Brazil
• Nicolas Ollinger, Université de Provence, France
• Ronnie Pavlov, Denver University, USA
• Marcus Pivato, Trent University, Canada
• Ivan Rapaport, Universidad de Chile, co-chair
• Dipanwita Roychowdhury, Indian Institute of Technology, India
• Mathieu Sablik, Université de Provence
• Michael Schraudner, Universidad de Chile
• Klaus Sutner, Carnegie Mellon, USA
• Guillaume Theyssier, CNRS, Université de Savoie, France
• Edgardo Ugalde, Universidad Autónoma de San Luis Potosí, Mexico
• Hiroshi Umeo, Osaka Electro-Communication University, Japan
• Thomas Worsch, Karlsruhe University, Germany

We were very pleased to receive a record number of submissions this year covering the spectrum of combinatorics and its applications. The presentations will cover many exciting new results and build connections between research areas. We hope you will be able to attend all the lectures and the two poster sessions. We encourage you to ask questions, discuss the material during breaks and participate fully in the FPSAC experience.

Our thanks goes out to everyone attending FPSAC 2010, and especially the members of the Program and Organizing Committees. We also thank the following organizations for their financial support: the National Science Foundation, the National Security Agency, the San Francisco State University College of Science and Engineering and Department of Mathematics, the Fields Institute, Elsevier, and Lindo Systems. Finally, we hope everyone will join us in thanking Federico Ardila and Matthias Beck for taking on the huge job of co-chairing the Organizing Committee.

Sara Billey & Vic Reiner

Program Committee co-chairs

• Sara Billey (University of Washington, USA, co-chair)
• Vic Reiner (University of Minnesota, USA, co-chair)
• Michael Albert (University of Otago, New Zealand)
• Francesco Brenti (Universita' di Roma "Tor Vergata", Italy)
• Sylvie Corteel (Université Paris XI, France)
• Sergi Elizalde (Dartmouth College, USA)
• Dmitry Feichtner-Kozlov (Universität Bremen, Germany)
• Ira Gessel (Brandeis University, USA)
• Curtis Greene (Haverford College, USA)
• Jim Haglund (University of Pennsilvania, USA)
• Sam Hsiao (Bard College, USA)
• Jakob Jonsson (KTH, Sweden)
• Gil Kalai (Hebrew University, Israel)
• Carly Klivans (University of Chicago, USA)
• Fu Liu (University of California, Davis, USA)
• Soichi Okada (Nagoya University, Japan)
• Julian Pfeifle (Universitat Politècnica de Catalunya, Spain)
• Alexander Postnikov (Massachusetts Institute of Technology, USA)
• David Speyer (Massachusetts Institute of Technology, USA)
• Volkmar Welker (Philipps-Universität Marburg, Germany)
• Alex Yong (University of Illinois at Urbana-Champaign, USA)
• Mike Zabrocki (York University, Canada)

• Federico Ardila (San Francisco State University, USA, co-chair)
• Matthias Beck (San Francisco State University, USA, co-chair)
• Nantel Bergeron (York University, Canada)
• Thomas Bliem (San Francisco State University, USA and Universität zu Köln, Germany)
• Tristram Bogart (San Francisco State University, USA and Queen's University, Canada)
• Serkan Hosten (San Francisco State University, USA)
• Brant Jones (University of California, Davis, USA)
• Fu Liu (University of California, Davis, USA)
• Peter McNamara (Bucknell University, USA)
• Ellen Veomett (California State University, East Bay, USA)
• Mike Zabrocki (York University, Canada)