FRAC d'hiver 2012

The 10th edition of the workshop FRAC "Complex systems and computation models" will take place the 22, 23 and 24 february 2012 at Paris-Est Créteil University.

It will be located at CMC "salle des thèses", second floor, building P2.

Topic include, but are not limited to:

  • Computational models
  • their topological, ergodic, algebraic and structural aspects
  • Computability
  • Complexity
  • Complex systems
  • Symbolic dynamics


Wednesday 22
10:00-10:30 Welcome of participants
10:30-10:45 Opening
10:45-11:45 Serge Grigorieff Functionals using bounded information and the dynamics of algorithms (common work with Pierre Valarcher)
12:00-14:00 Lunch
14:00-14:20 Fabien Givors Sub-computabilities
14:20-15:20 Alexander Shen Topological arguments for Kolmogorov complexity
15:20-15:50 Coffe break
15:50-16:20 Kévin Perrot Kadanoff sand pile model
16:20-16:50 Bastien Le Gloannec Substitutions and strongly deterministic tilesets
16:50-17:20 Laurent Bienvenu On absolutely undecidable sets
Thursday 23
10:30-11:30 Enrico Formenti Particles dynamics and return times
11:30-11:50 Anahi Gajardo Temporal symmetry in cellular automata
12:00-14:00 Lunch
14:00-14:30 Pedro Montealegre The computational complexity of bootstrapping percolation
14:30-15:00 Julien Cervelle Decidability of first order dynamical properties of linear cellular automata
15:00-15:30 Coffe break
15:30-16:00 Julien Provillard Non-uniform cellular automata
16:00-16:30 Guillaume Theyssier On μ-limit sets of cellular automata
16:30-17:00 Catalin Dima Estimating covert channel capacities using transducer entropy
evening Conference diner
Friday 24
10:00-10:30 Luidnel Maignan A spatio-temporal algorithmic point of view on firing squad synchronisation problems
10:30-11:00 Damien Regnault About non-monotony in boolean automata networks
11:00-11:30 Coffe break
11:30-12:00 Gregory Lafitte Computability and what not
12:00-12:30 Serghei Verlan Computational properties of the operations of insertion and deletion on words


Véronique Terrier GREYC University of Caen
Damien Regnault IBISC University of Evry-Val-d’Essone
Pierre-Étienne Meunier LAMA University of Savoie
Fabien Givors LIF University Aix-Marseille
Gaétan Richard GREYC University of Caen
Gregory Lafitte LIRMM University of Montpellier 2
Alexandre Shen LIRMM University of Montpellier 2
Emmanuel Jeandel LIRMM University of Montpellier 2
Bastien Le Gloannec LIFO University of Orléans
Pierre Guillon IML CNRS
Julien Provillard I3S University of Nice Sophia-Antipolis
Pascal Vanier LIF University Aix-Marseille
Luidnel Maignan LIAFA University Paris 7
Tarik Kaced LIRMM University of Montpellier 2
Enrico Formenti I3S University of Nice Sophia-Antipolis
Christophe Papazian I3S University of Nice Sophia-Antipolis
Guillaume Theyssier LAMA University of Savoie
Kevin Perrot LIP École Normale Supérieure de Lyon
Anahi Gajardo University of Concepción
Eric Goles University Adolfo Ibanez
Pedro Montealegre University of Chile
Serghei Verlan LACL University Paris Est
Catalin Dima LACL University Paris Est
Irene Marcovici LIAFA University Paris 7
Pierre Valarcher LACL University Paris Est
Laurent Bienvenu LIAFA University Paris 7
Antoine Taveneaux LIAFA University Paris 7
Etienne Muller LIAFA University Paris 7
Rupert Hölzl LIAFA University Paris 7
Benoît Monin LIAFA University Paris 7
Laurent Boyer SAMM University Paris 1
Alex Borello LIF University Aix-Marseille


The participation to the conference is free but, for the need of organization, a preliminary registration by e-mail at is mandatory. Participant can propose a short talk or a more general introduction to particular topic. Please provide the following information:

First name:
Last name:
Participation to lunch and diner: Wednesday lunch Y/N, Thursday lunch Y/N, Diner Y/N
Talk (optional yet recommended): Y/N
  Requested time: 20mn/30mn/1h


By mass transportation
The nearest RER D station is "le vert de maison". For schedule see (or mobile version The nearest Metro station (line 8) is "Créteil-Université". For schedule see (or mobile version See attached files at the end of the page for the map for stations to conference place.
By car
There is a public access parking lot under the University. When your car is near the barrier, it opens automatically (security through obscurity). The entrance of the parking lot is at GPS coordinate 48.788192,2.446024 and address (at least for 61 avenue du General du Gaulle, 94000 Créteil.


Though there are hotels in Créteil, I suggest to book a hotel in Paris, either near the RER D stations (for instance Gare de Lyon) or near the stations of line 8. See for instance


There are two airports in Paris: ORY (Paris-Orly) and CDG (Paris-Charles de Gaulle). Other airports (like Paris-Beauvais) are far from Paris.