Frac d'automne 2008

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 journées Frac d’automne 2008 auront lieu du lundi 1er décembre 2008 à 14h au mercredi 3 décembre 2008 à 12h à Nice, au Grand Château du campus Valrose de l’Université de Nice - Sophia Antipolis.

Plan du campus
Plan du campus via google maps

 

Inscription

Afin d’organiser ces journées, les pauses café, etc, il est demandé aux participants de s’inscrire par mail à l’adresse suivante : Nicolas.Ollinger[at]lif.univ-mrs.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

Les participants peuvent proposer des exposés (30 minutes) dans les thèmes du projet Sycomore lors de leur inscription par mail auprès des organisateurs. Il est demandé de fournir un titre ainsi qu’un résumé de quelques lignes. Titres, résumés et transparents sont à réaliser en anglais. Les exposés pouvant au choix de l’orateur être déclamés en français ou en anglais.

 

Logement

Pour l’hébergement nous pouvons vous proposer les hôtels suivants (triés par prix croissants). Informations indicatives repiquées de l’annonce d’un ancien Frac, les prix ont du augmenter.

Hôtel        Adresse        Téléphone        Prix indicatif chambre simple
Hôtel Clemenceau **   3 av. Georges Clémenceau - 06000 NICE   04 93 88 61 19   45€
Hôtel Astor **   33 rue Pastorelli - 06000 NICE   04 93 62 18 82   50€
Hôtel Star **   14 rue Biscarra - 06000 NICE   04 93 85 19 03   52€
Hôtel Acanthe **   2 rue Chauvain - 06000 NICE   04 93 62 22 44   54€
Hôtel Plaisance **   20 rue de Paris - 06000 NICE   04 93 85 11 90   54€  
Hôtel Lépante **   6 rue Lépante - 06000 NICE   04 92 62 20 55   69€
Hôtel Ibis **   41 rue Lamartine - 06000 NICE   04 93 62 14 43   72€ - 140€
Hôtel Mercure ****   28 av. Notre Dame - 06000 NICE   04 93 13 36 36   ≥ 115€

 

Programme

    Lundi 1er décembre
14h00 - 14h30 :   Accueil
14h30 - 15h00 :   Laurent Boyer, On Local Symmetries and Universality in Cellular Automata
15h00 - 15h30 :   Thomas Fernique, Weak Matching Rules
    Pause
16h30 - 17h00 :   Victor Poupet, Ultimate cellular complexity
17h00 - 17h30 :   Pierre-Etienne Meunier, Communications in cellular automata
    Dîner Frac
     
    Mardi 2 décembre
9h00 - 10h00 :   Jarkko Kari, Bounds on non-surjective 1D CA : A linear algebra approach
    Pause
10h30 - 11h00 :   Alexis Ballier, Structural aspects of tilings
11h00 - 11h30 :   Alex Borello, Real-time Language Recognition on Two-Dimensional Cellular Automata : Influence of the Neighbourhood
    Déjeuner
14h00 - 15h00 :   Kenichi Morita, Designing 1d universal reversible cellular automata
15h00 - 15h30 :   Martin Delacourt, Consequences of a finite word on cellular automata
    Pause
16h00 - 16h30 :   Alberto Dennunzio, Decidable Properties of 2D Cellular Automata
16h30 - 17h00 :   Pablo Arrighi, Universalité intrinsèque des Automates Cellulaires Quantiques
     
    Mercredi 3 décembre
9h00 - 10h00 :   Alexander Shen, Transcendental density tilings
    Pause
10h30 - 11h00 :   Grégory Lafitte, Busy beavers everywhere
11h00 - 11h30 :   Enrico Formenti, Non-uniform cellular automata
    Déjeuner
14h00 - 15h00 :   Nicolas Ollinger, Soutenance d’habilitation à diriger des recherches

Abstracts

Laurent Boyer, On Local Symmetries and Universality in Cellular Automata

