2022-2023


Lundi 23 janvier : Philippe Duchon

Titre : Complexité des automates non-déterministes aléatoires

Résumé : (Travail en commun avec Arnaud Carayol, Florent Koechlin et Cyril Nicaud)

Les automates finis sont un modèle bien connu de programmes ne disposant que d'une mémoire finie. Si l'on ignore les questions de lettres, de mots reconnus et de langages, un automate déterministe complet ressemble très fort à un graphe orienté où chaque sommet a un degré sortant constant (et possiblement des arcs multiples). On sait beaucoup de choses sur ces graphes k-sortants aléatoires uniformes: existence d'une grosse composante fortement connexe "puits", ainsi que de nombreux résultats sur les distances à l'intérieur comme à l'extérieur de cette composante.

Dans le monde des automates, on peut également définir des automates non déterministes, dans lesquels un même état peut avoir plus d'une transition étiquetée par la même lettre; en particulier il est classique que leur pouvoir d'expression est le même que celui des automates déterministes, et il existe des algorithmes bien connus de déterminisation - partant d'un automate non déterministe, on calcule un automate déterministe qui accepte le même langage. Il est également bien connu que la taille de l'automate déterminisé est, dans le pire cas, exponentielle en la taille de l'automate de départ.

Dans ce travail, nous cherchons à savoir si ce comportement d'explosion de la taille est rare ou non. Il est difficile de choisir un modèle pertinent d'automates non déterministes aléatoires, aussi nous choisissons un modèle minimalement non-déterministe: partant d'un automate déterministe aléatoire, nous lui ajoutons une transition aléatoire.

Notre résultat principal est que, sous ce modèle, la taille moyenne de l'automate déterminisé est superpolynomiale. Plus précisément, pour tout degré d, la probabilité que l'automate déterminisé ait une taille supérieure à ⚠ $n^d$ reste loin de 0. Notre analyse repose sur une analyse de la structure un peu fine de l'algorithme, et la détection de structures raisonnablement probables dans les automates aléatoires.

Transparents Enregistrement


Lundi 16 janvier : Ivan Yakovlev

Titre :Spectre de longueurs des graphes sur le tore

Résumé : Soit G un graphe aux arêtes pondérées, plongé (de manière cellulaire) dans une surface topologique S. Le spectre marqué de longueurs de G est la fonction qui sur une classe d'homotopie libre de S vaut la longueur d'un cycle le plus court de G qui est dans cette classe d'homotopie. Le spectre non-marqué est une liste croissante de toutes les valeurs du spectre marqué.

Je vais présenter des algorithmes pour calculer les spectres de longueur dans le cas ou S est le tore (surface de genre 1). Plus précisément, pour un graphe de complexité n, le prétraitement en temps O(n^2 log log n) permet de calculer : pour un cycle à k arêtes, la longueur minimale d'un cycle homotope en O(k + log n); les k premières valeurs du spectre non-marqué en O(k * log n). Je vais aussi présenter des algorithmes pour tester l'égalité des spectres de deux graphes différents.


Lundi 9 janvier : Jean-François Marckert

Titre :Chaînes de Markov avec noyaux presque triangulaires sur N

Résumé : Les processus de naissances et morts sont des chaînes de Markov, à valeurs dans N, dont les incréments valent +1, - 1 ou 0. Leur matrice de transition sont dites "tridiagonales".

Dans une série de travaux des années 50, Karlin et McGregor donnent des CNS pour leur récurrence et récurrence positive. Ils calculent également leur mesure invariante (qui existe toujours et est unique pour tout noyau irréductible).

Dans ce travail, nous nous intéressons au modèle nettement plus général des chaînes sur N dont les noyaux sont dits presque triangulaires: -- presque triangulaires supérieures PTS: les incréments valent au moins -1 -- presque triangulaires inférieures PTI: les incréments valent au plus +1

Les tri-diagonales sont donc à l'intersection de ces 2 familles.

Pour ces 2 familles, on donne des CNS de récurrence, et récurrences positives. On calcule les mesures invariantes quand il y en a... et on observe que les PTS et les PTI sont très différentes.

Les méthodes sont principalement de nature combinatoire, et sont différentes de celles de Karlin et McGregor.

Travail commun avec Luis Fredes, IMB, Bordeaux

Lien vers l'article

Enregistrement


Lundi 12 décembre : Zoé Varin

Titre : Un système de particules : le modèle de golf sur ⚠ $\znz$ et sur ⚠ $\Z$.

Résumé : On considère un modèle de golf aléatoire, ou parking aléatoire, sur un graphe fini connexe. On assigne des balles et des trous à chaque sommet (aléatoirement ou non), puis les balles sont activées une par une, chacune réalisant une marche aléatoire jusqu'au premier trou libre qu'elle trouve. Sur les cycles (⚠ $\Z/n\Z$), on caractérise la loi des trous résiduels dans le cas où on tire uniformément une configuration avec des nombres de balles et de trous fixés. On peut alors étendre la définition du modèle à un graphe infini, ⚠ $\Z$, et on explicite également la loi des trous résiduels dans ce cas.

Transparents Enregistrement


Lundi 5 décembre : Carole Porrier

Titre :Aperiodic tilesets derived from cut and project tilings

Résumé : Ammann bars are formed by segments (decorations) on the tiles of a tiling such that forming straight lines with them while tiling forces non-periodicity. Only a few cases are known, starting with Robert Ammann's observations on Penrose tiles, but there is no general explanation or construction. We propose a general method for cut and project tilings based on the notion of subperiods and we illustrate it with an aperiodic set of 36 decorated prototiles corresponding to what we called Cyrenaic tilings. We also explore how to get aperiodic Wang tilesets from cut and project tilings with local rules. To illustrate this, we construct an aperiodic Wang tileset from a decomposition of golden octagonal tilings.

