Les journées du groupe de travail SDA2 auront lieu à Nancy les 9 et 10 avril à Nancy (au Loria, campus scientifique de l'Université de Lorraine) . Elles seront précédées d'une journée FRAC le 8 avril, rencontre semestrielle francophone autour des thèmes "systèmes complexes et modèles de calcul", historiquement soutenue par le projet ANR EMC.

Les journées sont organisées avec le soutien du département Méthodes Formelles du LORIA.

Dates importantes

  • Déroulement des journées: 8-10 avril 2014.

  • Date limite d'inscription: 2 avril.

  • Date limite de soumission d'exposé: 2 avril.

Thématiques principales

  • Dynamique symbolique, automates et langages formels, automates cellulaires, pavages et numération

  • Systèmes dynamiques a événements discrets: aspects logiques, temporels et probabilistes,

  • Modélisation et analyse en moyenne des algorithmes par des systèmes dynamiques.

Orateurs invites

  • Laurent Bartholdi, Georg-August-Universität Göttingen

  • Marie-Pierre Beal, Universite Paris-Est Marne-la-Vallee

  • Michel Coornaert, Universite de Strasbourg

  • Loick Lhote, Universite de Caen Basse Normandie

Programme

8 avril - FRAC - 10h30 - 18h - C005

[10h00-10h45]
Pause café - Accueil
[10h45-11h35]
Martin Delacourt - Calculabilité des ensembles mu-limites
[11h35-12h25]
Benjamin Hellouin - Rock-Paper-Scissors: Self-organisation in the gliders and 3-state cyclic cellular automaton [Résumé]
We consider a simple one-dimensional cellular automaton on Z/3Z whose local update can be described as a cyclic prey/predator relationship (rock-paper-scissors). Iterating this automaton on a configuration drawn at random produce a self-organizing behaviour: homogeneous clusters with a single state grow larger and larger. To determine precisely the rate of growth of these clusters and of convergence to the limit measure, we introduce a related random walk process and approximate it with a Brownian motion. This does not fully describe the limit measure, however, and an interesting phenomenon arises when the initial measure is independant and biaised: the frequency of each state converges to the initial frequency of its "prey". We will prove this result by refining the previous probabilistic tools.
[12h30-14h00]
Déjeuner
[14h00-14h45]
Simon Martiel - Causal Dynamics of Discrete Manifolds [Slides] [Résumé]
We formalize the intuitive idea of a discrete manifold which evolves in time, subject to two natural constraints: the evolution does not propagate information too fast; and it acts everywhere the same. The talk will proceed as follows. First, we summarize earlier results on Causal Graph Dynamics, a model which generalizes Cellular Automata to time-varying, bounded degree graphs. Second, we explain how a subclass of these bounded degree graphs can be interpreted as being the dual of a simplicial complex, where attention must be paid to discrepancies between geometrical distance and graph distance, as well as the appearance of torsion. Third, we provide provide an equivalent to the notion of Pachner moves upon these graphs, so that we are able to characterize homeomorphism in a purely combinatorial manner, and hence the notion of combinatorial manifold. Last, we report on our progress towards proving that the local rules which map combinatorial manifolds to combinatorial manifolds are enumerable.
[14h45-15h15]
Bastien Le Gloannec - Deterministic tilings, periodicity and undecidability [Slides] [Résumé]
The most fundamental undecidable question on tilings is the Domino Problem that asks whether a Wang tileset tiles the discrete plane. Lukkarila proved in 2009 that it remains undecidable when restricting the input to thape class of 4-way deterministic tilesets. Due to the existence of aperiodic tilesets, the most natural distinct variant of this problem is the Periodic Domino Problem which asks whether a Wang tileset admits a periodic tiling of the plane. This problem is also undecidable. Jeandel recently discovered a new and elegant proof for this result. Inspired by this new proof technique and some ingredients from Lukkarila's construction, we prove that it remains undecidable when restricted to 4-way deterministic tilesets.
[15h15-16h00]
Pascal Vanier - Degrés Turing des ensembles limites d'automates cellulaires [Article] [Résumé]
Les automates cellulaires sont des systèmes dynamiques discrets ainsi qu'un modèle de calcul. L'ensemble limite d'un automate cellulaire est constitué des configurations ayant une suite infinie de préimages. On sait qu'ils contiennent toujours un point calculable et que toute propriété non triviale à leur propos est indécidable. Nous allons donner une caractérisation complète des ensembles de degrés Turing pouvant être des ensembles de degrés Turing d'ensembles limites d'automates cellulaires : ce sont exactement les mêmes que les ensembles de degrés Turing des ensembles effectivement clos contenant un point calculable.
[16h00-16h30]
Pause café
[16h30-18h00]
FRAC: perspectives

9 avril - SDA2 - 10h30 - 18h - C005

[10h00-10h30]
Accueil - Pause café
[10h30-11h30]
Michel Coornaert - Décalages et sous-décalages à configurations périodiques denses [Slides] [Résumé]
Après avoir passé en revue quelques résultats classiques sur le problème de la densité des configurations périodiques dans les décalages et les sous-décalages, je décrirai une classe de sous-décalages de type fini fortement irréductibles dans lesquels les configurations périodiques sont denses (travail en collaboration avec Tullio Ceccherini-Silberstein).
[11h30-12h00]
Nazim Fates - Reversibility of Elementary Cellular Automata Under Fully Asynchronous Update
[12h00-12h45]
Nicolas Ollinger - A Small Minimal Aperiodic Reversible Turing Machine [Slides]
[12h45-14h15]
Déjeuner
[14h15-15h15]
Laurent Bartholdi - Automates: groupes, pavages et systèmes dynamiques holomorphes [Slides] [Article] [Résumé]
J'expliquerai comment les automates transducteurs sont un point charnière entre la théorie des groupes, les pavages autosimilaires et la théorie de l'itération d'une fonction holomorphe. Je montrerai en particulier comment les automates ont permis de résoudre algorithmiquement le problème de Douady-Hubbard sur les "lapins aux oreilles tordues".
[15h15-16h00]
Emmanuel Jeandel - Infinite Communication Complexity [Slides]
[16h00-16h30]
Pause café
[16h30-18h00]
SDA2: prospectives.

10 avril - SDA2 - 10h00 - 15h00 - C005

[9h30-10h00]
Café introductif
[10h00-11h00]
Loick Lhote - Modélisations de l'algorithme LLL et de ses entrées par des systèmes dynamiques [Slides] [Résumé]
Intuitivement, un réseau est un ensemble de points régulièrement disposés dans l'espace. En pratique, les réseaux sont représentés par une base formée de vecteurs linéairement indépendants. Un réseau admet une infinité de bases et réduire un réseau consiste à construire une bonne base ayant des vecteurs assez courts et assez orthogonaux à partir d'une base quelconque. L'algorithme LLL, inventé en 1982 par Lenstra, Lenstra et Lovasz, est le premier algorithme de réduction de réseaux en temps polynomial. On peut aussi le voir comme une généralisation de l'algorithme d'Euclide en dimension supérieure. Le groupe de Caen, autours de Brigitte Vallée, a développé une méthode originale appelée analyse dynamique qui s'est avérée très efficace dans l'étude des algorithmes du PGCD. Cette méthode est basée à la fois sur les méthodes classiques d'analyse d'algorithmes et sur les systèmes dynamiques. Si le cas de la dimension 1 est maintenant bien compris (cas des algorithmes du PGCD), l'étude des algorithmes en dimension supérieure ne fait que commencer. Cependant, la dynamique des algorithmes de type LLL est trop complexe pour envisager une étude directe. L'exposé expliquera comment des simplifications dans l'exécution de l'algorithme LLL peuvent conduire à des systèmes dynamiques variés. Selon le degré de simplification, les systèmes dynamiques obtenus seront des tas de sable (ou chip firing game), des systèmes dynamiques à trou, des systèmes dynamiques probabilistes, etc. Quelques résultats obtenus avec ces modélisations simplifiées seront aussi expliqués.
[11h00-11h45]
Emmanuel Hainry - Robustesse et calculabilité dans les systèmes dynamiques à perturbation [Résumé]
L'accessibilité (ou atteignabilité) est un problème indécidable pour les systèmes dynamiques. Ce problème est déjà indécidable pour des classes très restreintes de systèmes. Pourtant des algorithmes existent et résolvent parfaitement ce problème indécidable pour les instances rencontrées dans le monde réel. Nous soupçonnons que c'est la résistance aux perturbations des systèmes du monde réel qui permet de décider ce problème et montrerons qu'en effet la robustesse des systèmes implique la décidabilité de l'accessibilité pour les systèmes dynamiques à temps continu et à temps discret. Nous montrerons finalement que la robustesse est équivalente à la décidabilité de l'accessibilité.
[11h45-12h30]
Amaury Pouly - Computational Complexity of the GPAC [Slides]
[12h30-14h00]
Déjeuner
[14h00-15h00]
Marie-Pierre Béal - Systèmes sofiques-Dyck [Slides] [Ar ti cle ] [Résumé]
Les systèmes dynamiques symboliques sont des suites bi-infinies de symboles dont les facteurs finis évitent un ensemble de mots finis donné. Nous présentons les systèmes appelés sofiques-Dyck. Ces systèmes sont une généralisation des systèmes Markov-Dyck introduits par Krieger et Matsumoto. Nous montrons que ces systèmes de séquences sont exactement les systèmes dont le langages des facteurs finis est visibly pushdown. Nous donnons un théorème de décomposition des conjugaisons dites propres pour les systèmes finite-type Dyck, une sous-classe des systèmes sofic-Dyck. Nous calculons la fonction zeta, qui compte les séquences périodiques du système, pour un système sofic-Dyck.
[15h00-15h00]
Fin des journées

Inscription

L'inscription est gratuite mais obligatoire.

Pour s'inscrire, envoyer un mail sur l'adresse emmanuel.jeandel AT loria.fr

Merci de préciser lors de l'inscription:

  • si vous souhaitez donner un exposé à cette occasion.
  • A quelles journées (Frac, SDA2, Frac+SDA2) vous assistez

Informations pratiques

Les journées se déroulent au Loria, campus scientifique de l'Université de Lorraine.

Pour se rendre au Loria

Selection d'hotels:

Comite scientifique et d'organisation

  • V. Berthé
  • E. Jeandel
  • N. Ollinger
  • G. Theyssier

Participants

  • Pablo Arrighi
  • Laurent Bartholdi
  • Marie-Pierre Beal
  • Valerie Berthe
  • Sylvain Contassot-Vivier
  • Michel Coornaert
  • Martin Delacourt
  • Nazim Fates
  • Enrico Formenti
  • Bastien Le Gloannec
  • Emmanuel Hainry
  • Benjamin Hellouin de Menibus
  • Damien Jamet
  • Emmanuel Jeandel
  • Loick Lhote
  • Simon Martiel
  • Nicolas Ollinger
  • Sabrina Ouazzani
  • Simon Perdrix
  • Amaury Pouly
  • Julien Provillard
  • Gwenaël Richomme
  • Mathieu Sablik
  • Pierre-Alain Scribot
  • Pascal Vanier