Cellular automata (CA) are dynamical systems defined by a finite local rule but they are studied for their global dynamics. They can exhibit a wide range of complex behaviours and a celebrated result is the existence of (intrinsically) universal CA, that is CA able to fully simulate any other CA. In this paper, we show that the asymptotic density of universal cellular automata is 1 in several families of CA defined by local symmetries. We extend results previously established for captive cellular automata in two significant ways. First, our results apply to well-known families of CA (e.g. the family of outer-totalistic CA containing the Game of Life) and, second, we obtain such density results with both increasing number of states and increasing neighbourhood. Moreover, thanks to universality-preserving encodings, we show that the universality problem remains undecidable in some of those families.

Thomas Fernique, Weak Matching Rules

Matching rules on a set of tiles are finite constraints on the way tiles can be glued together. It is obvious to define matching rules which allow only periodic tilings to be formed. It turns out that it is also possible - although much harder - to enforce aperiodic tilings. Such constructions generally enforce a single aperiodic tiling (more precisely, its orbit under a group action), with the most celebrated example being probably the Penrose or the Robinson tilings. But there is also some "weaker" constructions, in the sense that they enforce not only one but many different aperiodic tilings. This is, for example, the case of the set of 14 Wang tiles discovered by J. Kari (later modified to get one lesser tile by K. Culik). This is also the case of so-called weak matching rules, introduced by L. Levitov for canonical tilings. Moreover, these matching rules also have an additional interesting geometric property. We will detail this construction and discuss some related open questions.

Pierre-Etienne Meunier, Communications in cellular automata

The framework of communication complexity was introduced by A.C. Yao in 1969. We intend to show here why these tools seem suitable for the study of cellular automata, by linking it both to several results and properties of cellular automata ("universalities"), and to other notions of complexity, namely Turing complexity and circuits. The ideas of this talk come from a paper (Cellular automata and communication complexity) by C. Durr, I. Rapaport and G. Theyssier, extended by the work of E. Goles and myself.

Jarkko Kari, Bounds on non-surjective 1D CA : A linear algebra approach

Based on the compactness and the Garden-of-Eden theorem, respectively, every non-surjective one-dimensional CA has an orphan (a finite word without a pre-image) and a diamond (two different words equal at the boundaries, having the same image). Also, there exist non-balanced words : words of equal length having different numbers of pre-images. We find upper bounds on the lengths of such words, using a linear algebra aproach. A similar approach was previously used to obtain a tight upper bound on the size of the inverse neighborhood of one-dimensional reversible CA.

Our bounds are the following. Consider a one-dimensional, non-surjective CA with n states and the radius-1/2 neighborhood. Then there exist words of length n that have different numbers of pre-images, there exists an orphan of length (n-3)n+5, and there exists a diamond of length at most 2n sqrt(n).

Alex Borello, Real-time Language Recognition on Two-Dimensional Cellular Automata : Influence of the Neighbourhood

A cellular automaton’s capacity to recognize a language in real time (the smallest number of time steps required for the automaton to entirely read the word in input) depends on its neighbourhood : V. Terrier proved that there exist two-dimensional languages which are recognizable in real time by a cellular automaton using von Neumann’s neighbourhood while they are not recognizable in real time by any automaton using Moore’s one. We come back here on this demonstration, with a slight use of Kolmogorov complexity inspired by the work of J. Cervelle.

Martin Delacourt, Consequences of a finite word on cellular automata

We consider one dimensional cellular automata with the standard neighborhood. On a cellular automata and with a finite word u, we look at the set of cells of the space-time diagram that are fixed for any initial configuration containing u (on the origin). This set can draw non-trivial shapes on the plane. We will essentially consider the example of drawing a parabola, which deals with some more general techniques, and with the reversibility of the automaton.

Kenichi Morita, Designing 1d universal reversible cellular automata

We study the problem how we can construct 1d reversible cellular automata (RCA) with computation universality (i.e., Turing universality). So far, several methods for designing such RCAs have been proposed. They are to simulate reversible Turing machines, to simulate cyclic tag systems, and others. As for simple universal RCAs, a 24-state model that works on infinite (ultimately periodic) configurations, and a 98-state model on finite configurations have been shown by Morita. In this talk, we give a survey on these results, as well as several techniques for designing such 1d universal RCAs. We also show a method of constructing 1d universal RCAs with one-bit communication channel.

Alexis Ballier, Structural aspects of tilings

