CNRS Institut de Mathématiques de Marseille
English glossary

👨 Pierre Guillon

I am not the Pierre Guillon who can review articles (or projects) on antennas or sensors…
Je suis chargé de recherche dans l'équipe GDAC de l'Institut de MAthématiques de Marseille.
Je m'intéresse, entre autres, à la dynamique (symbolique) des modèles de calcul : automates cellulaires, pavages, machines de Turing et autres bistrouillets étudiables sous l'éclairage d'une part de la dynamique topologique, de la théorie ergodique, de la géométrie des groupes, de la théorie des graphes, d'autre part de la théorie des langages, de la logique, de la calculabilité, des complexités…
Pour un étudiant : j'ai peut-être bien des idées de sujets de stage sur ces choses-là.

Contact : pguillonÀmath♫cnrs♫fr | IML Bureau 221, Campus de Luminy, Case 907, F-13288 Marseille cedex 9

🗒 Prochainement possiblement intéressant :

Écrit (liste thématique) :

Dynamique symbolique multidimensionnelle :

  • Infinite Communication Complexity, avec Emmanuel Jeandel
  • Surjective Cellular Automata Far from the Garden of Eden, avec Silvio Capobianco et Jarkko Kari
    (DMTCS, 15 (3) : 41-60, 2013).
    Résumé : Il existe, sur chaque groupe non moyennable, des automates cellulaires surjectifs qui ne préservent ni la mesure uniforme, ni les configurations normales, ni algorithmiquement aléatoires (inspiré par Bartholdi).
    Question liée : Existe-t-il, sur chaque groupe non sofique, un automate cellulaire injectif mais pas surjectif ?
  • Densities and Entropies in Cellular Automata, avec Χαρἀλαμπος Ζηνοβιἀδης
    (présenté à CiE 2012 ; version ici avec les schémas de preuve ; ce résultat est dans un état très temporaire et sera bientôt partie d'un article plus long ; si cela vous intéresse écrivez-nous).
    Résumé : Les entropies (topologiques) d'automates cellulaires sont les réels positifs calculables à droite (inspiré de Hochman…).
    Question liée : L'entropie d'un sous-shift peut-elle être plus complexe que son langage ?
  • Projective Subdynamics and Universal Shifts
    (présenté à Automata 2011).
    Résumé : Les sous-shifts effectifs universels (contenant un sofique d'entropie non nulle) unidimensionnels apparaissent comme la trace (ensemble des lignes) de SFT bidimensionnels. De plus, toutes les propriétés non triviales des traces sont indécidables.
    Question liée : Quelles sont les traces possibles d'entropie nulle ou apériodiques ?

Automates cellulaires :

  • Distorted Cellular Automata and One-head Machines, avec Ville Salo.
    (présenté à Automata 2017).
    Résumé : On s'attend à ce que le rayon (minimal) des itérés d'un automate cellulaire grandisse linéairement (ou ne grandisse pas, dans le cas équicontinu) ; si la croissance est effectivement assez contrainte, on peut toutefois construire, en passant par les machines de Turing, des exemples où il grandit logarithmiquement ; sur des sous-shifts on peut simultanément faire baisser encore plus le semi-rayon (que la règle doit regarder en ayant la connaissance complète de l'autre côté de la configuration).
    Question liée : Mais quelles sont les croissances possibles pour le rayon des itérés ?
  • Limit Sets of Stable and Unstable Cellular Automata, avec Alexis Ballier et Jarkko Kari.
    (Fundamenta Informaticæ, 110 : 1-12, 2011).
    Résumé : Il existe deux automates cellulaires avec le même ensemble limite, l'un l'atteignant en temps fini, l'autre en temps infini (répondant à Maass).
    Question liée : Quels sont les ensembles limites stables ? Sont-ils tous les facteurs du full shift ?
  • Clandestine Simulations for Cellular Automata, avec Pierre-Étienne Meunier et Guillaume Theyssier
    (présenté à JAC 2010 ; ici avec annexes en plus).
    Résumé : La simulation par facteurs (voir notamment Theyssier…) préserve la simplicité de l'ensemble limite et des facteurs sous-shifts. En revanche, il existe des automates cellulaires très puissants pour la simulation par sous-automate et qui ont des ensembles limites ou des facteurs sous-shifts très simples.
    Question liée : La simulation par sous-automate préserve-t-elle la soficité de l'ensemble limite ? la stabilité ?
  • Traced Communication Complexity of Cellular Automata, avec Eric Goles et Ivan Rapaport
    (TCS, 412 (30) : 3906-3916, 2011 ; prolongement d'une version présentée à Automata 2009).
    Résumé : La complexité de communication du problème "un 0 apparaît-il dans la trace ?" présente plus de liens avec la dynamique topologique que les problèmes précédemment étudiés (depuis Rapaport…). Notamment, elle est constante en présence d'équicontinuité, exponentielle pour certaines formes d'expansivité, et essentiellement bornée par l'entropie.
    Question liée : Peut-on avoir une complexité de communication constante sans avoir un problème de prévision NC⁰ ?
  • Revisiting the Rice Theorem of Cellular Automata, avec Gaétan Richard
    (corrigé depuis sa présentation à STACS 2010).
    Résumé : Toutes les propriétés non triviales des ensembles limites d'automates cellulaires binaires sont indécidables, sauf la surjectivité (ramené au cas binaire depuis Kari).
    Question liée : Peut-on caractériser élégamment les propriétés décidables sur les SFT bidimensionnels ?
  • Asymptotic Behavior of Dynamical Systems and Cellular Automata, déjà avec Gaétan Richard
    (contient entre autres une généralisation de Nilpotency and Limit Sets of Cellular Automata, présenté à MFCS 2008).
    Résumé : Les automates cellulaires dont toutes les orbites convergent vers la même configuration, ou bien dont l'ensemble limite ne contient que des configurations finies, sont nilpotents.
    Question liée : L'ensemble asymptotique d'un automate cellulaire peut-il être dense sans être plein ?
  • Ultimate Traces of Cellular Automata, avec Julien Cervelle et Enrico Formenti
    (présenté à STACS 2010 ; ici avec annexes en plus ; suite de Towards a Rice Theorem on Traces of Cellular Automata, présenté à MFCS 2007, et Sofic Trace of a Cellular Automaton, présenté à CiE 2007).
    Résumé : À étapes de temps initiales près, les sofiques unidimensionnels d'entropie positive et les SFT unidimensionnels sont les traces d'automates cellulaires (des facteurs sous-shifts, comme dans Kůrka); les propriétés non triviales des traces sont indécidables.
    Question liée : Mais quelles sont les traces plus complexes ? quand on impose aussi les étapes de temps initiales ?
  • Automates cellulaires : dynamiques, simulations, traces, thèse de doctorat
    à Paris-Est devant Marie-Pierre Béal, Valérie Berthé (examinatrices), Julien Cervelle, Enrico Formenti (directeurs), Nataša Jonoska, Luciano Margara (rapporteurs), Jacques Mazoyer
    (english summary ou version complète + résumé anglais).

Autres modèles :

Divers :

🚂 Passé

J'ai donné un cours de Dynamique Symbolique à l'école Tilings & Tesselations du CIMPA à اصفهان en 2015, au MDFI en 2013, et 2017 avec Anna Frid, et de Systèmes dynamiques en M1 en 2011 avec Emmanuel Beffara.
Parfois, j'interviens à l'IREM pour des Stages Hippocampe, ou encadre des ateliers MATh.en.JEANS.
Auparavant, j'avais enseigné plutôt de l'informatique.

Dans le temps, je cherchai au FUNDIM (Turun Yliopisto), au CMM (Universidad de Chile), au LIGM (Université Paris-Est Marne la Vallée).

Liens

something still unclear? ask me