Samy Abbes
IRIF, Université Paris Diderot
https://www.irif.fr/~abbes/
Date(s) : 29/03/2016 iCal
11 h 00 min - 12 h 00 min
Les monoïdes d’empilements de pièces apparaissent dans differents contextes de combinatoire, et egalement en informatique comme modèles de systèmes parallèles. Ce type de système présente une difficulté lorsqu’on cherche à le probabiliser : à cause des commutations entre pièces parallèles, il n’y a pas d’ « horloge globale » a l’échelle du système.
Nous introduisons les mesures multiplicatives, et parmi celles-ci la mesure uniforme, comme les mesures de probabilité les plus simples sur l’espace des empilements infinis. Leur construction repose sur la combinatoire des monoïdes d’empilements, le polynôme de Mœbius y jouant un role clef. On prouve que les mesures multiplicatives correspondent à certaines chaînes de Markov pour la forme normale de Cartier-Foata des empilements infinis. On en déduit une approximation markovienne des distributions finies et uniformes sur les empilements de grande taille.
Multiplicative and uniform measurements for part stack monoids
Monoids of stacks of pieces appear in different contexts of combinatorics, and also in computer science as models of parallel systems. This type of system presents a difficulty when one seeks to make it more probable: because of the switching between parallel parts, there is no « global clock » on the scale of the system.
We introduce multiplicative measures, and among them the uniform measure, as the simplest probability measures on the space of infinite stacks. Their construction is based on the combinatorics of stacking monoids, the Moebius polynomial playing a key role. We prove that the multiplicative measures correspond to certain Markov chains for the Cartier-Foata normal form of infinite stacks. We deduce a Markovian approximation of the finite and uniform distributions on large stacks.
Catégories