We study the structure of the set of tilings produced by any given tile-set. For better understanding this structure, we address the set of finite patterns that each tiling contains. This set of patterns can be analyzed in two different contexts : the first one is combinatorial and the other topological. These two approaches have independent merits and, once combined, provide somehow surprising results. The particular case where the set of produced tilings is countable is deeply investigated while we prove that the uncountable case may have a completely different structure. We introduce a pattern preorder and also make use of *Cantor-Bendixson rank*. Our first main result is that a tile-set that produces only periodic tilings produces only a finite number of them. Our second main result exhibits a tiling with exactly one vector of periodicity in the countable case.

Enrico Formenti, Non-uniform cellular automata

We study the robusteness of the dynamics of cellular automata when the uniformity condition on the local rule is relaxed.

Pablo Arrighi, Universalité intrinsèque des Automates Cellulaires Quantiques

Co-authors : Renan Fargetton, Zizhu Wang.

Abstract. We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any onedimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will then correspond to one step of the simulated QCA. The simulation preserves the topology in the sense that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours.

Alberto Dennunzio, Decidable Properties of 2D Cellular Automata

We study some decidable properties of two dimensional cellular automata (2D CA). The notion of closingness is generalized to the 2D case and it is linked to permutivity and openness. We present two deep constructions which have been fundamental in order to prove our new results.

Alexander Shen,Transcendental density tilings

(talk by A.Shen joint with B.Durand, A.Romashchenko)

Penrose tiling is made by two tiles, and in a large region the proportion betwen these two tiles tends to a golden ratio. For other known tilings the fraction of each tile is also an algebraic number (since it is a component of an eigenvector of integer substitution matrix). However, the fixed point construction allows us to get any computable real number in [0,1] as a limit of tiles density (and only computable reals can be obtained in this way). We will explain the fixed point construction of aperiodic tiling with variable zoom factor and explain how to achieve any computable density.

 

Liste des participants

Nom   Etablissement
Michael Armand   ENS Cachan
Pablo Arrighi   Université de Grenoble
Alexis Ballier   Université de Provence
Alex Borello   Université de Provence
Olivier Bournez   École Polytechnique
Gianpiero Cattaneo   Università degli Studi di Milano-Bicocca, Italie
Julien Cervelle   Université Paris-Est
Martin Delacourt   Université de Provence
Marianne Delorme   Université de Lyon
Alberto Dennunzio   Università degli Studi di Milano-Bicocca, Italie
Bruno Durand   Université de Provence
Thomas Fernique   CNRS & Université de Provence
Enrico Formenti   Université de Nice Sophia-Antipolis
Fabien Givors   ENS Lyon, antenne de Nice
Pierre Guillon   Université Paris-Est
Emmanuel Jeandel   Université de Provence
Sandrine Julia   Université de Nice Sophia-Antipolis
Tarik Kaced   ENS Lyon, antenne de Nice
Jarkko Kari   University of Turku, Finlande
Grégory Lafitte   Université de Provence
Marc Lasson   ENS Lyon, antenne de Nice
Bruno Martin   Université de Nice Sophia-Antipolis
Jacques Mazoyer   Université de Lyon
Luca Manzoni   Università degli Studi di Milano-Bicocca, Italie
Pierre-Etienne Meunier   ENS Lyon
Kenichi Morita   Hiroshima University, Japon
Guilhelm Mouli   ENS Lyon, antenne de Nice
Nicolas Ollinger   Université de Provence
Kevin Perrot   ENS Lyon, antenne de Nice
Victor Poupet   Université de Provence
Gaétan Richard   Université de Provence
Andrei Romashchenko   CNRS & Université de Provence
Mathieu Sablik   Université de Provence
David Salinas   ENS Lyon, antenne de Nice
Alexander Shen   CNRS & Université de Provence
Felix Sipma   ENS Lyon, antenne de Nice
Siamak Taati   Université de Nice Sophia-Antipolis
Michael Weiss   Università degli Studi di Milano-Bicocca, Italie
Jean-Baptiste Yunès   Université Paris 7

 

Organisateurs

Pour toute question, vous pouvez vous adresser à :
-  Bruno Durand,
-  Enrico Formenti,
-  Grégory Lafitte,
-  Nicolas Ollinger,
-  Gaétan Richard.