Volumes

DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)

(61 articles)

Programme Committee-Comité de Programme

Bruce Sagan (Michigan State University, USA) (Chair)
Christian Krattenthaler (Universität Wien, Austria) (Co-chair)
Federico Ardila (San Francisco State University, USA)
Jean-Christophe Aval (Université Bordeaux 1, France)
Christine Bessenrodt (Universität Hannover, Germany)
Xun Dong (University of Miami, USA)
Susanna Fishel (Arizona State University, USA)
Sergey Fomin (University of Michigan, USA)
Patricia Hersh (Indiana University, USA)
Ronald King (University of Southampton, UK)
Luc Lapointe (Universidad de Talca, Chile)
Jeremy Lovejoy (Université Denis Diderot, France)
Jeremy Martin (University of Kansas, USA)
Jean-Christophe Novelli (Université de Marne-la-Vallée, France)
Frédéric Patras (Université de Nice, France)
Peter Paule (Universität Linz, Austria)
Nathan Reading (North Carolina State University, USA)
Bruno Salvy (INRIA, France)
Mark Shimozono (Virginia Tech University, USA)
Einar Steingrímsson (Reykjavik University, Iceland)
Itaru Terada (University of Tokyo, Japan) Organizing Committee-Comité d'Organisation Federico Ardila (San Francisco State University, USA)
Hélène Barcelo (Arizona State University, USA)
Christian Krattenthaler (Universität Wien, Austria)
María Ines Icaza (Universidad de Talca, Chile)
Luc Lapointe (Universidad de Talca, Chile) (Chair)
Jennifer Morse (Drexel University, USA)

Foreword

This Proceedings volume is devoted to the 20th International Conference on Formal Power Series and Algebraic Combinatorics, held in Viña del Mar, Chile, during 23-27 June 2008. The conference attracted an audience of approximately 120 participants, consisting of graduate students, junior researchers, and senior researchers from Argentina, Australia, Austria, Canada, Chile, Colombia, China, France, Germany, Iceland, Israel, Japan, South Korea, Mexico, New Zealand, Portugal, Russia, Spain, Sweden, the United States and Venezuela.

The conference was dedicated to Pierre Leroux (1942-2008), who, while serving as president of the permanent programme committee of this conference series from 1991 to 1998, has been one of the driving forces which have made this series into the continuing success that it has been over the past 20 years.

The conference programme featured eight invited lectures, given by Marcelo Aguiar, Michael Albert, Jonathan Brundan, Dmitry Feichtner-Kozlov, Gilbert Labelle, Alexander Postnikov, María Ronco, and Carla Savage, 26 contributed talks, and 39 poster presentations. This volume contains the extended abstracts for most of the contributed talks and poster presentations, all of which had been selected in a careful reviewing process by the programme committee from submissions. These extended abstracts reflect the thematic breadth of the conference by covering aspects of Formal Power Series and Algebraic Combinatorics, including enumeration, commutative algebra, algebraic geometry, combinatorial representation theory, Hecke algebras, Hopf algebras, computational complexity, and statistical physics. We thank all contributors and participants for having made this conference a show-case of current trends in the field and a lively place of exchange of ideas.

The organizers are very grateful for the financial support of the Universidad de Talca (through funds from the Dirección de Investigación y Asistencia Técnica and the Instituto de Matemáticas) and of the Programa Bicentenario de Ciencia y Tecnología: Anillo Ecuaciones Asociadas a Reticulados (Chile). Many American participants were given the opportunity to attend the conference thanks to the support of the National Science Foundation and the National Security Agency. The Fields Institute was very helpful in managing the registration process, and funds generously provided by Elsevier were allocated to the Elsevier award for best extended abstract by a student (Valentin Féray) and to the support of Latin American participants.

We would like to thank all of those who served on the Programme and Organizing Committees, whitout whose contribution such a conference could never have been held. Finally, the help of Ricardo Baeza, Andrés Bustamante, Erdal Emsiz, Raimundo Hamilton, Ana Cecilia de la Maza, María Elena Pinto, Nancy Ruminot, Steen Ryom-Hansen, and especially Blanca Zúñiga, was more than invaluable to the local organizers.

Christian Krattenthaler
Luc Lapointe
Bruce Sagan

DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science

(38 articles)

The Fifth Colloquium on Mathematics and Computer Science is, singularly, the sixth one in a series of events that began at the University of Versailles Saint-Quentin with the Colloque Arbres in June 1995, then went on to the First and Second Colloquia on Mathematics and Computer Science in September 2000 and 2002, again in Versailles, the third edition being hold in Vienna in 2004 and the fourth in Nacy 2006. These meetings aim try provide a forum for researchers working on the closely related domains of probabilities, trees, algorithms and combinatorics. Basic data structures of Computer Science, such as trees or graphs, can and should be studied from several points of view: as the data structure underlying some algorithms, or as a combinatorial or probabilistic object.

