✍Écrit (liste thématique ; sinon voir HAL) :

Dynamique symbolique et topologique :

• ⊞ Various questions around finitely positively expansive dynamical systems , avec Silvère Gangloff et Piotr Oprocha
• ⊞ Dill maps in the Weyl-like space associated to the Levenshtein distance, avec Firas Ben Ramdhane
  (Automata 2023)
  lié au travail similaire : Cellular automata and substitutions in topological spaces defined via edit distances, avec Firas Ben Ramdhane (Natural Computing, version étendue d'un exposé à Automata 2021)
• ⊞ The Generic Limit Set of Cellular Automata, avec Saliha Djenaoui
  (version erronée publiée au Journal of Cellular Automata, 14 : 435-477, 2019)
  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 ?
• ⊞ Distortion in One-Head Machines and Cellular Automata, 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).
  Un petit bout a été traduit en le chapitre Canonical Factor of Cellular Automata, du livre Cellular Automata (Nova Publishers, 2011).

Dynamique et calcul :

• ⊞ Hardness of monadic second-order formulae over succinct graphs, avec Guilhem Gamard et al, Kévin Perrot et Guillaume Theyssier
  à comparer avec une version non déterministe FO : Rice-Like Theorems for Automata Networks (STACS), des mêmes auteurs.
• ⊞ Infinite Communication Complexity, avec Emmanuel Jeandel
• ⊞ Densities and Entropies in Cellular Automata, avec Charalampos Zinoviadis
  (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 :

• ⊞ Graph subshifts, avec Pablo Arrighi et Amélia Durbec.
• ⊞ Besicovitch pseudodistances with respect to non-Følner sequences, avec Silvio Capobianco
  Résumé : La pseudodistance de Besicovitch parle de la densité de différence entre deux configurations (ou coloriages), selon une suite de parties finies.
• ⊞ Uncomputable Word Problem in Subshift Automorphism Groups, avec Emmanuel Jeandel et al, Jarkko Kari et Pascal Vanier
  Résumé : Dans un SFT bidimensionnel, le problème du mot du groupe d'automorphismes peut être indécidable. En fait il peut être de n'importe quel degré borné par le colangage, sur n'importe quel groupe.
  Question liée : Cela reste-t-il vrai si le groupe d'automorphismes est finiment engendré ?
• ⊞ On the Cost of Simulating a Parallel Boolean Automata Network by a Block-sequential one, avec Florian Bridoux et al, Kevin Perrot, Sylvain Sené et Guillaume Theyssier
  présenté à TAMC 2017.
  Question liée : Combien d'automates au maximum sont nécessaires pour espérer simuler (en asynchrone) n'importe que réseau de taille n (synchrone) ?
• ⊞ 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 ?

Divers :

• ⊞ Comparison of max-plus automata and joint spectral radius of tropical matrices, avec Laure Daviaud et Glenn Merlet
  présenté à MFCS 2017.
  Question liée : Quelle est la classe des réels réalisables comme rayons spectraux joints ?
• ⊞ The Ultimate Rank of Tropical Matrices, avec Zur Izhakian, Glenn Merlet et Jean Mairesse
  (JA, 437 : 222-248, 2015, extension d'une présentation à Tropical and Idempotent Mathematics).
  Résumé : Une matrice tropicale admet plusieurs définitions différentes du rang, mais elles partagent toutes le même minimum sur les puissances projectives. Ce "rang ultime" est calculable en temps polynomial, et s'étend à une notion sur les semi-groupes, qui se voit de façon assez naturelle combinatoriellement et géométriquement.
  Question liée : Quelle est la bonne définition ?
• ⊞ Gene Maps Linearization using Genomic Rearrangement Distances, avec Guillaume Blin et al, Éric Blais, Danny Hermelin, Mathieu Blanchette et Nadia El-Mabrouk
  (JCB, 2007, basé sur la présentation Inferring Gene Orders from Gene Maps using the Breakpoint Distance à RECOMB-CG 2006).
  Résumé : Savoir linéariser un ordre partiel aussi prêt que possible (pour la notion de distance de cassure de) d'un ordre total est un problème NP-complet, mais une heuristique peut toutefois être efficace.
  Question liée : C'est quoi le rapport ?