Discrete Mathematics & Computer Science: Groups, Dynamics, Complexity, Words
Mathématiques discrètes et informatique : mots, complexité, dynamique, groupes

29 January – 1st March, 2024


Scientific & Organizing Committee
Comité scientifique & d’organisation

Sebastián Barbieri (University of Santiago)
Julien Cassaigne (CNRS, Aix-Marseille Université)
Jérémie Chalopin (CNRS, Aix-Marseille Université)
Victor Chepoi (Aix-Marseille Université)
Anna Frid (Aix-Marseille Université)
Anahí Gajardo (University of Concepción)
Pierre Guillon (CNRS, Aix-Marseille Université)
Victor Lutfalla (Aix-Marseille Université)
Etienne Moutot (CNRS, Aix-Marseille Université)
Nicolas Ollinger (CNRS, IRIF)
Andrei Romashchenko (CNRS, Université de Montpellier)
Guillaume Theyssier (CNRS, Aix-Marseille Université)
Pascal Vanier (Université de Caen Normandie)

The interface of mathematics with computer science form a large, diverse and rich landscape. Of course, many classical mathematical tools and concepts turn out to be very useful to answer questions arising from computer science. Besides, the core objects of computer science (typically discrete) that were once considered non-classical in mathematics have now a well-established and growing theory. In addition, the main ideas of computer science (the very notions of computation and algorithmic complexity) yield new points of views and new questions on many mathematical objects.
   This thematic month proposes a walk along discrete mathematics and computation theory to explore both a range of mathematical objects (groups, symbolic dynamical systems, words, . . . ) and a range of notions from computer science (information, randomness, computability, complexity,. . . ) that share many strong links. To encourage participants (especially the youngest ones) to attend the entire month and foster interactions outside each one’s expertise zone, the first week will consist in a research school with in-depth introduction to the key objects and notions of the entire month.
   The month is then organized around four scientific pillars that will be the focus of four successive weeks:
Geometric and Asymptotic Group Theory with Applications (GAGTA 2024), on week 2, will be devoted to infinite groups, as they offer a meeting point of many fields: algebra, geometry, dynamical systems, graph theory and computability theory.
Complexity of Simple Dynamical Systems, on week 3, will be devoted to the interplay between dynamical systems theory and computability or complexity theory.
Randomness, Information & Complexity, on week 4, will study various connections between information and computation theory, ranging from communication complexity, information complexity and Kol- mogorov complexity, to pseud-random structures and computability.
Combinatorics on words, on week 5, will focus on finite and infinite words, linking discrete dynamics and number theory to computer science. One important topic will be automatic problem solving on words.
   All these subjects have a lot in common, and we chose to organize them in this order to have a coherent program for the whole month, empathizing particular interactions across the successive weeks. Here are some examples of these interactions. A major trend in symbolic dynamics is to consider tilings or cellular automata over arbitrary groups, or to study the group of automorphisms of a subshift. On another point of view, a striking similarity has been discovered in the last decade between the history of computational aspects of multidimensional symbolic dynamics and of group theory. Several notions of complexity coming from computation and information theory (like communication or Kolmogorov  complexity, or arithmetical hierarchy and Turing degrees) have been successfully used to analyze symbolic dynamical systems in complement to standard notions like  Kolmogorov-Sinaï) entropy. The link between dynamics and combinatorics on words is clear, for example through the trace object, or symbolic complexity as a refinement for entropy. It also presents strong connexion with computation, for instance in the decidability problems for some properties of substitutions, or the links with string compression.

Research School in Discrete Mathematics and Computer Science
École de recherche en mathématiques discrètes et informatique
29 January – 2 February, 2024

GAGTA, Geometric and Asymptotic Group Theory with Applications
Théorie des Groupes Géométrique et Asymptotique
5 – 9 February, 2024

Complexity of Simple Dynamical Systems
Complexité des Systèmes Dynamiques Simples
12 – 16 February, 2024

Randomness, Information & Complexity
Aléatoire, information et complexité
19 – 23 February, 2024

Combinatorics on words
Combinatoire des mots
26 February – 1st March, 2024