Chevaleret, salle 1D06, LIAFA
10H30 : Guglielmo Paoletti
“Strings and Patches in the Abelian Sandpile Model”
The Abelian Sandpile Model is a simple cellular automaton describing the dynamics of a pile of sand under particle’s addition, which has also been studied under the name of Chip-Firing Game; it presents Self Organized Criticality and seems to display allometry. Here I will show the emergence of 2-dimensional periodic patterns (patches) and 1-dimensional periodic defects (strings). I will present the classification of these objects and the relation between their densities and respective periodicity vector, momentum, reminiscent of a dispersion relation. Strings interact, they can merge and split. In the understanding of the whole structure SL(2,Z) plays a key role, finally bringing to the full determination of particular self-similar Structures.
13H30 : Markus Nebel : Generation Aléatoire Non Uniforme
The random generation of combinatorial objects is useful in many places in
computer science, e.g. in the random testing of programs or for the
estimation of the average case runtime of algorithms that elude a
mathematical analysis. In the Bioinformatics area, random sequences are a
topic of great interest e.g. in genome analysis, since according to a
powerful paradigm, they represent the background noise from which the actual
biological information must differentiate.
However, in many applications the random generation should follow the native
distribution of the objects considered.
In this talk we will show how stochastic context-free grammars can be used
for the random generation of combinatorial objects according to non-uniform
distributions derived from sample data. We will see that both, a fixed size
sampling as well as the more efficient Boltzmann sampling can be performed
on basis of those grammars.