Résumés des exposés

Pablo Arrighi : Quantum walks, cellular automata and relativistic space-time.

Résumé :

A Quantum Walk (QW) is an evolution of a single particle in discrete-time steps, on the lattice. They can be thought of as Cellular Automata (CA), where each cell contains a vector of complex numbers. Some QWs admit a continuum limit, leading to familiar PDEs (e.g. the Dirac equation), and thus provide us with discrete toy models of familiar particles (e.g. the electron): we recall these facts in very simple terms.
 
In continuous physics however, relativity imposes certain space-time symmetries (Lorentz covariance, general covariance) which seem to break down in discrete toy models. We introduce discrete Lorentz transforms for QWs and CA, and explain how discrete Lorentz covariance just boils down to some local, circuit equivalence rules, which the model has to respect. Time-allowing, we may also provide some intuition of QWs models of particles in curved space-time.

Francesco Dolce : Specular sets.

Résumé :

We introduce specular sets, a subclass of tree sets having particular symmetries.  We present two important families of specular sets: natural codings of linear involutions and sets obtained by a doubling transducer.  We prove several cardinality results, as well as some results concerning the subgroups generated by return words.  This is a based on a joint work with Valérie Berthé, Clelia De Felice, Vincent Delecroix, Julien Leroy, Dominique Perrin, Christophe Reutenauer and Giuseppina Rindone.

Fabien Durand : Décidabilité de la factorisation entre sous-shifts substitutifs.

Damien Gaboriau : Sofic entropy, after Bowen-Kerr-Li.

Guilhem Gamard : Some news about quasiperiodicity.

Résumé :

Bruno Gaujal : Analyse d’algorithmes par des systèmes dynamiques: l’exemple du collectionneur de coupons et de l’algorithme de meilleure réponse.

Résumé :

Dans cet exposé, je vais montrer comment on peut formuler le temps d’exécution moyen de certains algorithmes distribués comme solution d’un système d’équations différentielles.

L’approche que je vais présenter tient en deux étapes: la première consiste à modéliser l’exécution de l’algorithme comme une chaîne de Markov avec un état absorbant. La deuxième étape est la construction d’un système d’équations différentielles qui donne son temps moyen d’absorption.

Je vais illustrer cette technique avec deux algorithmes célèbres dont la complexité moyenne est inconnue (ou presque): le collectionneur de coupons (ou plutôt, de cartes Panini) et l’algorithme de meilleure réponse dans un jeu matriciel.

Dans le premier cas, le système différentiel est construit comme limite en champ moyen, et dans le deuxième cas, en utilisant l’équation de Poisson des temps d’atteinte.

(joint avec Nicolas Gast et Stéphane Durand)

Christian Gentil : Conception géométrique assistée par ordinateur de formes fractales.

Résumé :

Les formes fractales possèdent des propriétés spécifiques : surfaces infinies, structures « volumiques » de mesure nulle. Ces propriétés présentent un intérêt pour l'industrie comme par exemple pour la conception d'échangeurs thermiques ou la conception d'objets allégés. Les évolutions des procédés de fabrication additive rendent possible la matérialisation de ces formes et offrent l'opportunité de développer de nombreuses d'applications. Dans ce contexte, nous nous intéressons à la représentation et au développement d'outils et méthode d'aide à la conception géométrique assistée par ordinateur (CGAO) de formes fractales.
Classiquement, les formes fractales sont générées par des procédés itératifs de construction traduisant une propriété d'auto-similarité caractéristique de ces formes. Cela revient à subdiviser l'objet en plusieurs parties. Chaque partie subit à son tour une subdivision produisant de nouvelles sous-parties auxquelles le même traitement est réservé... Le nombre de règles de subdivision est généralement fini. Dans la pratique, chaque procédé de subdivision est réalisé par l'application d'un ensemble de transformations géométriques.

Le processus est simple et permet la génération de formes complexes souvent spectaculaires.

