Les rencontres FRAC sont des rencontres semestrielles francophones autour des thèmes du Projet ANR Sycomore : « Systèmes complexes et modèles de calcul ».

Lieu et dates

Les rencontres FRAC d’été 2007 auront lieu les jeudi 28 et vendredi 29 juin à Nice, au Grand Château du campus Valrose de l’Université de Nice - Sophia Antipolis.

Plan d’accès à l’université
Plan du campus

Inscription

Afin d’organiser au mieux ces journées, il est demandé aux participants de s’inscrire par mail à l’adresse benoit.masson [at] i3s.unice.fr. Il n’y a pas de frais d’inscription et les frais autres que l’organisation stricte des rencontres (matériel, salles, pauses café) sont à la charge des participants (transport, logement, repas, dîner du jeudi soir).

Déroulement des journées

Ces journées seront dédiées aux Systèmes Complexes dans l’esprit de Sycomore, avec un accent sur les Systèmes Dynamiques Discrets et leurs connexions avec l’informatique théorique.

Les participants peuvent proposer des exposés, courts (30 min) ou longs (1h), lors de leur inscription. Dans ce cas, merci de le signaler par mail à benoit.masson [at] i3s.unice.fr en indiquant la durée souhaitée, un titre et un résumé de 5 à 10 lignes (Rq : dans le cas où le nombre d’exposés proposés serait trop important, nous pourrions être amenés à faire une sélection parmi les exposés).

Les exposés peuvent être en français ou en anglais, les transparents de préférence en anglais.

Logement

Pour l’hébergement nous pouvons vous proposer les hôtels suivants (triés par prix croissants).

Programme

  Laurent Boyer, Limit probabilities of properties of CA

  Julien Cervelle, Vieilles réminiscences sur les pavages

Nous allons revisiter une vieille preuve sur les pavages et ses connexions avec le théorème de Rice pour les pavages.

  Bruno Durand, About fixed point cellular automata

  Alexandre Goldsztejn, A New Containment Method For Rigorous Shadowing

A reliable simulation usually refers to a simulation that presents a small global error. This study of reliability is called forward error analysis. However, this kind of analysis is useless when one studies chaotic systems, because such systems will present exponential growth global errors no matter how small is the local error. In this context, where the forward error analysis does not provide any interesting information, the backward error analysis may allow extracting information from simulations that diverge exponentially from the exact solution.

The backward error analysis consists of finding a modified problem P’ for which the simulation, which diverges exponentially from the exact solution of P, is a good approximation of the exact solution of P’. Among other backward error analysis techniques, shadowing allows modifying the problem P by changing its initial condition, while disallowing changes in the defining equation. Therefore, the question asked by shadowing error analysis is "Given a dynamical system, an initial condition and a simulation of this system (simulation which certainly diverges exponentially), can we find a different initial condition for which our simulation is accurate ?" We will introduce the shadowing backward analysis and present our new containment algorithm for the rigorous proof of the existence of a shadow. This algorithm results of an original application of the interval analysis for the rigorous verification of the hypotheses of a containment theorem. Our method is both simpler and more efficient than the previous containment algorithms. Applications to the rigorous proof of chaos in discrete dynamical systems are reported.

  Jarkko Kari, A new proof for the undecidability of the tiling problem

We give a new proof for the undecidability of the tiling problem. The proof is based on simulating piecewise affine transformations by Wang tiles. The construction is such that it reduces the immortality problem of piecewise affine maps into the tiling problem. On the other hand, the immortality question is undecidable - a fact that easily follows from a result by Hooper 1966 - and hence the undecidability of the tiling problem follows. We also show how the proof can be modified to demonstrate the undecidability of the tiling problem on the hyperbolic plane, thus answering an open problem posed by R.M.Robinson 1971.

  Petr Kůrka, Holomorphic arithmetics

We construct a symbolic representation of the complex sphere using the Moebius transformations.

  Benoît Masson, A new topology for sand automata

We define a new topology for sand automata, so that the configurations space is compact. We show that all topological properties are preserved, and give an overview of some new ones.

   Nicolas Ollinger, Cellular Automata, Tilings, Undecidability : revisiting classics (TBA)

  Adrien Richard, Influence des circuits de rétroaction dans les réseaux d’automates asynchrones

  Gaétan Richard, Automates de cartes à pile(s), particules et collisions

  Véronique Terrier, Simulation of one-way cellular automata by boolean circuits

A characteristic of one-way cellular automata (OCA) is that each cell c acts as a rational transducer operating on the sequence of states of its left neighbor c-1. So the key result to simulate OCA by boolean circuits is the simulation of rational transducer by boolean circuits as designed by Ladner and Fischer. For a transducer which involves t iterations, the simulating boolean circuit is of depth O(log(t)).

As a consequence, an OCA which works in space n and time t(n) corresponds to a succession of n transducers which operate on words of length t(n) and so can be simulated by a boolean circuit of depth O(n log(t(n))).

In this talk, we will present a simple trick which leads to a smaller circuit and will evaluate its depth.

  Guillaume Theyssier, Higher dimensionnal dynamics in cellular automata

  Sandrine Julia, Reduced languages as ω-generators

We consider the following decision problem : “Is a rational language generated by a code ?” Since 1994, the codes admit a charaterization in terms of infinite words. We derive from this result the definition of a new class of languages, the reduced languages. A code is a reduced language but the converse does not hold. The idea is to “reduce” easy-to-obtain minimal ω-generators in order to obtain codes as ω-generators.

  Sébastien Verel, Vers une résolution du problème des fusiliers à 5 états par métaheuristiques

Participants

Liste des participants au 27 juin 2007 (total 35) :

Organisateurs

Enrico Formenti

Sandrine Julia

Bruno Martin

Benoît Masson