The previous meetings were very well received and established a vivid and increasing cooperation between mathematicians and researchers in computer science. Both communities get their reward from the cooperation. For mathematicians computer science is a rich source of interesting and new structures, which require a systematic approach and provide new insights. For theoretical computer science researcher it is a source of mathematical knowledge and a platform for exchanging problems and for abstract research on theoretical fundamentals. The previous meetings as well as this one showed an ongoing research and an development of new tools and methods, like in probability, combinatorics and singularity analysis. In this sense, the meetings serves as a melting pot for different views, attitudes and cultures.

With the organization of the 2008 Colloquium, we hope to have contributed further progress on topics at the boundary (or closed partly the gap) between probability theory and theoretical computer science. Papers were sought in a wide spectrum of mathematical areas, for instance random trees, stochastic processes, large deviations, branching processes, random walks, discrete probabilities, analytical and enumerative combinatorics, run time analysis of algorithms and data structures, performance evaluation, random generation of combinatorial structures, singularity analysis, logic, number theory, statistics, stochastic geometry and so on. A large Program Committee, guaranteeing wide coverage of subtopics and expertise in a variety of fields, selected 34 papers for a presentation as 30-minute talks and some for a presentation as a poster. Almost all talk presentations appear in this volume of the journal Discrete Mathematics & Theoretical Computer Science. Furthermore, eight one-hour plenary lectures were presented by the following invited speakers (appearing in alphabetical order)

Philippe Chassaing (Université Henri Poincaré, France)
Jean-Francois Le Gall (Université Paris-Sud, France)
Malwina Luczak (The London School of Economics and Political Sience, Great Britain)
Ralph Neininger (Johann Wolfgang Goethe Universität, Germany)
Mathew Penrose (University of Bath, England)
Angelika Steger (ETH Zürich, Switzerland)
Wojciech Szpankowski (Purdue University, USA)
Joseph E. Yukich (Lehigh University, USA).

The papers assembled in this volume offer snapshots of current research. Moreover, some of them, in particular invited talks, include carefully crafted surveys of their field. The variety of topics illustrate the numerous ramifications of the theory of discrete and random discrete structures throughout mathematics and computer science. And they show the interplay of different fields.

I wish to express my gratitude and indebtness to the members of the Program Committee, who I was honoured to chair, to the members of the Organizing Committee, to the invited speakers and to all the authors and participants of the conference contributing to the great success of the conference. Thanks for all the constructive support, fast reports of the referees, sound advice by the organizing committee, help of the editor-in-chief of DMTCS and many more. Especially I like to thank the coorganizers of the meeting, Rudolph Grübel and Ludger Rueschendorf, for sharing the work, Jan Spitzman for his internet support and the edition of this volume, our secretary Mrs. Ceuleman for the autonomous work and Mrs. Riemer at the desk office.

Last but not least, I would like to thank for financial support by the DFG and the Center of Scientific Computing (CSC) in Kiel. Further the Christian-Albrechts-Universität zu Kiel provided substantial help in many respects.

Kiel, September 2008
Uwe Roesler
Chair of the Program Committee

Program Committee

Philippe Chassaing (Université Henri Poincaré, France)
Brigitte Chauvin (Université de Versailles, France)
Michael Drmota (Technische Universität Wien, Austria)
Philippe Flajolet, (INRIA, France)
Danièle Gardy (Université de Versailles, France)
Rudolf Grübel (Leibniz Universität Hannover, Germany)
Uwe Roesler, chair, (Christian-Albrechts-Universität Kiel, Germany)
Ludger Rüschendorf (Albert-Ludwigs-Universität Freiburg, Germany)
Gilles Schaeffer (CNRS, France)
Robert Sedgewick (Princeton University, USA)
Wojciech Szpankowski (Purdue University, USA)
Brigitte Vallée (Université de Caen, France)

DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)

(36 articles)

