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.
En 2018-2019, je suis à Moscou.
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 des étudiants : j'ai des idées de sujets de stage sur ces choses-là ; écrivez-moi.

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 et topologique :

  • The Generic Limit Set of Cellular Automata, avec صليحة جناوي
    (soumis)
    Résumé : Dans un système dynamique topologique, il existe un plus petit fermé vers lequel converge les orbites (topologiquement) génériques. Celles-ci contiennent les orbites équicontinues. Si le système est sensible, alors cet ensemble est infini; s'il est semi-transitif, alors c'est l'ensemble limite. Dans le cas des automates cellulaires, l'ensemble est un sous-shift, et s'il y a des directions quasi-équicontinues à droite et à gauche alors c'est une orbite périodique.
    Question liée : Comment sont reliés les ensembles limites génériques d'un même automate cellulaire, quand on le compose avec des décalages différents ?
  • 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 prépériodique) ; 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 ?
  • 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é ?
  • Sand Automata as Cellular Automata, avec Alberto Dennunzio et Benoît Masson
    (TCS, 410 (38-40) : 3962-3974, 2009, concaténation de Stable Dynamics of Sand Automata, présenté à IFIP-TCS 2008, et Topological Properties of Sand Automata as Cellular Automata, présenté à JAC 2008).
    Résumé : Les automates de sable (définis dans Cervelle…) peuvent être vus comme des automates cellulaires sur un SFT bidimensionnel binaire très simple. En particulier, on peut définir une notion de nilpotence, qui est indécidable.
    Question liée : Existe-t-il un automate de sable non sensible mais sans point d'équicontinuité ?
  • Asymptotic Behavior of Dynamical Systems and Cellular Automata, 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 ? La réponse est oui : > va vers la droite, mange des R et écrit des L. Si elle trouve autre chose que R sur son passage, elle se transforme en <, et fait exactement l'inverse. L'AC est réversible, donc son ensemble asymptotique est résiduel, mais ne contient pas les configurations qui se terminent par >RRRRR... ou commencent par ...LLLLL< .
  • 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).

Dynamique et calcul :

  • Infinite Communication Complexity, avec Emmanuel Jeandel
  • 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 un jour 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 ?
  • Zigzags in Turing Machines, avec Anahí Gajardo
    (présenté à CSR 2010 ; ici avec annexes et corrections).
    Résumé : Les machines de Turing peuvent être vues comme des systèmes dynamiques (comme dans Kůrka) ; il y a alors un lien très fort entre leurs points d'équicontinuité, la complexité du langage de facteurs sous-shifts et les mouvements possibles de la tête.
    Question liée : Quelle est la classe des entropies des machines à ruban mobile ?
  • 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 ?
  • 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 ?

Dynamique et combinatoire :

Divers :

💡Intérêts actuels (non exhaustif)

🚂 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.
J'intervenais parfois ces dernières années à 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