La première partie de l'exposé est basé sur https://arxiv.org/abs/2205.13973

Transparents Enregistrement


Lundi 28 novembre : Olivier Carton

Titre :Discrepancy and nested perfect necklaces

Résumé : M. B. Levin constructed a real number x such that the first N terms of the sequence b^n x mod 1 for n >= 1 have discrepancy ⚠ $O((log N)^2/N)$. This is the lowest discrepancy known for this kind of sequences. In this talk, we present Levin's construction in terms of nested perfect necklaces, which are a variant of the classical de Bruijn sequences. For base 2 and the order being a power of 2, we give the exact number of nested perfect necklaces and an explicit method based on matrices to construct each of them.

Transparents Enregistrement image


Lundi 21 novembre : Bastián Espinoza

Titre :An S-adic characterization of sublinear complexity subshifts

Résumé : In the context of symbolic dynamics, the class of "sublinear complexity subshifts" is of particular relevance as it occurs in a variety of areas, such as geometric dynamical systems, language theory, number theory, and numeration systems, among others. During the intensive study carried on this subject from the beginning the 90's, it was proposed that a hierarchical decomposition based on S-adic sequences that characterizes sublinear complexity subshifts would be useful to understand this class. The problem of finding such a characterization was given the name "S-adic conjecture" and inspired several influential results in symbolic dynamics. In this talk, I will present an S-adic characterization of sublinear complexity subshifts and some of its applications, which in particular give a solution to this conjecture.

Enregistrement


Lundi 14 novembre : Doriann Albertin

Titre : The canonical complex of the weak order

Résumé :The canonical join complex of a join-semidistributive lattice L is a simplicial complex whose faces are in bijection with the elements of L and record the canonical join representations in L. We introduce the canonical complex of a semidistributive lattice L, another simplicial complex containing both the canonical join and meet complexes, and whose faces are in bijection with intervals of L. Like the canonical join complex, the canonical complex is flag, and behaves well with quotients of L. In 2015, N. Reading introduced the non-crossing complex, a combinatorial model for the canonical join complex of the right weak order on permutations. Its faces are described with non-crossing arc diagrams. We focus in this talk on the example of the weak order, and extend this combinatorial model to a description of the canonical complex of the weak order, the semi-crossing complex, and its faces, the semi-crossing arc bidiagrams. This allows us to compute a generalization of the Kreweras complement on non-crossing partitions to all quotients of the weak order.

Transparents Enregistrement


Lundi 7 novembre 9h30 : Pierre Bonnet

Titre :Algébricité de modèles de marche à grands pas dans le quart de plan

Résumé : Depuis une vingtaine d'année, différents modèles de marches confinées dans un cône du plan sont étudiés. Notamment, la classification complète de la nature des séries génératrices pour les modèles à petits pas dans le quart de plan a été achevée. Dans ce cadre d'étude, on fournit dans cet exposé une preuve de l'algébricité des séries de deux modèles à grands pas, jusqu'alors conjectures algébriques, en introduisant de nouveaux outils issus de la théorie de Galois.

Transparents Enregistrement


Lundi 7 novembre 10h45 : Mélodie Andrieu

Titre :Complexities of hypercubic billiard words

Résumé : [Based on a joint work with Léo Vivion.]

Sturmian words (1940) form a class of infinite words over the binary alphabet which sheds light, through their various equivalent definitions, on the remarkable interactions between combinatorics, dynamical systems and number theory.

On larger alphabets, these definitions give birth to different classes of words (e.g.: Arnoux- Rauzy or episturmian words, words associated with d−dimensional continued fraction algorithms, polygonal or cubic billiard words, etc.) A large program, initiated by G. Rauzy (∼1980), is to determine whether some of these classes of words coincide, and which characteristic properties of Sturmian words they still satisfy.

In this talk, we will focus on a combinatorial quantity which characterizes Sturmian words, called abelian complexity, and compute it for words generated by a billiard in a cube of dimension d.


Lundi 10 octobre : Hugo Mlodecki

Titre :Un automorphisme bidendriforme de WQSym

Résumé : Grâce aux travaux de Foissy, on sait que l'algèbre de Hopf WQSym est isomorphe à sa duale car bidendriforme. Dans cet exposé nous montrons comment construire un isomorphisme bidendriforme combinatoire explicite. Pour ceci nous représentons deux décompositions récursives des mots tassés par deux nouvelles familles combinatoires appelées forêts biplanes rouge et bleue. On obtient alors deux bases de WQSym et sa duale. L'intérêt de ces bases est qu'en prenant des sous-ensembles explicites, on obtient des bases d'éléments primitifs et totalement primitifs. Nous combinons soigneusement les forêts rouges et bleues pour obtenir des forêts bicolores. Une simple recoloration des arêtes nous permet d'obtenir le premier automorphisme bidendriforme explicite de WQSym.

Transparents Enregistrement


Lundi 19 septembre : Sébastien Labbé

Titre : Paires asymptotiques indistinguables et configurations sturmiennes multidimensionelles

Résumé : Two asymptotic configurations on a full ⚠ $\mathbb{Z}^d$-shift are indistinguishable if for every finite pattern the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of ⚠ $\mathbb{Z}^d$. We prove that indistinguishable asymptotic pairs satisfying a ``flip condition'' are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together the two results provide a generalization to ⚠ $\mathbb{Z}^d$ of the characterization of Sturmian sequences by their factor complexity ⚠ $n+1$. Many open questions are raised by the current work which was made in collaboration with Sebastián Barbieri (https://arxiv.org/abs/2204.06413).

Transparents Enregistrement



Français English

Groupe

Événements

GT

* Années précédentes

Ressources

edit SideBar