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
|