Exposés longs:
Mélodie Andrieu (Université du littoral)
Titre: Complexité abélienne des mots engendrés par un billard dans un hypercube
Résumé: Les mots Sturmiens (1940) sont des mots infinis binaires qui, à travers leurs définitions équivalentes, mettent en lumière des interactions remarquables entre combinatoire, systèmes dynamiques et arithmétique.
Ces définitions donnent naissance à différentes classes de mots sur l’alphabet à d lettres : mots d’Arnoux-Rauzy et mots épisturmiens, classes de mots associées à des algorithmes de fraction continue en dimension d, mots engendrés par un billard polygonal ou cubique, etc. Une question générale est de déterminer quelles propriétés des mots Sturmiens sont encore satisfaites par ces classes de mots.
Dans cet exposé, on intéressera à une quantité combinatoire qui caractérise les mots Sturmiens, la complexité abélienne, et on la calculera pour les mots engendrés par un billard dans un cube de dimension d.
Nicolas Bédaride (I2M-Université Aix-Marseille)
Titre: Transfert de mesures via une substitution
Résumé: Dans cet exposé on s'intéressera à des sous shifts substitutifs voire S adiques et on étudiera leurs mesures ergodiques.
Emilie Charlier (Université de Liège)
Titre: About alternate base expansions
Résumé: The link between positional numeration systems for representing integers and real base numeration systems for representing real numbers is well known and well studied since the 1980’s. Alternate base numeration systems are a generalization of real base numeration systems as defined by Renyi which naturally appear when considering linear numeration systems without a dominant root. Many results happen to generalize to these numeration systems but some don’t. In this talk, I will attempt to present a survey of the work done so far concerning combinatorial, dynamical and algebraic aspects. This study has been led in collaboration with several co-authors : Célia Cisternino, Karma Dajani, Savinien Kreczman, Zuzana Masakova and Edita Pelantova.
Daniel Graca Title: Continuous robust simulation of Turing machines on low-dimensional dynamical systems
Abstract: In this talk we will analyze the problem of finding the minimum dimension over which a discrete-time/continuous-time dynamical system defined over the real space can simulate a Turing machine. In particular, we will consider this problem for (i) simulations which are robust to perturbations (i.e. which do not break down on the presence of a small amount of "noise") and (ii) for which the dynamics is analytic (as it happens in many physically realistic systems). We show that one-dimensional analytic maps are sufficient to robustly simulate Turing machines. On the other hand, under some reasonable assumptions, the minimum dimension needed to robustly simulate Turing machines with analytic ordinary differential equations is two. We also show that any Turing machine can be simulated by a smooth two-dimensional ordinary differential equation on the compact sphere. Talk based on joint work with Ning Zhong.
Kevin Perrot (LIS-Université Aix-Marseille)
Title: Computational complexity of automata networks
* Abstract: Automata networks (ANs) are discrete dynamical systems composed of interacting entities. Each entity (automaton) is equipped with a finite set of possible states and a local transition function telling its next state, provided the states of its neighbors. Basically at each step all automata update their state synchronously, but other update policies can be considered. We will survey some advances in the computational complexity of such systems, through two kinds of problems. (1) Given an AN, how hard is it to decide whether its dynamics verifies a given property? (e.g. does it have a fixed point? no limit-cyle of length three? is it reversible/injective?) We will see that logic of graphs allows to state complexity lower bounds for large families of such questions at once. (2) Given only the architecture of interactions (neighborhood relationship as a directed graph), what can be said on the dynamics? In this case many ANs are possible, and reductions are tricky. We will make some detour around the encodings of local functions and succinct graph representations, and state some open problems (if someone in the attendance knows for which class the problem "given a propositional formula φ(x,y), does for all x there is a unique y such that φ(x,y) is true?" is complete, please tell me!).
Andrei Romashchenko (LIRRM-Université de Montpellier)
Title: SFT with embedded computations, controlled information flows, and limits of soficness.
Abstract: Many work on multidimensional subshifts prove results of the following type: for each value of some specific parameter (e.g., topological entropy) that belongs to a certain class (e.g., for all upper-computable real numbers), there exists a sofic multidimensional subshift that provides this value of the parameter (e.g., all upper-computable numbers can be realized as entropy of a sofic subshift, as shown by Hochman and Meyerovitch). These proofs typically follow the natural general scheme: we construct a suitable SFT that provides "transfer" and subsequent algorithmic "processing" of information which certifies that a factor of this SFT is indeed a sofic subshift with the desired property. We will discuss bottlenecks and limitations of these techniques and open problems connected with these limitations.
Exposés courts:
Alexey Barsukov
Titre: TBA
Pierre Béaur (LISN-Université Paris-Saclay)
Titre: Walking On A Line: comment détecter des marches S-adiques dans des ω-automates
Abstract: Deux méthodes classiques coexistent en dynamique symbolique 1D pour construire des mots infinis et les structures discrètes associées. La première est la méthode substitutive de Thue, qui consiste à itérer un morphisme sur une lettre initiale : cette méthode est généralisée par celle des représentations S-adiques, où on peut alterner entre plusieurs substitutions. La seconde méthode consiste à considérer les marches infinies sur un graphe étiqueté (ou ω-automate), ce qui correspond en dynamique aux sous-shifts sofiques.
Dans cette présentation, je m'intéresserai à des questions de décidabilité à l'intersection entre ces deux points de vue. Étant donné un ω-automate A et une substitution σ, est-ce que A accepte un mot substitutif généré par σ ? En utilisant des méthodes de théorie des langages formels, je construirai un outil qui permet de décider ce problème. Cet outil peut être généralisé aux représentations S-adiques pour résoudre de nouvelles questions : étant donné un ω-automate A, est-ce que A accepte un mot sturmien ? un mot d'Arnoux-Rauzy ? Cet outil permet aussi d'obtenir une caractérisation des représentations S-adiques des mots acceptés par un ω-automate et sur la combinatoire des mots sturmiens.
Bitar Nicolás
Title: Realizability of Subgroups by SFTs
Abstract: Strongly aperiodic (SA) SFTs have been an object of interest ever since the proof of the undecidability of Domino Problem by Berger in 1962. Since then, numerous finitely generated groups have been shown to admit SA SFTs, as well as obstructions to their existence. Viewed from a different angle, these SFTs can be seen as subshifts in which every stabilizer is the trivial subgroup. Can this be done for other subgroups ? Given a subgroup H, does there exist a SFT such that all stabilizers are H ? What sets of subgroups can appear as the set of stabilizers of some SFT ? In this talk we will explore these questions and introduce some dynamical, algebraic and computational restrictions to the realizability of these sets.
Antonin Callard (Greyc-Université de Caen)
Title : Pattern complexity, aperiodic domino problem and group geometry
Abstract: (Joint work with Benjamin Hellouin de Menibus and Ville Salo).
The Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. We consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling?
In this talk, we relate the pattern complexity of subshifts with the aperiodic Domino problem by proving the following: if a subshift on Z^d has infinite "surface entropy" (in particular, if it has positive entropy), then it contains an aperiodic configuration. We then generalize this result from Z^d to some other groups by introducing a new geometrical notion of "confluence" for ordered group.
Nicanor Carrasco
Titre: Medvedev degrees of effective subshifts on groups
Abstract: It is known that the class of effective subshifts in Z can attain al /Pi_1 Medvedev degrees. In this talk we will discuss how this result extends to the class of finitely generated groups with decidable word problem.
This involves codifying translation-like actions by Z as a subshift, and takes us to the problem of the computability of translation-like actions on locally finite graphs.
Silvère Gangloff
Titre: Caractérisation des systèmes dynamiques "lents" sur le Cantor:
Résumé: Avec Piotr Oprocha, nous avons étudié la question de quels systèmes dynamiques sur le Cantor peuvent être vus comme un sous-système
d'un système de l'intervalle dérivable de telle manière que la dérivée est nulle partout sur le Cantor (on dit qu'un tel système est lent). Il était déjà connu que tout système minimal sur le Cantor satisfait cela. La preuve utilise la représentation de Gambaudo-Martens des système minimaux sur le Cantor. Nous avons caractérisé complètement les systèmes lents comme ceux dont toutes les orbites finies sont des attracteurs. Je présenterai ce résultat et les idées derrière la preuve de ce résultat.
Benjamin Hellouin
Title: The domino problem on rhombus subshifts
Abstract: We prove that the domino problem is undecidable for rhombus-shaped Wang tiles even when the tiles are forced to belong to some geometrical subshift, such as the Penrose tiling. In other words, we work with fixed "geometrical" constraints and input "symbolic" constraints, and the domino is undecidable for any geometrical constraints. The reduction proceeds by finding a subsytem of the geometrical tiling and a shape whose occurences in every tiling form a copy of Z^2, giving a reduction to the classical Z^2 case. This is a joint work with Victor Lutfalla.
Bastien Laboureix (LORIA-Nancy)
Titre : Connexité des hyperplans arithmétiques
Résumé : Les mots sturmiens possèdent de nombreuses définitions équivalentes en dimension 2, à travers la complexité en facteurs, le billard, les droites, les cercles, etc. Parmi toutes ces possibilités, nous nous intéressons à la définition géométrique, notamment aux droites discrètes et à leur généralisation en dimension d : les hyperplans arithmétiques. La géométrie discrète étudie ainsi différentes structures géométriques dans Z^d comme des droites, des hyperplans ou des polytopes. Plus particulièrement, nous travaillons sur la connexité des hyperplans arithmétiques. De nombreux travaux ont été menés sur ce sujet depuis 20 ans, en lien notamment avec la dynamique des algorithmes de PGCD, la fractale de Rauzy ou la théorie des langages. Pour résoudre le problème de connexité des hyperplans arithmétiques, nous montrons que la connexité obéit à un phénomène de percolation et étudions analytiquement la fonction épaisseur critique de connexité associée. Cette fonction est discontinue en tout rationnel mais sa restriction aux irrationnels est continue. Le graphe de la fonction fait notamment apparaître des fractales sous-jacentes proches du triangle de Sierpinski et reflétant la dynamique d'algorithmes de PGCD. Nous proposons enfin un algorithme pour calculer l'épaisseur critique de connexité.
Jérôme Durand-Lose
Titre: Fonctions primitives récusrsives sur les mots avec/sans concaténation
Résumé: Dans cet exposé nous revisitons les schémas de récusions primitive en ne les basant plus sur les entiers mais sur les mots (sur un alphabet fini). Dans un premier temps, nous montrons que cela permet une approche plus informaticienne de la chose et ainsi que de faire des liens avec les classes de complexité classiques. Dans un second temps, nous nous intéressons au cas où la concaténation n'est plus disponible et montrons qu'il est néanmoins possible de décider des langages non triviaux.
Anna Frid
Titre: La longueur palindromique d'un mot automatique n'est-elle pas toujours automatique?
Ricardo Gossi
Titre: TBA
Alonso Herrera:
Titre: Embedding Universal Turing Machines in the Dynamics of Smooth Maps
Abstract: The computable properties of dynamical systems arise naturally in many contexts and is an extensively studied subject. The opposite direction, that is, the ability dynamical systems have to perform computations, is a less travelled road. With Cristobal Rojas we investigated the abundancy of systems whose dynamics can simulate a Turing machine in the restrictive class of diffeomorphisms of the disk. In this talk we will survey Moore's generalized shifts construction and use it to modify any given disk diffeomorphism such that arbitrarily close to it, there is one that can simulate a Turing machine. As a corollary we obtain that non-statistical systems are everywhere in the space.
Etienne Moutot
Titre: Pavages et diagrammes
Résumé:Dans cet exposé, nous verrons les pavages sous formes de diagrammes, mais pas forcément ceux dont nous avons l'habitude à SDA2.
Le comptage du nombre de pavages par dimères est un problème combinatoire classique, et relativement bien compris dans le cas des grilles ou des graphes planaires par exemple, où Kasteleyn, Fisher et Temperley ont résolu de nombreuses questions. Dans cet exposé, je montrerai un nouveau lien entre ce problème et les diagrammes du ZW-calcul, initialement inventés pour répondre à des questions de calcul quantique. Ce lien permet par exemple de dénombrer des couplages parfaits en utilisant des techniques de réécriture de diagrammes. En étudiant un fragment bien choisi du ZW-calcul, je montrerai qu'il est notamment possible de trouver un nouvel algorithme de comptage des dimères sur un graphe planaire, à base d'opérations locales purement diagrammatiques.
Tout l'exposé est basé sur des travaux avec Titouan Carette, Thomas Perez et Renaud Vilmart.
Matthieu Rosenfeld
Titre: Word reconstruction using queries on subwords or factors
Abstract: I will present some results that we recently obtained about word reconstruction problems. In our setting, you can ask queries to an oracle about the number of occurrences of any given subword in an unknown word w, and the task is to reconstruct w in as few queries as possible. Fleischmann, Lejeune, Manea, Nowotka and Rigo, showed that for a binary word w of length n, it is always possible in at most n/2 +1 queries. We prove that O((n log n)^(1/2)) queries suffices. In this talk, I will provide the few necessary definitions and present this result.
This is joint work with Gwenaël Richomme.
Léo Paviet Salomon (Greyc-Université de Caen)
Titre: Le groupe fondamental projectif des Hom-shifts
Abstract:
Un sous-shift, ou sous-décalage, est un ensemble de pavages de Z^d, c'est-à-dire un ensemble de coloriages qui respectent des contraintes locales. En dimension 2 ou supérieure, la plupart des problèmes de décision "naturels" sur les sous-shifts sont indécidables -- par exemple le problème du domino: étant donné un ensemble fini de couleurs et de règles d'adjacence à respecter, déterminer s'il existe un pavage infini respectant ces contraintes. En dimension 1, beaucoup de ces problèmes sont cependant décidables : en effet, on peut représenter les contraintes d'adjacence par un graphe, et beaucoup de questions portant sur les configurations infinies du sous-shift se reformulent en questions portant sur ce graphe.
Ces remarques motivent la définition des Hom-shifts [Chandgotia, 2014] : ce sont des sous-shifts en n'importe quelle dimension définis à l'aide d'un graphe, ou de façon équivalente, dont les contraintes sont invariantes par rotations et symétries. Cette structure additionnelle permet de décider de nombreux problèmes sur cette classe particulière de sous-shifts, même en haute dimension.
Dans cet exposé, nous étudierons un invariant de conjugaison: le groupe fondamental projectif [Geller, Propp, 1995]. De façon analogue au groupe fondamental usuel, il est défini en utilisant une notion de boucles et de chemins entre motifs et configurations, et une notion de déformation. Dans le cas particulier des Hom-shifts, on montrera comment ce groupe peut être calculé, en adaptant au contexte des sous-shifts des techniques de théorie des graphes.
Pierre Stas (Université de Liège)
Titre: Return Groups of Eventually Dendric Shifts.
Abstract: Since 2015, dendric shifts (a generalisation of Sturmian words) have been widely studied. One of the results concerning these shift spaces is the return theorem. It describes the groups generated by the return words of a dendric shift. The proof uses the fundamental group of the Rauzy graph of the shift space. Later, eventually dendric shifts were introduced. They are of utmost importance because, unlike dendric shifts, they are stable under conjugacy. This key feature makes eventual dendricity a dynamical property. It seems natural to investigate if results similar to the return theorem hold in the eventually dendric case.
The aim of this presentation is to introduce return groups and dendricity. It will also contain new results concerning the return theorem in the case of eventually dendric shifts and showcase the tools used to prove it.