Cependant, la conception et le contrôle de ces formes sont peu aisés et peu intuitifs de par les concepts sous-jacents auxquels les concepteurs ne sont pas habitués. Peu d'outils standards de CGAO sont applicables ou définis pour ce type de formes.

Nous présentons le modèle BCIFS (Boundary Controlled Iterated Function System), dont le principe est de décrire la subdivision topologique des formes et de rendre indépendant le contrôle de la topologie et de la géométrie. Les formes sont paramétrées par des mots infinis. Les mots finis représentent des subdivisions de la forme. Nous introduisons alors une relation d'équivalence sur les mots finis pour définir des équivalences entre subdivisions et construire ainsi des raccords entre parties subdivisées. Ces raccords permettent de contrôler et de garantir la topologie des formes. Ces relations d'équivalences se traduisent par des contraintes sur les transformations géométriques. Les degrés de liberté restants sont utilisés pour ajuster la géométrie.

Nous avons développé un modeleur géométrique pour la conception et la fabrication de prototypes.

Elise Janvresse : Des suites de Fibonacci aléatoires aux beta-shift, en passant par les fractions continues.

Résumé :

Il est bien connu que les suites de Fibonacci croissent exponentiellement vite. En 2000, Viswanath a introduit les suites de Fibonacci aléatoires, définies par la relation de récurrence suivante : F(n+1)= F(n)±F(n-1) où le signe + ou - est donné par une suite de tirages à pile ou face. Nous nous intéresserons dans cet exposé à la croissance des suites de Fibonacci aléatoires. Leur lien avec les fractions continues nous amènera aussi à discuter des \beta-shifts.

Il s'agit d'un travail effectué en collaboration avec Benoît Rittaud (Paris 13) et Thierry de la Rue (Rouen).

Timo Jolivet : Questions de décidabilité en géométrie fractale et en dynamique des substitutions.

Résumé :

Nous passerons en revue quelques résultats de décidabilité sur les propriétés topologiques de certains ensembles fractals, utilisés dans l'étude des systèmes dynamiques liés à des substitutions. Nous mentionnerons ensuite certains problèmes d'indécidabilité qui peuvent survenir dans un cadre plus général.

Aude Maignan : Behavior analysis of a neighbor-dependent substitution system called DEM-System.

Résumé :

A substitution system called a DEM-system is presented. Deeply influenced by cellular automata (CA) and L-Systems, it has the structural flexibility of an L-system but can expand to higher dimensions and inherits algebraic properties of CA. The behavior of DEM- systems are discussed here in the case of a linear ring or chain. For the additive case, a partial partition into three finiteness classes is given. Interesting behaviors, such as reproduction, are exhibited.

Svetlana Puzynina : Ergodic infinite permutations.

Résumé :

Infinite permutations can be defined as equivalence classes of real sequences with distinct elements, such that only the order of elements is taken into account. In other words, an infinite permutation can be defined as a linear ordering of the set of natural numbers. We investigate a new natural notion of ergodic infinite permutations, that is, infinite permutations which can be defined by equidistributed sequences. We study complexity and substitutions on ergodic permutations.

Sylvain Sené : Réseaux d'automates et régulation biologique : un retour aux fondamentaux.

Résumé :

Nous nous intéresserons à un modèle de systèmes dynamiques discrets qui possède un ensemble de propriétés particulièrement pertinent pour la modélisation de systèmes biologiques comme les réseaux de régulation génétique : les réseaux d'automates. Ce modèle, entre autres, combine une simplicité de définition étonnante à la capacité de capturer la richesse comportementale et certaines des complexités intrinsèques inhérentes aux systèmes d'interactions réels, en permettant notamment de focaliser l'attention sur la transmission d'informations entre les entités qui les composent. Au delà de son appréhension sous l'angle de la modélisation de phénomènes naturels, ce modèle a également été largement étudié en tant que modèle de calcul du point de vue de l'informatique fondamentale. Dans cet exposé seront présentés quelques résultats majeurs du domaine, en lien avec les problèmes ouverts qui me semblent aujourd'hui essentiels d'aborder.