The 2007 Conference on Analysis of Algorithms (AofA'07), has been held in Juan-les-Pins near the cities of Antibes and Nice, France, on June 17-22, 2007.

The Analysis of Algorithms is a scientific basis for computation, providing a link between abstract algorithms and the performance characteristics of their implementations in the real world. The general effort to precisely predict the performance of algorithms has come to involve research in analytic combinatorics, the analysis of random discrete structures, asymptotic analysis, exact and limiting distributions, and other fields of inquiry in computer science, probability theory, and enumerative combinatorics.

DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

(42 articles)

The Fourth Colloquium on Mathematics and Computer Science is, singularly, the fifth one in a series of events that began at the University of Versailles Saint-Quentin with the ''Colloque Arbres'' in June 1995, then went on to the First and Second Colloquia on Mathematics and Computer Science in September 2000 and 2002, again in Versailles, the fourth edition being hold in Vienna in 2004. These meetings aim at creating a forum for researchers working on the closely related domains of probabilities, trees, algorithms and combinatorics. Basic data structures of Computer Science, such as trees or graphs, can, and should, be studied from several points of view: as the data structure underlying some algorithms, or as a combinatorial or probabilistic object ...

The first meetings in 1995, 2000, 2002 and 2004 were well received both by mathematicians and by computer science researchers, and were followed by a continuously increasing cooperation between both communities. On the one hand, mathematicians found a new source of difficult and interesting questions in the analysis of models for Computer Science. On the other hand, the analysis of algorithms and data structures experienced significant developments with the use of existing tools and methods in probability, statistics and combinatorics, and with the development of new ones. With the organization of the 2006 Colloquium, we hope we made further progress towards establishing a regular meeting place for discussion of topics at the boundary between probabilities, statistics, and fundamental computer science. Papers were sought in a wide spectrum of areas, for instance random trees, stochastic processes, large deviations, branching processes, random walks, discrete probabilities, analytical and enumerative combinatorics, analysis of algorithms and data structures, performance evaluation, random generation of combinatorial structures, and statistics. A large Program Committee, guaranteeing wide coverage of subtopics and expertise in a variety of fields, selected 27 papers for a presentation as 25-minutes talks and 10 other papers were selected for a presentation as posters. All these presentations appear in this volume of proceedings of the journal Discrete Mathematics & Theoretical Computer Science. Furthermore, eight 1-hour invited lectures were presented by Michael Drmota (Vienna), Philippe Flajolet (INRIA), Piotr Indyk (MIT), Grégory Miermont (Orsay), Gilles Schaeffer (École Polytechnique), Laurent Viennot (INRIA), Johan Wästlund (Linköping), Wolfgang Woess (Graz). The invited speakers were free to propose a paper, and that resulted in 4 important contributions to this volume.

Altogether, papers assembled in this volume offer snapshots of current research. At the same time, they illustrate the numerous ramifications of the theory of random discrete structures throughout mathematics and computer science. Many of them, in particular invited lectures, include carefully crafted surveys of their field. I thus hope that this volume may serve both as a reference text and as a smooth introduction to many fascinating aspects of this melting pot of continuous and discrete mathematics.

I wish to express my gratitude and indebtness to the members of the Program Committee who I was honoured to chair, to the members of the Organizing Committee, to the invited speakers and to all the authors and participants of the conference, for each one of them has contributed, in a way or another, to the great success of the conference. I also wish to thank Maxim Krikun for his support, help and advice for the edition of this volume. Jens Gustedt, editor-in-chief of DMTCS, Danièle Gardy, Conrado Martinez, Elahe Zohoorian-Azad and Lucas Gerin were also of a great help.

Last but not least, several public and private institutions provided financial support and other contributions. Special thanks shall be given for the financial and logistic support provided by the Plan Pluriannuel de Formation Informatique, Automatique, Electronique, Electrotechnique Mathématiques (PPF IAEEM), the Centre National de la Recherche Scientifique (CNRS), the Agence Nationale de la Recherche (ANR), the Université Henri Poincaré, the Faculté des Sciences, the Institut Élie Cartan and the city of Nancy.

Nancy, September 2006,
Philippe Chassaing
Chair of the Program Committee

Program Committee Mireille Bousquet-Mélou (Université de Bordeaux 1, France)
Philippe Chassaing, (Université Henri Poincaré, France)
Brigitte Chauvin (Université de Versailles St-Quentin, France)
Luc Devroye (McGill University, Canada)
Michael Drmota (Vienna University of Technology, Austria)
Danièle Gardy (Université de Versailles St-Quentin, France)
Micha Hofri (Worcester Polytechnic Institute, USA)
Hsien-Kuei Hwang (Academia Sinica, Taiwan)
Philippe Jacquet (INRIA, France)
Svante Janson (Uppsala University, Sweden)
Christian Krattenthaler (Universität Wien, Austria)
Nicholas Pippenger (Princeton, USA)
Jim Pitman (Berkeley, USA)
Philippe Robert (INRIA, France)

DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)

(8 articles)

On June 20-21, 2005 the third workshop on Computational Logic and Applications took place in Chambéry after the ones in Lyon (June 2004) and in Krakow (June 2002). This workshop, funded by the French Rhone-Alpes region, brings together in a friendly atmosphere researchers from Poland and France around two main topics: analysis of algorithms and lambda calculus with type theory. These two topics, that at first look may seem disjoint, have a meeting point in research on the analysis of densities of lambda terms.

The proceedings of the former workshops have been published in Schedae Informaticae (for the Krakow meeting) and by ENTCS (for the Lyon meeting).

After their presentation at the workshop in Chambéry, some papers were submitted to the editors. The refereeing process (by two anonymous referees from all over the world) has been the usual one. This volume also includes the notes of the course given by Danièle Gardy on random boolean expressions.

We are happy to present these updated papers as a proceedings volume of DMTCS.

The editors: René David Danièle Gardy Pierre Lescanne Marek Zaionc