THEMATIC MONTH - MOIS THÉMATIQUE :  Discrete Mathematics & Computer Science: Groups, Dynamics, Complexity, Words / Mathématiques discrètes et informatique : mots, complexité, dynamique, groupes

Collection THEMATIC MONTH - MOIS THÉMATIQUE : Discrete Mathematics & Computer Science: Groups, Dynamics, Complexity, Words / Mathématiques discrètes et informatique : mots, complexité, dynamique, groupes

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.

Organizer(s) 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)
Date(s) 29/01/2024 - 01/03/2024
linked URL
Give feedback